Ai Ai Developer’s Guide #1: MGL

 

MGL Game Development Guide

Introduction

The MGL (Modular Game Language) file structure is designed by Cameron Browne and Stephen Tavener, and is closely based on JSON.
This guide gives a broad outline of the design, and how to use MGL to make games. It is far from definitive, so I strongly recommend looking at the individual MGL files in a suitable text editor for useful examples. Hopefully the format is easy to read.

Components of the system

The structure of Ai Ai splits the code base into roughly three components:

  • The GUI
  • The AIs (which I also refer to as searches, since the search the moves available for good moves)
  • The games themselves

This guide is concerned with the games, and how to define them. All games are initially defined using MGL, but fall into two general categories:

  • Games with custom java implementations: these use MGL to define parameters for the code, but typically contain a something like: "class":"ai.mogal.mgl.game.LineGames" to tell Ai Ai to load a custom class instead of the default rule handler. Most of these are designed to pay a single game very quickly, but it is worth mentioning LineGames as a generic class which can play a wide variety of N-in-a-row games. Look at the (optimised) implementations of Connect6.mgl, Yavalath.mgl, or Unfair.mgl for some good examples.
  • MGL games, glued together from small blocks of java called rules and ops. These are discussed in this guide. Note: the rules and operations are not a complete set by any stretch of the imagination. I take requests!

MCTS and ActionInstances

MCTS

Before I get into the details of the rules, you may need to know a few things about how the AI works, and how we handle actions.

Unlike traditional Minimax searches, MCTS searches evaluate a game by performing random playouts until the end of the game, building a tree as they go, so the initial random approximations become better over time.
This removes the need for heuristic functions where the AI must stop searching and calculate the value of a given position using an algorithm, which makes it ideal for general game playing.
In fact, all we really need for the AI to find a good move are the following:

  1. The number of moves available from the current position,
  2. A way of applying the nth move to the current position to move to a new position,
  3. A way of calculating when the game has ended,
  4. A way of figuring out the final result.

The last two items on the list above are usually very closely related, and can be treated as a single function.

We do, of course, need a few other things as well, mostly for board setup and graphical display, but these are the basics.

The ActionInstance

The generate rules create and manipulate objects called ActionInstances. These contain the information required to apply a move, and have the following structure. Aside: you probably won’t be creating or manipulating these things directly, but you should have an idea of their capabilities.

	priority: games like draughts favour captures over non-captures
	generator: the object which will apply this move to the current state if it is selected
	actionType: defined by the generator to select the type of move (see BoardActions below)
	p1: integer parameter, e.g. the 'from' space for a move
	p2: integer parameter, e.g. the 'to' space for a move
	p3: object containing any parameters that don't fit in p1 or p2
	next: another action instance - a move could consist of several moves chained together

Note that it is possible to avoid using ActionInstances, but you will have to override almost each individual rule in order to do so.
Some of the strict placement games do this by using an empty cells array.
The ‘unoptimised’ version of gomoku.mgl is a good example.

BoardActions

While the action instances do not enforce any particular action type, there is an enumerated type called BoardActions which defines a set of actions which between them allow most game actions to be generated. These are as follows:

  • ADD : place a piece on the board
  • REMOVE : removes a piece from the board
  • SWAP : exchanges the location of two pieces
  • SWAP_SIDES : pie rule
  • CHANGE_OWNER : changes the owner of a single piece
  • SET : sets a key-value pair for the current piece
  • TRANSLATE : moves a piece from one location to another

Most rules and operations described below which process lists of actions expect one of the above actions.

Overall file structure

The file is made up of a number of sections; order irrelevant.

detail This section contains game details which can be displayed by the GUI, such as name, rules, author
type Information describing the game type and potentially controlling how the game is to be handled; this information is ignored at present, but watch this space.
agent List of named players, defines the number of players amongst other things.
world This determines the equipment with which the game will be played. This is partly used for graphical display of the pieces, but some rules may be inferred from the pieces and board topology. rule The rules, where the game will be defined. All of these rules have useful defaults, so most games will only require a few rules to be defined. search Parameters for use in search and playouts. In particular, playoutMoveLimit and gameMoveLimit restrict the number of moves in a random playout, and before declaring a game a draw, respectively.

Rules

rule.start

Sets up the board at the start of the game.

start.Default Takes a list of pieces and locations, and adds them to the board. See draughts.mgl or reversi.mgl for examples.
start.RandomFill Takes a list of pieces, and adds them to the board in random locations. See WebOfFlies.mgl or QuantumLeap.mgl for examples.

rule.evaluate

Determines how the AI will assess who has won/lost from a given position

