1. Introduction

The most significant characteristic of General Game Playing is that players do not know the rules of games before those games begin. Game rules are communicated at runtime, and the players must be able to read and understand the descriptions they are given in order to play legally and effectively.

In general game playing, information about games is typically communicated to players in a formal language called Game Description Language, or GDL. This document is an introduction to GDL and the issues that arise in using it to describe games.

GDL is a logic programming language. It is similar to other logic programming languages, such as Prolog. The main differences are that (1) the semantics of GDL is purely declarative, (2) GDL has restrictions that assure that all questions of logical entailment are decidable, and (3) there are some reserved words (described below), which tailor the language to the task of defining games.

We start the document with a general definition of GDL. We then look at a sample game description, and we show how to simulate instances of the game using our game description. We talk about additional features of games that ensure that they are interesting. Finally, we summarize the prefix syntax for GDL used in most GGP competitions.

2. Game Description Language (GDL)

The basis for GDL is a conceptualization of games in terms of entities, actions, propositions, and players.

Entities include objects relevant to the state of a game, e.g. game pieces, ranks, files, board squares, and so forth. In writing GDL descriptions, we often use object constants to represent entities. For example, in Chess, we can refer to the white king as wk, and we can refer to the the fifth file on the board as e and the third rank as 3. In some cases, we use compound terms to refer to entities. For example, we can designate the square in the fifth file and third rank as square(e,3).

The set of entities in any game is assumed to be fixed for the duration of the game. This does not mean they are all in play at all times, only that they exist somewhere.

Actions are performed by players. As with entities, we use object constants or compound terms to refer to primitive actions. For example, in Chess, we might designate the primitive action of doing nothing as noop and we might designate the action of moving a piece from square e1 to square e2 with the term move(e1,e2).

Like primitive objects, the set of feasible actions in a game is also fixed for the duration of the game. That said, some actions may not be legal in every state. For example, advancing a bishop along a diagonal is a feasible action in Chess, but it is not legal for a player if so doing places the player's king is placed in check.

Propositions are conditions that are either true of false in each state of a game. In GDL, we designate propositions using object constants or compound terms. For example, in Chess, we might use the object compound term on(wk,e1) to designate the proposition that the white king is on square e1.

Note that, in each state, some of the game's propositions can be true while others can be false. As actions are performed, some propositions become true and others become false. For example, in Chess, we might have a proposition on(wk,e1) stating that the white king is on square e1, and we might have another proposition on(wk,e2)stating that it is on square e2. Obviously, both cannot be true at the same time. If the first proposition is true in a state and the white player advances his king, then that proposition becomes false and the second proposition becomes true.

Players are the active entities in games. On each time step, each player has a set of legal actions it can perform and executes some action in this set. In GDL, we usually use object constants to refer to players, though in rare cases we use compound terms.

In GDL, the meaning of some words in the language is fixed for all games (the game-independent vocabulary) while the meanings of all other words can change from one game to another (the game-specific vocabulary).

There are 101 game-independent object constants in GDL, viz. the base ten representations of the integers from 0 to 100, inclusive, i.e. 0, 1, 2, ... , 100. These are included for use as utility values for game states, with 0 being low and 100 being high. GDL has no game-independent function constants. However, there are ten game-independent relation constants, viz. the ones shown below.

role(a) means that a is a role in the game.

base(p) means that p is a base proposition in the game.

input(r,a) means that a is an action for role r.

init(p) means that the proposition p is true in the initial state.

true(p) means that the proposition 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 proposition p is true in the next state.

legal(r,a) means it is legal for role r to play action a in the current state.

goal(r,n) means that player the current state has utility n for player r.

terminal means that the current state is a terminal state.

In General Game Playing, the intent is to treat a GDL description as an open logic program with the following input and output relations. (1) A GDL game description must give complete definitions for role, input, base, init. (2) It must define legal and goal and terminal in terms of an input true relation. (3) It must define next in terms of input true and does relations. Since does and true are treated as inputs, there must not be any rules with either of these relations in the head.

3. Game Description Example

In our definition of Tic-Tac-Toe, states are characterized by the contents of the cells on the Tic-Tac-Toe board and control (whose turn it is to play). (It is true that control can be defined in terms of the contents of cells; but making control explicit costs little and simplifies the description.) In what follows, we use the 3-ary function constant cell together with a row m and a column n and a mark w to designate the proposition that the cell in row m and column n contains w where w is either an x or an o or a b (for blank). For example, the term cell(2,3,o) refers to the proposition asserting that there is an o in the cell in row 2 and column 3. We use the unary function constant control to map a player into the proposition that it is that player's turn to mark a cell. For example, the term control(x) refers to the proposition asserting that it is x's turn to mark a cell.

There only two types of actions a player can perform - he can mark a cell or he can do nothing (which is what a player does when it is not his turn to mark a cell). The binary function mark together with a row m and a column n designates the action of placing a mark in row m and column n. The mark placed there depends on who does the action. The object constant noop refers to the act of doing nothing.

