Game Description Language
Game Description Language, or GDL, is a language designed by Michael Genesereth as part of the General Game Playing Project at Stanford University, California. GDL describes the state of a game as a series of facts, and the game mechanics as logical rules.
Purpose of GDL
Quoted in an article in New Scientist , Genesereth pointed out that although Deep Blue is able to play chess at a grandmaster level, it is incapable of playing checkers at all because it is a specialized game player. Both chess and checkers can be described in GDL. This enables general game players to be built that can play both of these games and any other game that can be described using GDL.
Specification
Syntax
GDL is a variant of Datalog, and the syntax is largely the same. It is usually given in prefix notation. Variables begin with "?".
Keywords
The following is the list of keywords in GDL, along with brief descriptions of their functions:
distinct- This predicate is used to require that two terms be syntactically different.
does- The predicate
does(?r,?m)means that player (or role)?rmakes move?min the current game state.
goal- The predicate
goal(?r,?n)is used to define goal value?n(usually a natural number between 0 and 100) for role?rin the current state.
init- This predicate refers to a true fact about the initial game state.
legal- The predicate
legal(?r,?m)means that?mis a legal move for role?rin the current state.
next- This predicate refers to a true fact about the next game state.
role- This predicate is used to add the name of a player.
terminal- This predicate means that the current state is terminal.
true- This predicate refers to a true fact about the current game state.
Rules
A game description in GDL provides complete rules for each of the following elements of a game.
Players
Facts that define the roles in a game. The following example is from a GDL description of the two-player game Tic-tac-toe:
(role xplayer) (role oplayer)
Initial state
Rules that entail all facts about the initial game state. An example is:
(init (cell 1 1 blank)) ... (init (cell 3 3 blank)) (init (control xplayer))
Legal moves
Rules that describe each move by the conditions on the current position under which it can be taken by a player. An example is:
(<= (legal ?player (mark ?m ?n))
(true (cell ?m ?n blank))
(true (control ?player)))
Game state update
Rules that describe all facts about the next state relative to the current state and the moves taken by the players. An example is:
(<= (next (cell ?m ?n x))
(does xplayer (mark ?m ?n)))
(<= (next (cell ?m ?n o))
(does oplayer (mark ?m ?n)))
Termination
Rules that describe the conditions under which the current state is a terminal one. An example is:
(<= terminal
(line x))
(<= terminal
(line o))
(<= terminal
not boardopen)
Goal states
The goal values for each player in a terminal state. An example is:
(<= (goal xplayer 100)
(line x))
(<= (goal oplayer 0)
(line x))
Extension
With GDL one can describe finite games with an arbitrary numbers of players. However, GDL can not describe games which contain an element of chance (for example, rolling of dice) or games where players have incomplete information about the current state of the game (for example, in many card games the opponents' cards are not visible). GDL-II, the Game Description Language for Incomplete Information games, extends GDL by two keywords that allow for the description of elements of chance and incomplete information:
sees- The predicate
sees(?r,?p)means that role?rperceives?pin the next game state.
random- This constant refers to a pre-defined player who chooses moves randomly.
The following is an example from a GDL-II description of the card game Texas hold 'em:
(<= (sees ?player ?card)
(does random (deal_face_down ?player ?card)))
(<= (sees ?r ?card)
(role ?r)
(does random (deal_river ?card)))