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.

Contents

At its core, GDL is a tool for expressing the intricacies of game rules and dynamics in a form comprehensible to AI systems through a combination of logic-based constructs and declarative principles.

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 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: [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">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 rational 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.

Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the 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:

<span class="mw-page-title-main">Douglas Lenat</span> Computer scientist and AI pioneer

Douglas Bruce Lenat was an American computer scientist and researcher in artificial intelligence who was the founder and CEO of Cycorp, Inc. in Austin, Texas.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.
<span class="mw-page-title-main">Perfect information</span> Condition in economics and game theory

In economics, perfect information is a feature of perfect competition. With perfect information in a market, all consumers and producers have complete and instantaneous knowledge of all market prices, their own utility, and own cost functions.

<span class="mw-page-title-main">Symbolic artificial intelligence</span> Methods in artificial intelligence research

In artificial intelligence, symbolic artificial intelligence is the term for the collection of all methods in artificial intelligence research that are based on high-level symbolic (human-readable) representations of problems, logic and search. Symbolic AI used tools such as logic programming, production rules, semantic nets and frames, and it developed applications such as knowledge-based systems, symbolic mathematics, automated theorem provers, ontologies, the semantic web, and automated planning and scheduling systems. The Symbolic AI paradigm led to seminal ideas in search, symbolic programming languages, agents, multi-agent systems, the semantic web, and the strengths and limitations of formal knowledge and reasoning systems.

Interactive storytelling is a form of digital entertainment in which the storyline is not predetermined. The author creates the setting, characters, and situation which the narrative must address, but the user experiences a unique story based on their interactions with the story world. The architecture of an interactive storytelling program includes a drama manager, user model, and agent model to control, respectively, aspects of narrative production, player uniqueness, and character knowledge and behavior. Together, these systems generate characters that act "human," alter the world in real-time reactions to the player, and ensure that new narrative events unfold comprehensibly.

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.

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

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.

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.

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.

Explainable AI (XAI), often overlapping with Interpretable AI, or Explainable Machine Learning (XML), either refers to an artificial intelligence (AI) system over which it is possible for humans to retain intellectual oversight, or refers to the methods to achieve this. The main focus is usually on the reasoning behind the decisions or predictions made by the AI which are made more understandable and transparent. XAI counters the "black box" tendency of machine learning, where even the AI's designers cannot explain why it arrived at a specific decision.

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.

<span class="mw-page-title-main">Thomas Dean (computer scientist)</span> American computer scientist

Thomas L. Dean is an American computer scientist known for his work in robot planning, probabilistic graphical models, and computational neuroscience. He was one of the first to introduce ideas from operations research and control theory to artificial intelligence. In particular, he introduced the idea of the anytime algorithm and was the first to apply the factored Markov decision process to robotics. He has authored several influential textbooks on artificial intelligence.

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. 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.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.