The official Game Description Language Specification is available here. An informal discussion of Game Description Language appears below. Readers looking for rigor should consult the spec.

An Informal Overview of Game Description Language:

Game Description Language (GDL) is a formal language for defining discrete games of complete information.

In its most abstract form, we can think of a game as a state machine with the following components:

• S - a set of game "states"
• I₁, ..., I_n - n sets of "actions", one set for each player
• a₁, ..., a_n - where each a_i ⊆ I_i x S
• n - an update function mapping I₁ x ... x I_n x S → S
• s₁ - the initial game state, a member of S
• g₁, ..., g_n - where each g_i ⊆ S
• t - a unary relation on S, the "terminal" states of the game

This definition of games is similar to the traditional definition in game theory with a couple of exceptions. In this version, a game is a graph rather than a tree. This makes it possible to describe games more compactly, and it makes it easier for players to play games efficiently.

Since all of the games that we are considering are finite, it is possible, in principle, to describe such games in the form of lists (of states and actions) and tables (to express legality, goals, temination, and update). Unfortunately, such explicit representations are not practical in all cases. Even though the numbers of states and actions are finite, they can be extremely large; and the tables relating them can be larger still. For example, in chess, there are thousands of possible moves and approximately 10³⁰ states.

All is not lost. In the vast majority of games, states and actions have composite structure that allows us to define a large number of states and actions in terms of a smaller number of more fundamental entities. In chess, for example, states are not monolithic; they can be conceptualized in terms of pieces, squares, rows and columns and diagonals, and so forth.

By exploiting this structure, it is possible to encode games in a form that is more compact than direct representation. GDL supports this by relying on a conceptualization of game states as databases and by relying on logic to define the notions of legality and so forth. These two featuers are described in the following sections.

Databases:

In what follows, we look at a model for games in which states take the form of databases. Each game has an associated database schema, and each state of the game is an instance of this schema. Different states correspond to different instances, and changes in the world correspond to movement among these database instances.

A database schema is a set of objects, a set of tables, and a function that assigns a natural number to each table (its arity, i.e. the number of objects involved in any instance of the relationship). The Herbrand base corresponding to a database schema is a set of expressions of the form r(a1,...,an), where r is a relationship of arity n and a1,...,an are objects. An instance of a database schema is a subset of the corresponding Herbrand base.

As an example of this conceptualization of games, let us look at the game of Tic-Tac-Toe. The game environment consiste of a 3 x 3 grid of cells wehere each cell is either blank or conatins an X or an O. In order to describe game states, we assume a ternary relation cell that relates a row number {1, 2, 3}, a column number {1, 2, 3}, and a content designator {X, O, B}. Although it is not strictly necessary, we include an auxiliary relation control that designates the player with the authority to make a mark. The following data encode the game state where X has marked the upper left corner and O has marked the center of the grid.

• cell(1,1,X)
• cell(1,2,B)
• cell(1,3,B)
• cell(2,1,B)
• cell(2,2,B)
• cell(2,3,B)
• cell(3,1,B)
• cell(3,2,B)
• cell(3,3,B)
• control(white)

Note that the control relation is not strictly necessary, as it can be computed from the other data. However, it is convenient to have this relation and so we have here chosen to make it part of the state description.

Logic

By itself, the switch from monolithic states to databases does not help. We must still encode tables that are as large as in the state model. However, with the database model, it is possible to describe these tables in a more compact form by encoding the notions of legality, goalhood, termination, and update as sentences in logic rather than as explicit tables.

In our GGP framework, we use a variant of first order logic enlarged with distinguished names for the key components of our conceptualization of games.

• Object variables: X, Y, Z
• Object constants: a, b, c
• Function constants: f, g, h
• Relation constants: p, q, r
• Logical operators: ~, |, &, =>, <=, <=>
• Quantifiers: A, E

