Game Description Language

Last updated

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 artificial intelligence (AI) systems through a combination of logic-based constructs and declarative principles.

Contents

In practice, GDL is often used for General Game Playing competitions and research endeavours. 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 rules. The use of GDL allows for the development of highly adaptable AI agents, capable of competing in diverse scenarios.

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. [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.

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 ?. [2]

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

Rules

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.

Players

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

Initial state

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(cell11blank))...(init(cell33blank))(init(controlxplayer))

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?nblank))(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. For example:

(<=(next(cell?m?nx))(doesxplayer(mark?m?n)))(<=(next(cell?m?no))(doesoplayer(mark?m?n)))

Termination

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(linex))(<=terminal(lineo))(<=terminalnotboardopen)

Goal states

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

(<=(goalxplayer100)(linex))(<=(goaloplayer0)(linex))

Extensions

GDL-II

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)(doesrandom(deal_face_down?player?card)))(<=(sees?r?card)(role?r)(doesrandom(deal_river?card)))

GDL-III

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]

Other methods of game representation

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:

NameYearFormalized with Game type Time aspect
Congestion game [6] 1973 functions subset of n-player games, simultaneous movesNo
Sequential form [7] 1994 matrices two-player games of imperfect information No
Timed games [8] [9] 1994functionstwo-player gamesYes
Gala [10] 1997 logic n-player games of imperfect informationNo
Graphical games [11] [12] 2001 graphs, functionsn-player games, simultaneous movesNo
Local effect games [13] 2003functionssubset of n-player games, simultaneous movesNo
Game Petri nets [14] 2006 Petri nets deterministic n-player games, simultaneous movesNo
Continuous games [15] 2007functionssubset of two-player games of imperfect informationYes
Petri net strategic interactions [16] [17] 2008Petri netsn-player games of imperfect informationYes
Action graph games [18] 2012graphs, functionsn-player games, simultaneous movesNo

Applications

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]

See also

References

  1. Biever, Celeste (2006-07-29). "Producing the ultimate game-playing bots - tech - 29 July 2006 - New Scientist Tech". Archived from the original on 11 August 2007.
  2. Love, N; Genesereth, M; Hinrichs, T (2006). "General game playing: game description language specification. Tech. Rep. LG-2006-01" (PDF). Stanford University. Stanford University, Stanford. Retrieved 1 July 2019.[ permanent dead link ]
  3. Thielscher, M (2010). Fox, M; Poole, D (eds.). "A general game description language for incomplete information games". Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2010. Atlanta: AAAI Press. Retrieved 1 July 2019.
  4. Thielscher, Michael (2017). "GDL-III: A Description Language for Epistemic General Game Playing" (PDF). Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. IJCAI. ISBN   978-0-9992411-0-3 . Retrieved 1 July 2019.
  5. Tagiew, Rustam (3 May 2011). "If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction". arXiv: 1105.0558 [cs.GT].
  6. Rosenthal, Robert W. (December 1973). "A class of games possessing pure-strategy Nash equilibria". International Journal of Game Theory. 2 (1): 65–67. doi:10.1007/BF01737559. S2CID   121904640.
  7. Koller, Daphne; Megiddo, Nimrod; von Stengel, Bernhard (1994). "Fast algorithms for finding randomized strategies in game trees". Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94. pp. 750–759. doi:10.1145/195058.195451. ISBN   0-89791-663-8. S2CID   1893272.
  8. Alur, Rajeev; Dill, David L. (April 1994). "A theory of timed automata". Theoretical Computer Science. 126 (2): 183–235. doi: 10.1016/0304-3975(94)90010-8 .
  9. Tomlin, C.J.; Lygeros, J.; Shankar Sastry, S. (July 2000). "A game theoretic approach to controller design for hybrid systems". Proceedings of the IEEE. 88 (7): 949–970. Bibcode:2000IEEEP..88..949T. CiteSeerX   10.1.1.129.8347 . doi:10.1109/5.871303. S2CID   1844682.
  10. Koller, Daphne; Pfeffer, Avi (1997). "Representations and solutions for game-theoretic problems" (PDF). Artificial Intelligence. 94 (1–2): 167–215. doi: 10.1016/S0004-3702(97)00023-4 .
  11. Michael, Michael Kearns; Littman, Michael L. (2001). "Graphical Models for Game Theory". In UAI: 253–260. CiteSeerX   10.1.1.22.5705 .
  12. Kearns, Michael; Littman, Michael L.; Singh, Satinder (7 March 2011). "Graphical Models for Game Theory". arXiv: 1301.2281 [cs.GT].
  13. Leyton-Brown, Kevin; Tennenholtz, Moshe (2003). "Local-effect games". IJCAI'03: Proceedings of the 18th International Joint Conference on Artificial Intelligence: 772–777.
  14. Clempner, Julio (2006). "Modeling shortest path games with Petri nets: a Lyapunov based theory". International Journal of Applied Mathematics and Computer Science. 16 (3): 387–397. ISSN   1641-876X.
  15. Sannikov, Yuliy (September 2007). "Games with Imperfectly Observable Actions in Continuous Time" (PDF). Econometrica. 75 (5): 1285–1329. doi:10.1111/j.1468-0262.2007.00795.x.
  16. Tagiew, Rustam (December 2008). "Multi-Agent Petri-Games". 2008 International Conference on Computational Intelligence for Modelling Control & Automation. pp. 130–135. doi:10.1109/CIMCA.2008.15. ISBN   978-0-7695-3514-2. S2CID   16679934.
  17. Tagiew, Rustam (2009). "On Multi-agent Petri Net Models for Computing Extensive Finite Games". New Challenges in Computational Collective Intelligence. Studies in Computational Intelligence. Vol. 244. Springer. pp. 243–254. doi:10.1007/978-3-642-03958-4_21. ISBN   978-3-642-03957-7.
  18. Bhat, Navin; Leyton-Brown, Kevin (11 July 2012). "Computing Nash Equilibria of Action-Graph Games". arXiv: 1207.4128 [cs.GT].
  19. Kowalski, Jakub; Szykuła, Marek (2013). "Game Description Language Compiler Construction". AI 2013: Advances in Artificial Intelligence: 26th Australasian Joint Conference, Dunedin, New Zealand, December 1-6, 2013. Proceedings. pp. 234–245. Retrieved 1 July 2019.
  20. de Jonge, Dave; Trescak, Tomas; Sierra, Carles; Simoff, Simeon; López de Mántaras, Ramon (2017). "Using Game Description Language for mediated dispute resolution". AI & Society. 2017 (4). Springer: 767–784. doi:10.1007/s00146-017-0790-8. S2CID   22738517.