We begin with an enumeration of roles. In this case, there are just two roles, here called x and o

    role(x)
    role(o)

We can characterize the feasible actions of the game as shown below.

    input(R,mark(M,N)) :- role(R) & index(M) & index(N)
    input(R,noop) :- role(R)

    index(1)
    index(2)
    index(3)

We can characterize the relevant propositions in similar fashion.

    base(cell(M,N,x)) :- index(M) & index(N)
    base(cell(M,N,o)) :- index(M) & index(N)
    base(cell(M,N,b)) :- index(M) & index(N)

    base(control(x))
    base(control(o))

Next, we characterize the initial state by writing all relevant propositions that are true in the initial state. In this case, all cells are blank; and the x player has control.

    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 it has control. Otherwise, the only legal action is noop.

    legal(W,mark(X,Y)) :-
      true(cell(X,Y,b)) &
      true(control(W))

    legal(x,noop) :-
      true(control(o))

    legal(o,noop) :-
      true(control(x))

Next, we look at 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 on that step, then it remains blank. Finally, control alternates on each play.

    next(cell(M,N,R)) :-
      does(R,mark(M,N)) &
      true(cell(M,N,b))

    next(cell(M,N,W)) :-
      true(cell(M,N,W)) &
      distinct(W,b)

    next(cell(M,N,b)) :-
      does(W,mark(J,K))
      true(cell(M,N,b)) &
      distinct(M,J)

    next(cell(M,N,b)) :-
      does(W,mark(J,K))
      true(cell(M,N,b)) &
      distinct(N,K)

    next(control(x)) :-
      true(control(o))

    next(control(o)) :-
      true(control(x))

Goals. The x player gets 100 points if there is a line of x marks and no line of o marks. If there are no lines of either sort, x gets 50 points. If there is a line of o marks and no line of x marks, then x gets 0 points. The rewards for o are analogous. The line relation is defined below.

    goal(x,100) :- line(x) & ~line(o)
    goal(x,50) :- ~line(x) & ~line(o)
    goal(x,0) :- ~line(x) & line(o)

    goal(o,100) :- ~line(x) & line(o)
    goal(o,50) :- ~line(x) & ~line(o)
    goal(o,0) :- line(x) & ~line(o)

Supporting concepts. 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(X) :- row(M,X)
    line(X) :- column(M,X)
    line(X) :- diagonal(X)

    row(M,X) :-
      true(cell(M,1,X)) &
      true(cell(M,2,X)) &
      true(cell(M,3,X))

    column(M,X) :-
      true(cell(1,N,X)) &
      true(cell(2,N,X)) &
      true(cell(3,N,X))

    diagonal(X) :-
      true(cell(1,1,X)) &
      true(cell(2,2,X)) &
      true(cell(3,3,X)) &

    diagonal(X) :-
      true(cell(1,3,X)) &
      true(cell(2,2,X)) &
      true(cell(3,1,X)) &

Termination. A game terminates whenever either player has a line of marks of the appropriate type or if the board is not open, i.e. there are no cells containing blanks.

    terminal :- line(W)
    terminal :- ~open

    open :- true(cell(M,N,b))

4. Game Simulation Example

As an exercise in logic programming and GDL, let's look at the outputs of the ruleset defined in the preceding section at various points during an instance of the game.

To start, we can use the ruleset to compute the roles of the game. This is simple in the case of Tic-Tac-Toe, as they are contained explicitly in the ruleset.

    role(x)
    role(o)

We can also compute the relevant actions of the game. The extension of the input relation in this case consists of the twenty sentences shown below.

    input(x,mark(1,1))
    input(x,mark(1,2))
    input(x,mark(1,3))
    input(x,mark(2,1))
    input(x,mark(2,2))
    input(x,mark(2,3))
    input(x,mark(3,1))
    input(x,mark(3,2))
    input(x,mark(3,3))
    input(x,noop)

    input(o,mark(1,1))
    input(o,mark(1,2))
    input(o,mark(1,3))
    input(o,mark(2,1))
    input(o,mark(2,2))
    input(o,mark(2,3))
    input(o,mark(3,1))
    input(o,mark(3,2))
    input(o,mark(3,3))
    input(o,noop)

Similarly, we can compute the possible base propositions. Remember that this gives a list of all such propositions; only a subset will be true in any particular state.

    base(cell(1,1,x))    base(cell(1,1,o))    base(cell(1,1,b))
    base(cell(1,2,x))    base(cell(1,2,o))    base(cell(1,2,b))
    base(cell(1,3,x))    base(cell(1,3,o))    base(cell(1,3,b))
    base(cell(2,1,x))    base(cell(2,1,o))    base(cell(2,1,b))
    base(cell(2,2,x))    base(cell(2,2,o))    base(cell(2,2,b))
    base(cell(2,3,x))    base(cell(2,3,o))    base(cell(2,3,b))
    base(cell(3,1,x))    base(cell(3,1,o))    base(cell(3,1,b))
    base(cell(3,2,x))    base(cell(3,2,o))    base(cell(3,2,b))
    base(cell(3,3,x))    base(cell(3,3,o))    base(cell(3,3,b))
    base(control(x))
    base(control(o))

