Game Description Language


Game Description Language, or GDL, is a logic programming 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. GDL is hereby one of alternative representations for game theoretic problems.

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
;does
;goal
;init
;legal
;next
;role
;terminal
;true

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:

Initial state

Rules that entail all facts about the initial game state. An example is:

...

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:

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:

Termination

Rules that describe the conditions under which the current state is a terminal one. An example is:

Goal states

The goal values for each player in a terminal state. An example is:

)
)

Extensions

GDL-II

With GDL, one can describe finite games with an arbitrary numbers of players. However, GDL cannot describe games which contain an element of chance or games where players have incomplete information about the current state of the game. 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
;random
The following is an example from a GDL-II description of the card game Texas hold 'em:

)

)

GDL-III

Michael Thielscher also created a further extension, GDL-III, a general game description language with imperfect information and introspection, that supports the specification of epistemic games — ones characterised by rules that depend on the knowledge of players.

Applications

A 2016 paper "describes a multilevel algorithm compiling a general game description in GDL into an optimized reasoner in a low level language".
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 efficiently to do so.