Game Description Language, or GDL, is a logic programming languagedesigned 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.
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.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.
GDL is a variant of Datalog, and the syntax is largely the same. It is usually given in prefix notation. Variables begin with "
The following is the list of keywords in GDL, along with brief descriptions of their functions:
does(?r,?m)means that player (or role)
?min the current game state.
goal(?r,?n)is used to define goal value
?n(usually a natural number between 0 and 100) for role
?rin the current state.
?mis a legal move for role
?rin the current state.
A game description in GDL provides complete rules for each of the following elements of a game.
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)
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:
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)))
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)
The goal values for each player in a terminal state. An example is:
(<= (goalxplayer100)(linex))(<= (goaloplayer0)(linex))
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:
sees(?r,?p)means that role
?pin the next game state.
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)))
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.
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.Some of these alternative representations also encode time related aspects:
|Name||Year||Means||Type of games||Time|
|Congestion game||1973||functions||subset of n-person games, simultaneous moves||No|
|Sequential form||1994||matrices||2-person games of imperfect information||No|
|Timed games||1994||functions||2-person games||Yes|
|Gala||1997||logic||n-person games of imperfect information||No|
|Local effect games||2003||functions||subset of n-person games, simultaneous moves||No|
|Game Petri-nets||2006||Petri net||deterministic n-person games, simultaneous moves||No|
|Continuous games||2007||functions||subset of 2-person games of imperfect information||Yes|
|PNSI||2008||Petri net||n-person games of imperfect information||Yes|
|Action graph games||2012||graphs, functions||n-person games, simultaneous moves||No|
|Graphical games||2015||graphs, functions||n-person games, simultaneous moves||No|
This section needs expansion. You can help by adding to it.(July 2019)
A 2016 paper "describes a multilevel algorithm compiling a general game description in GDL into an optimized reasoner in a low level language".
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.
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 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:
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.
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.
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 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.
|volume=has extra text (help)