evaluate.Default Performs a random playout to end of game, invokes rule.enumerate, rule.apply and rule.end to do so.
evaluate.SurroundCapture Custom playout with surround captures for games like go, margo.
evaluate.strictPlacement Highly optimised playout for games where players alternate placing pieces, which are never moved or removed.
evaluate.C4Heuristic Highly optimised playout for Connect 4.

rule.enumerate

Determines how many moves are available from the current position

enumerate.Default Generates the moves by calling rules.generate and returns the number of available moves.
enumerate.EmptyCellCount Counts the number of empty cells (optimisation for strict placement games).
enumerate.EmptyRegionCount Counts the number of empty cells in one or more regions (e.g. when pieces can only be entered from the top (Connect 4) of the board).

rule.generate

Generates the available moves into an action list. Action lists can be combined and further manipulated.

generate.Default Generates the moves by iterating through any game objects implementing the ActionGenerator interface – this effectively allows pieces to define their own movements.
generate.EmptyCells Generates one ADD action for each empty cell.
generate.C4Gen Highly optimised generator for Connect 4.
generate.CounterAdd Generates {add,decrement counter} moves for empty spaces; for adding pieces from a limited pool.
generate.CounterRemove Generates {remove, increment counter} moves (see CounterAdd).
generate.EmptyNeighbours Generates ADD actions for empty spaces next to occupied spaces.
generate.Pass Generates a single voluntary PASS action.
generate.NextActor Generates a single NEXT_PLAYER action. This is generally added to all actions but could be omitted if a player has several turns in a row.
generate.MovesForPiece Generates moves for pieces of the specified type. A restricted version of the default rule. The ownerType parameter allows specification of all pieces/friendly pieces/pieces belonging to single player.
generate.Remove Generates REMOVE actions for pieces of the specified type. The who parameter allows specification of whose pieces to remove.
generate.Translations Generates TRANSLATE actions moving each piece to each unoccupied space. This may be slow, due to the large number of actions. The ownerType parameter allows specification of all pieces/friendly pieces/pieces belonging to single player.
generate.SetValue Generates a setValue action for a given location, key, and value.
generate.SupportedCells Generates an ADD action for all cells at the base level, or that are completely supported from below.

rule.apply

Applies the nth move to the current board state to produce a new board state.

apply.Default Generates the available actions (see rule.generate), applies the nth move.
apply.AddFromEmptyCell Adds a piece to the nth empty cell, does not generate actions.

rule.nextAgent

Determines which player moves next. This rule is unusual, in that the default action depends on the number of players. Two player: Alternating2P, otherwise NextActive.

describe.Alternating2P Alternating two-player game; if player 1 moved, it is now player 2’s turn and vice versa.
describe.DoubleMove p1, p1, p2, p2, p1, etc.
describe.MultiMove Generic rule. Allows for certain number of moves at start, followed by repeating pattern (12*, etc.) or even progressive moves.
describe.NextActive Next active player, in turn order – for multiplayer games with player elimination.

rule.endCalled after applying a move to see if the game has ended and determine a winner. End rules take the required outcome as a parameter.
End rules are unusual, in that there may be multiple rules, which will be applied in turn.
End rules can also be combined in other ways.rule.describeDescribes the nth board action; used for display of moves to the user, saving and loading games, etc.OperationsOperations are modifiers, which can be used to combine or modify other rules.Action ModifiersThe following operations receive a list of actions and modify it in some way.Ops that Return a Value (Game-Related)MThe following operations generate a value for use elsewhere, e.g. a conditional clause.Logical/Control of Flow OpsOps that Return a Value (Other)The worldThe ‘world’ section of the MGL file is nominally where the board equipment is defined. Of course, the equipment and game play are intimately linked.
Changing the board from a square grid to a hex grid, for example, can have a significant effect on the game, as can removing the knights from a game and replacing them with bishops.boardThe board class is the representation of the board. At the moment, only class “world.board.IntArray” is defined. This will represent almost any board as a 1-dimensional array of integers.
These can be used to store ownership information, an index into an array of pieces, or other items.The topology class (see below) maps the 1d array of cells onto board coordinates, which may have any number of dimensions.The following board parameters are useful to know:

  • trackEmpties : keeps a separate array of empty cells, used to optimise performance in strict placement games.
  • trackGroups : keeps track of which group each piece is in, required for connection games
  • trackPieces : determines whether board entries show ownership, or are indexes into an array of pieces.

TopologyThe topology determines the connection between board cells, defining directions, cell names, and the like. The following topologies are supported at present:

  • Hex : Standard hex board, rhombus.
  • HexHex : Hexagonal board made of hexagons.
  • Shibumi : Square Pyramidal 4×4
  • SquareAll : Square/rectangular board with orthogonal and diagonal connections between squares.
  • SquareDiag : Square/rectangular board with diagonal connections between squares only.
  • SquareOtho : Square/rectangular board with orthogonal connections between squares only.
  • SquareKnight : Square/rectangular board with knight’s moves between squares.
  • SquarePyramidal : 3D topology; square pyramidal.
  • StarHex : Chinese Checkers board.
  • TriHex : Triangular board, made of hexagons.

