Game Description Language

Game Description Language (GDL), an innovation in the field of artificial intelligence[citation needed], represents a significant step forward in the quest to create versatile game-playing AI agents. Designed by Michael Genesereth, GDL is a specialized logic programming language that finds its home within the ambitious realm of the General Game Playing Project at Stanford University. This project aims to develop AI agents capable of playing a wide variety of games without the need for game-specific programming. At its core, GDL serves as a powerful tool for expressing the intricacies of game rules and dynamics in a form that is easily comprehensible to AI systems. It achieves this through a combination of logic-based constructs and declarative principles.

Here are key features and concepts associated with Game Description Language:

**Logic-Based Foundations:** GDL leverages formal logic to describe the rules of games. It allows for the precise representation of complex game mechanics, providing unambiguous instructions for gameplay. By using logical rules, GDL enables AI agents to understand and navigate the intricacies of a game's structure and dynamics.

**Game-Agnostic Flexibility:** A notable strength of GDL is its game-agnostic nature. It is not confined to any specific game or genre, making it a versatile language for defining the rules of an extensive range of games. This versatility is particularly valuable in the development of AI agents, as it empowers them to engage in various games without the need for individualized programming for each one.

**Declarative Clarity:** GDL adheres to a declarative paradigm. In other words, it focuses on defining the conditions that are either true or legal within the context of a game, rather than prescribing how to play the game. This clear distinction between rules and strategies is vital for AI agents. It enables them to reason logically about the game state and make informed, intelligent moves.

**Extensible Adaptability:** Game Description Language is an extensible framework. It can be expanded and customized to accommodate a wide array of game features. Whether a game involves chance elements, simultaneous actions, or other unique mechanics, GDL can be adapted to accurately represent these complexities.

In practice, GDL serves as a cornerstone for the 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.

## Contents

* 1 Purpose of GDL
* 2 Specification
* 2.1 Syntax
* 2.2 Keywords
* 2.3 Rules
* 2.3.1 Players
* 2.3.2 Initial state
* 2.3.3 Legal moves
* 2.3.4 Game state update
* 2.3.5 Termination
* 2.3.6 Goal states
* 3 Extensions
* 3.1 GDL-II
* 3.2 GDL-III
* 4 Other formalisms and languages for game representation
* 5 Applications
* 6 See also
* 7 References
* 8 External links

## 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 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 numbers of players. However, GDL cannot describe games which 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:[3]