• Terms: X,Y,Z,a,b,c,f(a),g(b,Z)
• Relational sentences: p(a,b)
• Logical sentences: r(a,c) <= r(a,b) & r(b,c)
• Quantified sentences: p(a,S) <= Ex.q(x,S)

GDL uses an indexical approach to defining games. A GDL game description takes the form of a set of logical sentences that must be true in every state of the game. The distinguished vocabulary words that support this are described below.

• role(a) means that a is a role / player in the game.
• init(p) means that the datum p is true in the initial state.
• true(p) means that the datum p is true in the current state.
• does(r,a) means that player r performs action a in the current state.
• next(p) means that the datum p is true in the next state.
• legal(r,a) means it is legal for r to play a in the current state.
• goal(r) means that player r's goal is achieved in the current state.
• terminal means that the current state is a terminal state.

GDL is an open language in that this vocabulary can be extended; however, the significance of these basic vocabulary items is fixed for all games.

Example:

As an example of GDL, here is a full accounting of Tic Tac Toe, beginning with the roles of the game. Please note that for ease of readability, this example is given in infix KIF, while the games currently available in the arcade are in prefix KIF.

• role(x)
• role(o)

Next, we characterize the initial state. In this case, all cells are blank.

• init(cell(1,1,b))
• init(cell(1,2,b))
• init(cell(1,3,b))
• init(cell(2,1,b))
• init(cell(2,2,b))
• init(cell(2,3,b))
• init(cell(3,1,b))
• init(cell(3,2,b))
• init(cell(3,3,b))
• init(control(x))

Next, we define legality. A player may mark a cell if that cell is blank and he has control. Otherwise, the only legal action is noop.

• legal(P,mark(X,Y)) <= true(cell(X,Y,b)) & true(control(P))
• legal(x,noop) <= true(control(o))
• legal(o,noop) <= true(control(x))

Here are the update rules for the game. A cell is marked with an x or an o if the appropriate player marks that cell. If a cell contains a mark, it retains that mark on the subsequent state. If a cell is blank and is not marked, then it remains blank. Finally, control alternates on each play.

• next(cell(M,N,P)) <= does(P,mark(M,N))
• next(cell(M,N,P)) <= true(cell(M,N,P)) & distinct(P,b)
• next(cell(M,N,b)) <= does(W,mark(J,K)) & true(cell(M,N,b)) & (distinct(M,J) | distinct(N,K))
• next(control(x)) <= true(control(o))
• next(control(o)) <= true(control(x))

A state is a win for x if there is a line of x's. It is a win for o if there is a line of o's. The line relation is defined below.

• goal(x) <= line(x)
• goal(o) <= line(o)

A line is a row of marks of the same type or a column or a diagonal. A row of marks mean thats there three marks all with the same first coordinate. The column and diagonal relations are defined analogously.

• line(P) <= row(M,P)
• line(P) <= column(M,P)
• line(P) <= diagonal(P)

• row(M,P) <= true(cell(M,1,P)) & true(cell(M,2,P)) & true(cell(M,3,P))
• column(M,P) <= true(cell(1,N,P)) & true(cell(2,N,P)) & true(cell(3,N,P))
• diagonal(P) <= true(cell(1,1,P)) & true(cell(2,2,P)) & true(cell(3,3,P))
• diagonal(P) <= true(cell(1,3,P)) & true(cell(2,2,P)) & true(cell(3,1,P))

A game terminates whenever either player has a line of marks of the appropriate type.

• terminal <= line(x)
• terminal <= line(o)

Note that, under the full information assumption, any of these relations can be assumed to be false if it is not provably true. Thus, we have complete definitions for the relations legal, next, goal, terminal in terms of true and does. The true relation starts out identical to init and on each step is changed to correspond to the extension of the next relation on that step.

Although GDL is designed for use in defining complete information games, it can be extended to partial information games relatively easily. Unfortunately, the resulting descriptions are more verbose and more expensive to process. This extension to GDL is the subject of a separate document.