PiecesTODOSkinsTODO

end.Captured Win by capturing a piece, or pieces.
end.Connects Win by having a group with pieces in all the listed regions.
end.ConnectsLast Win by having a group with pieces in all the listed regions; only tests the group containing the last piece played.
end.CountAfterPass Once all players have passed consecutively, player with the most pieces wins/loses as required.
end.EndAfterPass Once a player passes, they win/lose as required. Note that in a multiplayer game, it is possible for one player to lose but the others ontinue playing.
end.Line Win/lose by making a line of specified length in specified directions.
end.NoEmpties End the game when the board is full, marking remaining active players as required. This is usually a secondary rule, e.g. draw in Tic Tac Toe if board is full and no one wins first.
end.NoMoves Player wins/loses when they are forced to pass.
end.WOFCountAfterPass Special end rule for Web of Flies.
end.WormsEnd Intended to be a special flood fill rule for Worms (not implemented).
end.Yavalath Optimised function for Yavalath. you can do the same thing with end.Line though.
describe.Default Generates the available actions, asks the nth action for the description.
describe.FullDescription Generates the available actions, asks the nth action for the description. Unlike the default action, iterates through the whole action chain.
describe.DescribeEmptyCell Creates a move description for the nth empty cell, without generating the actions.
describe.ShibumiDescriptions Mostly produces the same output as the default actions, but with a special format for ADD actions.
game.op.action.AscendingOnly Removes any actions which do not involving raising a piece to a higher level. (Shibumi)
game.op.action.CapturesOnly Removes any actions which do not result in a capture.
game.op.action.Conditional test…then…else. The test is applied to each action in the list, in turn.
game.op.action.FlipCapture Modifies an action list to add Othello-style captures to each ADD.
game.op.action.FlipCaptureChain Modifies an action list to add Othello-style captures to each ADD. Flipped pieces can cause chain reactions.
game.op.action.HighestPriority Filters out all action except those with the highest priority. See draughts.mgl for example.
game.op.action.Ko Removes actions that would repeat a previous board position – moves parameter is how many turns of history to check (-1 for superko).
game.op.action.MultiMove Removes the implicit nextPlayer action from the and of the actions unless turn mod divisor = remainder
converting alternating turn games into games with multiple consecutive turns by the same player. NOTE: rule.nextAgent can usually perform the same purpose more efficiently.
game.op.action.RemoveReplacementCaptures Removes all capturing actions (by replacement) from the action list.
game.op.action.NoPass Removes all pass moves from the action list.
game.op.action.NotSupporting Removes actions for pieces that are supporting other pieces (think Shibumi/Pylos) – see also SupportedOnly.
game.op.action.RemoveCaptures Removes all capturing actions (by surrounding) from the action list.
game.op.action.RemoveTwoAfterSquare Removes up to two pieces after a square is completed (Pylos).
game.op.action.SupportedOnly Removes all actions except those that are stable (base level or supported from below – think Shibumi/Pylos) – see also NotSupporting.
game.op.action.SurroundCapture Modifies ADD actions to remove adjacent pieces which have no neighbours.
game.op.action.Swap Adds a swap sides action to the action list on the second move only.
game.op.action.VoluntaryCapture Modified version of SurroundCapture that makes each capture voluntary.
This increases the action list by about 2^n where n is the number of captured stones, so don’t be surprised if your computer grinds to a halt.
game.op.value.ActionsSoFar Returns the number of actions since the start of the game.
game.op.value.Value Finds the piece in location counterLocation and retrieves the value associated with key stored with that piece.
op.And Logical AND – can take booleans and numbers (0 = false, else true)
op.Or Logical OR – can take booleans and numbers (0 = false, else true)
op.Case A case statement of sorts. The first argument should be an operation returning a value, the second argument is a mapping from values to actions.
op.CrossProduct Merges two or more collections of ActionInstance together so
{A,B,C} , {a,b,c} becomes { Aa, Ab, Ac, Ba, Bb, Bc, Ca, Cb, Cc }
Passes and NextMove records will be merged.
A collection in this case could be a single ActionInstace record.
op.If test… then… else. Unlike conditional above, this op acts on values rather than lists.
op.Union Returns the union of two or more objects, which must be either ActionInstances or collections of ActionInstances
op.value.Even Returns true iff the supplied number is even
op.value.Odd Returns true iff the supplied number is odd