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.{{Cite web|url=http://www.newscientisttech.com:80/channel/tech/mg19125626.100.html|title=Producing the ultimate game-playing bots - tech - 29 July 2006 - New Scientist Tech|last=Biever|first=Celeste|date=2006-07-29|archive-url=https://web.archive.org/web/20070811111042/http://www.newscientisttech.com/channel/tech/mg19125626.100.html|archive-date=11 August 2007|url-status=live}} 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 "?".{{cite web |last1=Love |first1=N |last2=Genesereth |first2=M |last3=Hinrichs |first3=T |title=General game playing: game description language specification. Tech. Rep. LG-2006-01 |url=http://logic.stanford.edu/reports/LG-2006-01.pdf |website=Stanford University |publisher=Stanford University, Stanford |access-date=1 July 2019 |date=2006}}

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 {{code|(does ?r ?m)|scheme}} means that player (or role) ?r makes move ?m in the current game state.

;goal

:The predicate {{code|(goal ?r ?n)|scheme}} 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 {{code|(legal ?r ?m)|scheme}} 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.

A game description in GDL provides complete rules for each of the following elements of a game.

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)

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))

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)))

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)))

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)

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

(<= (goal xplayer 100)

(line x))

(<= (goal oplayer 0)

(line x))

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:{{cite journal |last1=Thielscher |first1=M |editor1-last=Fox |editor1-first=M |editor2-last=Poole |editor2-first=D |title=A general game description language for incomplete information games |journal=Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010 |date=2010 |url=http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1727 |access-date=1 July 2019 |publisher=AAAI Press |location=Atlanta}}

;sees

:The predicate {{code|(sees ?r ?p)|scheme}} 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)))

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.{{cite book |last1=Thielscher |first1=Michael |title=Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence |date=2017 |publisher=IJCAI |isbn=978-0-9992411-0-3 |chapter-url=https://www.ijcai.org/proceedings/2017/0177.pdf |access-date=1 July 2019 |chapter=GDL-III: A Description Language for Epistemic General Game Playing}}

{{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.{{cite arXiv |last1=Tagiew |first1=Rustam |title=If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction |date=3 May 2011 |eprint=1105.0558 |class=cs.GT }} Some of these alternative representations also encode time-related aspects:

{{expand section|date=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".{{cite book |last1=Kowalski |first1=Jakub |last2=Szykuła |first2=Marek |title=AI 2013: Advances in Artificial Intelligence: 26th Australasian Joint Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings |date=2013 |pages=234–245 |chapter-url=https://www.researchgate.net/publication/289992641 |access-date=1 July 2019 |chapter=Game Description Language Compiler Construction}}

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.{{cite journal |last1=de Jonge |first1=Dave |last2=Trescak |first2=Tomas |last3=Sierra |first3=Carles |last4=Simoff |first4=Simeon |last5=López de Mántaras |first5=Ramon |date=2017 |title=Using Game Description Language for mediated dispute resolution |journal=AI & Society |volume=2017 |issue=4 |publisher=Springer |pages=767–784 |doi=10.1007/s00146-017-0790-8 |s2cid=22738517 }}

• General Game Playing
• Artificial Intelligence

{{reflist}}

• [http://logic.stanford.edu/classes/cs227/2013/readings/gdl_spec.pdf Game Description Language Specification] {{Webarchive|url=https://web.archive.org/web/20130412032912/http://logic.stanford.edu/classes/cs227/2013/readings/gdl_spec.pdf |date=2013-04-12 }}
• [http://www.cse.unsw.edu.au/~mit/Papers/AAAI10a.pdf Refereed paper introducing GDL-II]

Category:Game artificial intelligence

Category:Logic programming languages