Game Description Language

Last updated

Game Description Language, or GDL, is a logic programming language [1] 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. [2]

Contents

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. [3] 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 "?". [4]

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

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?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. An example is:

(<= (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 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:

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

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: [5]

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)(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 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. [6]

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. [7] Some of these alternative representations also encode time related aspects:

NameYearMeans Type of games Time
Congestion game [8] 1973functionssubset of n-person games, simultaneous movesNo
Sequential form [9] 1994matrices2-person games of imperfect informationNo
Timed games [10] [11] 1994functions2-person gamesYes
Gala [12] 1997 logic n-person games of imperfect informationNo
Local effect games [13] 2003functionssubset of n-person games, simultaneous movesNo
Game Petri-nets [14] 2006 Petri net deterministic n-person games, simultaneous movesNo
Continuous games [15] 2007functionssubset of 2-person games of imperfect informationYes
PNSI [16] [17] 2008 Petri net n-person games of imperfect informationYes
Action graph games [18] 2012graphs, functionsn-person games, simultaneous movesNo
Graphical games [19] 2015graphs, functionsn-person 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". [20]

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

See also

Related Research Articles

Cyc

Cyc is a long-term artificial intelligence project that aims to assemble a comprehensive ontology and knowledge base that spans the basic concepts and rules about how the world works. Hoping to capture common sense knowledge, Cyc focuses on implicit knowledge that other AI platforms may take for granted. This is contrasted with facts one might find somewhere on the internet or retrieve via a search engine or Wikipedia. Cyc enables semantic reasoners to perform human-like reasoning and be less "brittle" when confronted with novel situations.

In artificial intelligence, the frame problem describes an issue with using first-order logic to express facts about a robot in the world. Representing the state of a robot with first-order logic requires the use of many axioms that simply imply that things in the environment do not change arbitrarily. For example, Hayes describes a "block world" with rules about stacking blocks together. The frame problem is the problem of finding adequate collections of axioms for a viable description of a robot environment.

Game theory The study of mathematical models of strategic interaction between rational decision-makers

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. In the 21st century, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

Logic programming is a programming paradigm which is largely based on formal logic. Any program written in a logic programming language is a set of sentences in logical form, expressing facts and rules about some problem domain. Major logic programming language families include Prolog, answer set programming (ASP) and Datalog. In all of these languages, rules are written in the form of clauses:

Semantic network

A semantic network, or frame network is a knowledge base that represents semantic relations between concepts in a network. This is often used as a form of knowledge representation. It is a directed or undirected graph consisting of vertices, which represent concepts, and edges, which represent semantic relations between concepts, mapping or connecting semantic fields. A semantic network may be instantiated as, for example, a graph database or a concept map.

Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.

Computational learning theory Theory of machine learning

In computer science, computational learning theory is a subfield of artificial intelligence devoted to studying the design and analysis of machine learning algorithms.

Prototype theory is a theory of categorization in cognitive science, particularly in psychology and cognitive linguistics, in which there is a graded degree of belonging to a conceptual category, and some members are more central than others. It emerged in 1971 with the work of psychologist Eleanor Rosch, and it has been described as a "Copernican revolution" in the theory of categorization for its departure from the traditional Aristotelian categories. It has been criticized by those that still endorse the traditional theory of categories, like linguist Eugenio Coseriu and other proponents of the structural semantics paradigm.

Legal informatics is an area within information science.

Circumscription is a non-monotonic logic created by John McCarthy to formalize the common sense assumption that things are as expected unless otherwise specified. Circumscription was later used by McCarthy in an attempt to solve the frame problem. To implement circumscription in its initial formulation, McCarthy augmented first-order logic to allow the minimization of the extension of some predicates, where the extension of a predicate is the set of tuples of values the predicate is true on. This minimization is similar to the closed-world assumption that what is not known to be true is false.

Keith Leonard Clark is an Emeritus Professor in the Department of Computing at Imperial College London, England.

General game playing (GGP) is the design of artificial intelligence programs to be able to play more than one game successfully. For many games like chess, computers are programmed to play these games using a specially designed algorithm, which cannot be transferred to another context. For instance, a chess-playing computer program cannot play checkers. General game playing is considered as a necessary milestone on the way to Artificial General Intelligence.

Frames are an artificial intelligence data structure used to divide knowledge into substructures by representing "stereotyped situations". They were proposed by Marvin Minsky in his 1974 article "A Framework for Representing Knowledge". Frames are the primary data structure used in artificial intelligence frame language; they are stored as ontologies of sets.

Abductive logic programming (ALP) is a high-level knowledge-representation framework that can be used to solve problems declaratively based on abductive reasoning. It extends normal logic programming by allowing some predicates to be incompletely defined, declared as abducible predicates. Problem solving is effected by deriving hypotheses on these abducible predicates as solutions of problems to be solved. These problems can be either observations that need to be explained or goals to be achieved. It can be used to solve problems in diagnosis, planning, natural language and machine learning. It has also been used to interpret negation as failure as a form of abductive reasoning.

Computational humor is a branch of computational linguistics and artificial intelligence which uses computers in humor research. It is a relatively new area, with the first dedicated conference organized in 1996.

Conceptualization (information science)

In information science a conceptualization is an abstract simplified view of some selected part of the world, containing the objects, concepts, and other entities that are presumed of interest for some particular purpose and the relationships between them. An explicit specification of a conceptualization is an ontology, and it may occur that a conceptualization can be realized by several distinct ontologies. An ontological commitment in describing ontological comparisons is taken to refer to that subset of elements of an ontology shared with all the others. "An ontology is language-dependent", its objects and interrelations described within the language it uses, while a conceptualization is always the same, more general, its concepts existing "independently of the language used to describe it". The relation between these terms is shown in the figure to the right.

Inductive programming (IP) is a special area of automatic programming, covering research from artificial intelligence and programming, which addresses learning of typically declarative and often recursive programs from incomplete specifications, such as input/output examples or constraints.

Action model learning

Action model learning is an area of machine learning concerned with creation and modification of software agent's knowledge about effects and preconditions of the actions that can be executed within its environment. This knowledge is usually represented in logic-based action description language and used as the input for automated planners.

This glossary of artificial intelligence is a list of definitions of terms and concepts relevant to the study of artificial intelligence, its sub-disciplines, and related fields. Related glossaries include Glossary of computer science, Glossary of robotics, and Glossary of machine vision.

Michael Genesereth is a logician and computer scientist, who is most known for his work on computational logic and applications of that work in enterprise management, computational law, and general game playing. Genesereth is professor in the Computer Science Department at Stanford University and a professor by courtesy in the Stanford Law School. His 1987 textbook on Logical Foundations of Artificial Intelligence remains one of the key references on Symbolic artificial intelligence. He is the author of the influential Game Description Language (GDL) and Knowledge Interchange Format (KIF), the latter of which led to the ISO Common Logic standard.

References

  1. "Game Definition Language". games.stanford.edu.
  2. Tagiew, Rustam (2011). Averkin, Alexey N.; Ignatov, Dmitry I.; Mitra, Sushmita; Poelmans, Jonas (eds.). "Beyond Analytical Modeling, Gathering Data to Predict Real Agents' Strategic Interaction" [Soft Computing Applications and Knowledge Discovery](PDF). CEUR Workshop Proceedings. Moscow, Russia. Vol-758: 113--124.|volume= has extra text (help)
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. Tagiew, Rustam (3 May 2011). "If more than Analytical Modeling is Needed to Predict Real Agents' Strategic Interaction". arXiv: 1105.0558 [cs.GT].
  8. 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.
  9. Koller, Daphne; Megiddo, Nimrod; von Stengel, Bernhard (1994). "Fast algorithms for finding randomized strategies in game trees". STOC '94: Proceedings of the Twenty-sixth Annual ACM Symposium on Theory of Computing: 750–759. doi:10.1145/195058.195451. ISBN   0-89791-663-8. S2CID   1893272.
  10. 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.
  11. 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. S2CID   1844682.
  12. 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.
  13. Leyton-Brown, Kevin; Tennenholtz, Moshe (2003). "Local-effect games". IJCAI'03: Proceedings of the 18th International Joint Conference on Artificial Intelligence.
  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: 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. Springer. 244: 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. Kearns, Michael; Littman, Michael L.; Singh, Satinder (7 March 2015). "Graphical Models for Game Theory". arXiv: 1301.2281 [cs.GT].
  20. 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.
  21. 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.