Game Description Language

Game Description Language (GDL) is a specialized logic programming language designed by Michael Genesereth. The goal of GDL is to allow the development of AI agents capable of general game playing. It is part of the General Game Playing Project at Stanford University.

GDL is a tool for expressing the intricacies of game rules and dynamics in a form comprehensible to AI systems through a combination of logic-based constructs and declarative principles.

In practice, GDL is often used for General Game Playing competitions and research endeavors. In these contexts, GDL is used to specify the rules of games that AI agents are expected to play. AI developers and researchers harness GDL to create algorithms that can comprehend and engage with games based on their rule descriptions. The use of GDL paves the way for the development of highly adaptable AI agents, capable of competing and excelling in diverse gaming scenarios.

This innovation is a testament to the convergence of logic-based formalism and the world of games, opening new horizons for AI's potential in understanding and mastering a multitude of games. Game Description Language equips AI with a universal key to unlock the mysteries of diverse game environments and strategies.

Purpose of GDL

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. 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) ?r makes 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 true fact about the initial game state.

legal

The predicate legal(?r,?m) means that ?m is a legal move for role ?r in 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))

Extensions

GDL-II

With GDL, one 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). 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 ?r perceives ?p in 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)))

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.

Other formalisms and languages for game representation

See also: Game theory § Representation of games

In classical game theory, games can be formalised 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. Some of the newer developments of formalisms and languages for the representation of some subclasses of games or representations adjusted to the needs of interdisciplinary research are summarized as the following table. Some of these alternative representations also encode time-related aspects:

Name	Year	Means	Type of games	Time
Congestion game	1973	functions	subset of n-person games, simultaneous moves	No
Sequential form	1994	matrices	2-person games of imperfect information	No
Timed games	1994	functions	2-person games	Yes
Gala	1997	logic	n-person games of imperfect information	No
Graphical games	2001	graphs, functions	n-person games, simultaneous moves	No
Local effect games	2003	functions	subset of n-person games, simultaneous moves	No
Game Petri-nets	2006	Petri net	deterministic n-person games, simultaneous moves	No
Continuous games	2007	functions	subset of 2-person games of imperfect information	Yes
PNSI	2008	Petri net	n-person games of imperfect information	Yes
Action graph games	2012	graphs, functions	n-person games, simultaneous moves	No

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.

See also

• General Game Playing
• Artificial Intelligence

External links

• Game Description Language Specification Archived 2013-04-12 at the Wayback Machine
• Refereed paper introducing GDL-II