The first step in playing or simulating a game is to compute the initial state. We can do this by computing the init relation. As with roles, this is easy in this case, since the initial conditions are explicitly listed in the program.

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

Once we have these conditions, we can turn them into a state description for the first step by asserting that each initial condition is true.

    true(cell(1,1,b))
    true(cell(1,2,b))
    true(cell(1,3,b))
    true(cell(2,1,b))
    true(cell(2,2,b))
    true(cell(2,3,b))
    true(cell(3,1,b))
    true(cell(3,2,b))
    true(cell(3,3,b))
    true(control(x))

Taking this input data and the logic program, we can check whether the state is terminal. In this case, it is not.

We can also compute the goal values of the state; but, since the state is non-terminal, there is not much point in doing that; but the description does give us the following values.

    goal(x,50)
    goal(o,50)

More interestingly, using this state description and the logic program, we can compute legal actions in this state. See below. The x player has nine possible actions (all marking actions), and the o player has just one (noop).

    legal(x,mark(1,1))
    legal(x,mark(1,2))
    legal(x,mark(1,3))
    legal(x,mark(2,1))
    legal(x,mark(2,2))
    legal(x,mark(2,3))
    legal(x,mark(3,1))
    legal(x,mark(3,2))
    legal(x,mark(3,3))
    legal(o,noop)

Let's suppose that the x player chooses the first legal action and the o player chooses its sole legal action. This gives us the following dataset for does.

    does(x,mark(1,1))
    does(o,noop)

Now, combing this dataset with the state description above and the logic program, we can compute what must be true in the next state.

    next(cell(1,1,x))
    next(cell(1,2,b))
    next(cell(1,3,b))
    next(cell(2,1,b))
    next(cell(2,2,b))
    next(cell(2,3,b))
    next(cell(3,1,b))
    next(cell(3,2,b))
    next(cell(3,3,b))
    next(control(o))

To produce a description for the resulting state, we substitute true for next in each of these sentences and repeat the process. This continues until we encounter a state that is terminal, at which point we can compute the goals of the players in a similar manner.

5. Game Requirements

The definitions in section 2.2 constrain GDL to game descriptions from which it is possible to compute the legal actions of all players for each state and from which it is possible to compute the next state for each state from the actions of all players. However, there are additional constraints that limit the scope of GDL to avoid problematic games.

Termination. A game description in GDL terminates if all infinite sequences of legal moves from the initial state of the game reach a terminal state after a finite number of steps.

Playability. A game description in GDL is playable if and only if every role has at least one legal move in every non-terminal state reachable from the initial state.

Winnability. A game description in GDL is strongly winnable if and only if, for some role, there is a sequence of individual individual actions of that role that leads to a terminal state of the game where that role's goal value is maximal no matter what the other players do. A game description in GDL is weakly winnable if and only if, for every role, there is a sequence of joint actions of all roles that leads to a terminal state where that role's goal value is maximal.

Well-formedness. A game description in GDL is well-formed if it terminates and is both playable and weakly winnable.

In general game playing, all well-formed single player games should be strongly winnable. Clearly, it is possible to generate game descriptions in GDL which are not well-formed. Checking game descriptions to see if they are well-formed can certainly be done in general by using brute-force methods (exploring the entire game tree); and, for some games, faster algorithms may exist. Game descriptions used in GGP competitions are always well-formed. However, in this book, we occasionally look at games that are not well-formed for reasons of simplicity or pedagogy.

6. Prefix GDL

The version of GDL presented here uses traditional infix syntax. However, this is not the only version of the language. There is also a version that uses prefix syntax.

Although some general game playing environments support Infix GDL, it is not universal. On the other hand, all current systems support Prefix GDL. Fortunately, there is a direct relationship between the two syntaxes, and it is easy to convert between them. There are just a few issues to worry about.

The first issue is the spelling of constants and variables. Prefix GDL is case-independent, so we cannot use capital letters to distinguish the two. Constants are spelled the same in both versions; but, in prefix GDL, we distinguish variables by beginning with the character '?'. Thus, the constant a is the same in both languages while the variable X in Infix GDL is spelled ?x or ?X in Prefix GDL.

The second issue in mapping between the formats is syntax of expressions. In Prefix GDL, all expressions are lists of components separated by spaces and enclosed in parentheses. Also, logical operators are spelled out. The following tables illustrates the mapping.

Finally, just to be clear on this, in Prefix GDL white space (spaces, tabs, carriage returns, line feeds, and so forth) can appear anywhere other than in the middle of constants, variables, and operator names. Thus, there can be multiple spaces between the components of an expression; there can be spaces after the open parenthesis of an expression and before the operator or relation constant or function constant; and there can be spaces after the last component of an expression and the closing parenthesis.