`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.[4]

## Other formalisms and languages for game representation

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 representation of some subclasses of games or representations adjusted to the needs of interdisciplinary research are summarized as the following table.[5] Some of these alternative representations also encode time related aspects:

Name  | Year  | Means  | Type of games | Time

|
|
|
|

1973  | functions  | subset of n-person games, simultaneous moves  | No
1994  | matrices  | 2-person games of imperfect information  | No
Timed games[6][7] | 1994  | functions  | 2-person games  | Yes
Gala[8] | 1997  | logic | n-person games of imperfect information  | No
Graphical games[9][10] | 2001  | graphs, functions  | n-person games, simultaneous moves  | No
Local effect games[11] | 2003  | functions  | subset of n-person games, simultaneous moves  | No
Game Petri-nets[12] | 2006  | Petri net | deterministic n-person games, simultaneous moves  | No
Continuous games[13] | 2007  | functions  | subset of 2-person games of imperfect information  | Yes
PNSI[14][15] | 2008  | Petri net | n-person games of imperfect information  | Yes
Action graph games[16] | 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".[17]

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

## See also

* General Game Playing
* Artificial Intelligence

## References

1. ↑ Biever, Celeste (2006-07-29). "Producing the ultimate game-playing bots - tech - 29 July 2006 - New Scientist Tech". http://www.newscientisttech.com:80/channel/tech/mg19125626.100.html.
2. ↑ Love, N; Genesereth, M; Hinrichs, T (2006). "General game playing: game description language specification. Tech. Rep. LG-2006-01". Stanford University, Stanford. http://logic.stanford.edu/reports/LG-2006-01.pdf.
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). http://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/view/1727. Retrieved 1 July 2019.
4. ↑ Thielscher, Michael (2017). "GDL-III: A Description Language for Epistemic General Game Playing". Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence. IJCAI. ISBN 978-0-9992411-0-3. https://www.ijcai.org/proceedings/2017/0177.pdf. 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. ↑ 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.
7. ↑ 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. doi:10.1109/5.871303.
8. ↑ Koller, Daphne; Pfeffer, Avi (1997). "Representations and solutions for game-theoretic problems". Artificial Intelligence 94 (1–2): 167–215. doi:10.1016/S0004-3702(97)00023-4. http://www.dca.fee.unicamp.br/~gomide/courses/EA044/Artigos/RepresentationsSolutionsGameTheoreticProblemsKoller1997.pdf.
9. ↑ Michael, Michael Kearns; Littman, Michael L. (2001). "Graphical Models for Game Theory". In UAI: 253–260.
10. ↑ Kearns, Michael; Littman, Michael L.; Singh, Satinder (7 March 2011). "Graphical Models for Game Theory". arXiv:1301.2281 [cs.GT].
11. ↑ Leyton-Brown, Kevin; Tennenholtz, Moshe (2003). "Local-effect games". IJCAI'03: Proceedings of the 18th International Joint Conference on Artificial Intelligence: 772–777. https://dl.acm.org/doi/10.5555/1630659.1630771.
12. ↑ Clempner, Julio (2006). "Modeling shortest path games with Petri nets: a Lyapunov based theory" (in EN). International Journal of Applied Mathematics and Computer Science 16 (3): 387–397. ISSN 1641-876X. http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-amcv16i3p387bwm.
13. ↑ Sannikov, Yuliy (September 2007). "Games with Imperfectly Observable Actions in Continuous Time". Econometrica 75 (5): 1285–1329. doi:10.1111/j.1468-0262.2007.00795.x. http://www.dklevine.com/archive/sannikov_games.pdf.
14. ↑ 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.
15. ↑ Tagiew, Rustam (2009). "On Multi-agent Petri Net Models for Computing Extensive Finite Games" (in en). New Challenges in Computational Collective Intelligence. Studies in Computational Intelligence. 244. Springer. pp. 243–254. doi:10.1007/978-3-642-03958-4_21. ISBN 978-3-642-03957-7.
16. ↑ Bhat, Navin; Leyton-Brown, Kevin (11 July 2012). "Computing Nash Equilibria of Action-Graph Games". arXiv:1207.4128 [cs.GT].
17. ↑ 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. https://www.researchgate.net/publication/289992641. Retrieved 1 July 2019.
18. ↑ 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 (Springer) 2017 (4): 767–784. doi:10.1007/s00146-017-0790-8.

## External links

* Game Description Language Specification
* Refereed paper introducing GDL-II

* v
* t
* e

Topics in game theory

Definitions|

* Cooperative game
* Determinacy
* Escalation of commitment
* Extensive-form game
* First-player and second-player win
* Game complexity
* Graphical game
* Hierarchy of beliefs
* Information set
* Normal-form game
* Preference
* Sequential game
* Simultaneous game
* Simultaneous action selection
* Solved game
* Succinct game

Equilibrium
concepts|

* Nash equilibrium
* Subgame perfection
* Mertens-stable equilibrium
* Bayesian Nash equilibrium
* Perfect Bayesian equilibrium
* Trembling hand
* Proper equilibrium
* Epsilon-equilibrium
* Correlated equilibrium
* Sequential equilibrium
* Quasi-perfect equilibrium
* Evolutionarily stable strategy
* Risk dominance
* Core
* Shapley value
* Pareto efficiency
* Gibbs equilibrium
* Quantal response equilibrium
* Self-confirming equilibrium
* Strong Nash equilibrium
* Markov perfect equilibrium

Strategies|

* Dominant strategies
* Pure strategy
* Mixed strategy
* Strategy-stealing argument
* Tit for tat
* Grim trigger
* Collusion
* Backward induction
* Forward induction
* Markov strategy

Classes
of games|

* Symmetric game
* Perfect information
* Repeated game
* Signaling game
* Screening game
* Cheap talk
* Zero-sum game
* Mechanism design
* Bargaining problem
* Stochastic game
* n-player game
* Large Poisson game
* Nontransitive game
* Global game
* Strictly determined game
* Potential game

Games|

* Go
* Chess
* Infinite chess
* Checkers
* Tic-tac-toe
* Prisoner's dilemma
* Optional prisoner's dilemma
* Traveler's dilemma
* Coordination game
* Chicken
* Centipede game
* Volunteer's dilemma
* Dollar auction
* Battle of the sexes
* Stag hunt
* Matching pennies
* Ultimatum game
* Rock paper scissors
* Pirate game
* Dictator game
* Public goods game
* Blotto game
* War of attrition
* El Farol Bar problem
* Fair division
* Fair cake-cutting
* Cournot game
* Deadlock
* Diner's dilemma
* Guess 2/3 of the average
* Kuhn poker
* Nash bargaining game
* Prisoners and hats puzzle
* Trust game
* Princess and Monster game
* Rendezvous problem

Theorems|

* Arrow's impossibility theorem
* Aumann's agreement theorem
* Folk theorem
* Minimax theorem
* Nash's theorem
* Purification theorem
* Revelation principle
* Zermelo's theorem

Key
figures|

* Albert W. Tucker
* Amos Tversky
* Ariel Rubinstein
* Claude Shannon
* Daniel Kahneman
* David K. Levine
* David M. Kreps
* Donald B. Gillies
* Drew Fudenberg
* Eric Maskin
* Harold W. Kuhn
* Herbert Simon
* Hervé Moulin
* Jean Tirole
* Jean-François Mertens
* Jennifer Tour Chayes
* John Harsanyi
* John Maynard Smith
* Antoine Augustin Cournot
* John Nash
* John von Neumann
* Kenneth Arrow
* Kenneth Binmore
* Leonid Hurwicz
* Lloyd Shapley
* Melvin Dresher
* Merrill M. Flood
* Olga Bondareva
* Oskar Morgenstern
* Paul Milgrom
* Peyton Young
* Reinhard Selten
* Robert Axelrod
* Robert Aumann
* Robert B. Wilson
* Roger Myerson
* Samuel Bowles
* Suzanne Scotchmer
* Thomas Schelling
* William Vickrey

See also|

* All-pay auction
* Alpha–beta pruning
* Bertrand paradox
* Bounded rationality
* Combinatorial game theory
* Confrontation analysis
* Coopetition
* First-move advantage in chess
* Game mechanics
* Glossary of game theory
* List of game theorists
* List of games in game theory
* No-win situation
* Solving chess
* Topological game
* Tragedy of the commons
* Tyranny of small decisions

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Game Description Language. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Game_Description_Language&oldid=269085"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template