Game Description Language

Last updated

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.

Contents

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.

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

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

NameYearMeans Type of games Time
Congestion game [6] 1973functionssubset of n-person games, simultaneous movesNo
Sequential form [7] 1994matrices2-person games of imperfect informationNo
Timed games [8] [9] 1994functions2-person gamesYes
Gala [10] 1997 logic n-person games of imperfect informationNo
Graphical games [11] [12] 2001graphs, functionsn-person games, simultaneous movesNo
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

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 efficiently to do so. [20]

See also

Related Research Articles

<span class="mw-page-title-main">Artificial intelligence</span> Intelligence of machines or software

Artificial intelligence (AI) is the intelligence of machines or software, as opposed to the intelligence of humans or animals. It may also refer to the corresponding field of study, which develops and studies intelligent machines, or to the intelligent machines themselves.

<span class="mw-page-title-main">Cyc</span> Artificial intelligence project

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, with implications for cognitive science, 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 traditional 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. In a first-order logic system, additional axioms are required to make inferences about the environment. The frame problem is the problem of finding adequate collections of axioms for a viable description of a robot environment.

Game theory is the study of mathematical models of strategic interactions among rational agents. It has applications in many fields of social science, used extensively in economics as well as in logic, systems science and computer science. Traditional game theory addressed two-person zero-sum games, in which a participant's gains or losses are exactly balanced by the losses and gains of the other participant. In the 21st century, game theory applies to a wider range of behavioral relations, and it is now an umbrella term for the science of logical decision making in humans, animals, as well as computers.

Knowledge representation and reasoning is the field of artificial intelligence (AI) dedicated to representing information about the world in a form that a computer system can use to solve complex tasks such as diagnosing a medical condition or having a dialog in a natural language. Knowledge representation incorporates findings from psychology about how humans solve problems and represent knowledge in order to design formalisms that will make complex systems easier to design and build. Knowledge representation and reasoning also incorporates findings from logic to automate various kinds of reasoning, such as the application of rules or the relations of sets and subsets.

Logic programming is a programming, database and knowledge-representation and reasoning paradigm which is based on formal logic. A program, database or knowledge base 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:

Prolog is a logic programming language associated with artificial intelligence and computational linguistics.

Inferences are steps in reasoning, moving from premises to logical consequences; etymologically, the word infer means to "carry forward". Inference is theoretically traditionally divided into deduction and induction, a distinction that in Europe dates at least to Aristotle. Deduction is inference deriving logical conclusions from premises known or assumed to be true, with the laws of valid inference being studied in logic. Induction is inference from particular evidence to a universal conclusion. A third type of inference is sometimes distinguished, notably by Charles Sanders Peirce, contradistinguishing abduction from induction.

Game semantics is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the existence of a winning strategy for a player, somewhat resembling Socratic dialogues or medieval theory of Obligationes.

<span class="mw-page-title-main">Logic in computer science</span> Academic discipline

Logic in computer science covers the overlap between the field of logic and that of computer science. The topic can essentially be divided into three main areas:

The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages. It was first developed by Drew McDermott and his colleagues in 1998 mainly to make the 1998/2000 International Planning Competition (IPC) possible, and then evolved with each competition. The standardization provided by PDDL has the benefit of making research more reusable and easily comparable, though at the cost of some expressive power, compared to domain-specific systems.

In video games, artificial intelligence (AI) is used to generate responsive, adaptive or intelligent behaviors primarily in non-playable characters (NPCs) similar to human-like intelligence. Artificial intelligence has been an integral part of video games since their inception in the 1950s. AI in video games is a distinct subfield and differs from academic AI. It serves to improve the game-player experience rather than machine learning or decision making. During the golden age of arcade video games the idea of AI opponents was largely popularized in the form of graduated difficulty levels, distinct movement patterns, and in-game events dependent on the player's input. Modern games often implement existing techniques such as pathfinding and decision trees to guide the actions of NPCs. AI is often used in mechanisms which are not immediately visible to the user, such as data mining and procedural-content generation.

Legal informatics is an area within information science.

<span class="mw-page-title-main">Outline of artificial intelligence</span> Overview of and topical guide to artificial intelligence

The following outline is provided as an overview of and topical guide to artificial intelligence:

<span class="mw-page-title-main">General game playing</span> Learning to play multiple games successfully

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.

<span class="mw-page-title-main">Stephen Muggleton</span> Artificial intelligence researcher

Stephen H. Muggleton FBCS, FIET, FAAAI, FECCAI, FSB, FREng is Professor of Machine Learning and Head of the Computational Bioinformatics Laboratory at Imperial College London.

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 languages; they are stored as ontologies of sets.

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.

<span class="mw-page-title-main">Glossary of artificial intelligence</span> List of definitions of terms and concepts commonly used in the study of artificial intelligence

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 an American 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. 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.
  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. 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. Springer. 2017 (4): 767–784. doi:10.1007/s00146-017-0790-8. S2CID   22738517.