Game Description Language

Quoted in an article in New Scientist, Genesereth pointed out that although Deep Blue can play chess at a grandmaster level, it is incapable of playing checkers at all because it is a specialized game player.^[1] 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.

GDL is a variant of Datalog, and the syntax is largely the same. It is usually given in prefix notation. Variables begin with ?.^[2]

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 the player (or role) ?r makes the move ?m in 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 ?r in the current state.

init

This predicate refers to a fact about the initial game state.

legal

The predicate (legal ?r ?m) means that ?m is a permissible move for role ?r in the current state.

next

This predicate refers to a 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 an end state of the game.

true

This predicate refers to a fact about the current game state.

A game description in GDL provides complete rules that define the game's players, initial state, valid moves, how the game state is updated, how the game ends, and how a winner is determined.

Facts that define the roles in a game. For example, the two-player game tic-tac-toe could define players in GDL with (role xplayer) and (role oplayer).

Rules that entail all facts about the initial game state. The following example describes an empty three-by-three tic-tac-toe board, with player x making the starting move:

(init (cell 1 1 blank))
...
(init (cell 3 3 blank))
(init (control xplayer))

Rules that describe each move which can be taken by a player, based on the current game conditions. A tic-tac-toe player can mark a cell if it is currently blank, and it is the player's turn to move. In GDL:

(<= (legal ?player (mark ?m ?n))
    (true (cell ?m ?n blank))
    (true (control ?player)))

Rules that describe all facts about the next state relative to the current state and the moves taken by the players. For example:

(<= (next (cell ?m ?n x))
    (does xplayer (mark ?m ?n)))
(<= (next (cell ?m ?n o))
    (does oplayer (mark ?m ?n)))

Rules that describe the conditions under which the game ends. In tic-tac-toe, the game is over if either player makes three marks in a line, or there are no more blank spaces:

(<= terminal
    (line x))
(<= terminal
    (line o))
(<= terminal
    not boardopen)

The values that determine which player wins in an end state. An example is:

(<= (goal xplayer 100)
    (line x))
(<= (goal oplayer 0)
    (line x))

GDL can describe finite games with an arbitrary number of players. However, GDL cannot describe games that contain an element of chance (for example, rolling 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). An extension of GDL known as the Game Description Language for Incomplete Information Games (GDL-II) extends the language by two keywords, sees and random, that allow for the description of elements of chance and incomplete information.^[3] The statement (sees ?r ?p) means that role ?r perceives ?p in the next game state. The random 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)))

Michael Thielscher also created a further extension, GDL-III, a general GDL with imperfect information and introspection, that supports the specification of epistemic games—those characterized by rules that depend on the knowledge of players.^[4]

In classical game theory, games can be formalized in extensive and normal forms. For cooperative game theory, games are represented using characteristic functions. Some subclasses of games allow special representations in smaller sizes, also known as succinct games. Over time, other formalisms and languages for representing different game types have been developed, due in part to the needs of interdisciplinary research.^[5] Some of these alternative representations include time-related aspects:

This section needs expansion. You can help by adding to it. (July 2019)

A 2016 paper "describes a multilevel algorithm compiling a general game description in GDL into an optimized reasoner in a low level language".^[19]

A 2017 paper uses GDL to model the process of mediating a resolution to a dispute between two parties and presented an algorithm that uses available information to efficiently do so.^[20]

• First-order logic
• Logic translation