C H A P T E R  2
 Game Description

### 2.1 Introduction

In general game playing, games are defined in a formal language known as GDL. GDL is a logic programming language. It is similar to other logic programming languages, such as Datalog and Prolog and Epilog, except that (1) its semantics is purely declarative, (2) it has restrictions that assure that all questions of logical entailment for any description in the language are decidable, and (3) it includes some reserved words that specialize it for the description of games.

We start this chapter with an introduction to logic programs in general. We then look at GDL in particular. We examine some requirements that avoid uninteresting games. Finally, we discuss some pragmatic details concerning the use of GDL, viz. the prefix syntax used in GGP competitions and the process of obfuscation.

### 2.2 Logic Programs

Logic Programs are built up from four disjoint classes of words, viz. object constants, function constants, relation constants, and variables. In what follows, we write such words as strings of letters, digits, and a few non-alphanumeric characters (e.g. "_"). Constants must begin with a lower case letter or digit. Examples include a, b, 123, comp225, and barack_obama. Variables must begin with an upper case letter. Examples include X, Y, Z, Age14, and so forth.

A term is either an object constant, a variable, or a functional term, i.e. an expression consisting of a function constant and n simpler terms. In what follows, we write functional terms in traditional mathematical notation - the function constant followed by its arguments enclosed in parentheses and separated by commas. For example, if f is a function constant, if a is an object constant, and if Y is a variable, then f(a,Y) is a term. Functional terms can be nested within other functional terms. For example, if f(a,Y) is a functional term, then so is f(f(a,Y),Y).

An atom is an expression formed from a relation constant and n terms. As with functional terms, we write atoms in traditional mathematical notation - the relation constant followed by its arguments enclosed in parentheses and separated by commas. For example, if r is a relation constant, if f is a function constant, if a is an object constant, and if Y is a variable, then r(a,Y) is a term and so is r(a,f(a,Y)). Although functional terms can be used within functional and within atoms, the reverse is not true - atoms cannot be nested inside of other atoms or inside of functional terms.

A literal is either an atom or a negation of an atom. A simple atom is called a positive literal, The negation of an atom is called a negative literal. In what follows, we write negative literals using the negation sign ~. For example, if p(a,b) is an atom, then ~p(a,b) denotes the negation of this atom.

A rule is an expression consisting of a distinguished atom, called the head, a conjunction of zero or more literals, called the body. The literals in the body are called subgoals. In what follows, we write rules as in the example shown below. Here, q(X,Y) is the head, p(X,Y) & ~r(Y) is the body; and p(X,Y) and ~r(Y) are subgoals.

```    q(X,Y) :- p(X,Y) & ~r(Y)
```

A logic program is a finite set of atoms and rules of this form. In order to simplify our definitions and analysis, we occasionally talk about infinite sets of rules. While these sets are useful, they are not themselves logic programs.

A rule in a logic program is safe if and only if every variable that appears in the head or in any negative literal in the body also appears in at least one positive literal in the body. A logic program is safe if and only if every rule in the program is safe.

The dependency graph for a logic program is a directed graph in which the nodes are the relations in the program and in which there is an arc from one node to another if and only if the former node appears in the body of a rule in which the latter node appears in the head. A program is recursive if and only if there is a cycle in the dependency graph.

A negation in a logic program is said to be stratified if and only if there is no recursive cycle in the dependency graph involving a negation. A logic program is stratified with respect to negation if and only if there are no unstratified negations.

The recursion in a set of rules is said to be stratified if and only if every variable in every subgoal relation (including the recursive relation) occurs in a subgoal involving a relation at a lower stratum, i.e. either it is not recursive or its recursive cycle does not include the relation in the head of the rule in which it occurs as a subgoal.

In GDL, we concentrate exclusively on logic programs that are both safe stratified with respect to negation and recursion. While it is possible to extend the results here to other programs, such extensions are beyond the scope of this work.

The Herbrand universe for a logic program is the set of all terms that can be formed from the constants in the program's schema. Said another way, it is the set of all objects constants and all functional terms of the form f(t1,...,tn), where f is an n-ary function constant and t1, ... , tn are elements of the Herbrand base.

The Herbrand base for a logic program is the set of all atoms that can be formed from the constants in the program's schema. Said another way, it is the set of all sentences of the form r(t1,...,tn), where r is an n-ary relation constant and t1, ... , tn are elements of the Herbrand universe.

A dataset for a logic program is an arbitrary subset of the Herbrand base for the program. A model of a logic program is a dataset that satisfies the program (as defined below).

An instance of a rule in a logic program is a rule in which all variables have been consistently replaced by terms from the program's Herbrand universe. Consistent replacement means that, if one occurrence of a variable is replaced by a given term, then all occurrences of that variable are replaced by the same term.

A dataset D satisfies a logic program P if and only if D satisfies every ground instance of every sentence in P. The notion of satisfaction is defined recursively. An interpretation D satisfies a ground atom p if and only if p is in D. D satisfies a ground negation ~p if and only if p is not in D. D satisfies a ground rule p :- p1 & ... & pn if and only if D satisfies p whenever it satisfies p1, ... , pn.

In general, a logic program can have more than one model, which means that there can be more than one way to satisfy the rules in the program. In order to eliminate ambiguity, we adopt the minimal model approach to logic program semantics, i.e. we define the meaning of a safe and stratified logic program to be its minimal model.

A model D of a logic program P is minimal if and only if no proper subset of D is a model for P. A logic program that does not contain any negations has one and only one minimal model. A logic program with negation may have more than one minimal model; however, if the program is stratified, then once again there is only one minimal model. In general, models can be infinitely large. However, if the program has stratified recursion, then it is guaranteed to be finite.

Computing the minimal model for a logic program is conceptually easy. We initialize our dataset to the ground atoms in the program. We then look at the rules in the program. If there is an instance of the rule whose body is satisfied by the atoms in our dataset, then we add the corresponding instance of the head to the dataset. This process continues until it reaches a fixpoint, i.e. there are no additional ground atoms added by any rule. It can be shown that this process computes the unique minimal model for every logic program so long as it is safe and stratified with respect to negation and recursion.

As an example, consider the following logic program. We have a few facts about about the parent relation; wee have a rule defining the grandparent relation in terms of parent; and we have two rules defining ancestors in terms of parents.

```    parent(art,bob)
parent(art,bud)
parent(bob,cal)
parent(bob,coe)
parent(cal,dan)

grandparent(X,Z) :- parent(X,Y) & parent(Y,Z)
ancestor(X,Y) :- parent(X,Y)
ancestor(X,Z) :- ancestor(X,Y) & ancestor(Y,Z)
```

We start the computation by initializing our dataset to the five facts about parent.

```    parent(art,bob)
parent(art,bud)
parent(bob,cal)
parent(bob,coe)
parent(cal,dan)
```

Looking at the grandparent rule and matching its subgoals to the data in our dataset in all possible ways, we see that we can add the following data.

```    grandparent(art,cal)
grandparent(art,coe)
grandparent(bob,dan)
```

Looking at the ancestor rule and matching its subgoals to the data in our dataset in all possible ways, get the following data.

```    ancestor(art,bob)
ancestor(art,bud)
ancestor(bob,cal)
ancestor(bob,coe)
ancestor(cal,dan)
```

```    ancestor(art,cal)
ancestor(art,coe)
ancestor(bob,dan)
```

However, we are not done. Using the ancestor rule again, we can derive the following additional datum.

```    ancestor(art,dan)
```

At this point, none of the rules when applied to this collection of data produces any results that are not already in the set, and so the process terminates. The resulting collection of 17 facts is the minimal model.

Logic programs as just defined are closed in that they fix the meaning of all relations in the program. In open logic programs, some of the relations (the inputs) are undefined, and other relations (the outputs) are defined in terms of these. The same program can be used with different input relations, yielding different output relations in each case.

Formally, an open program is a logic program together with a partition of the relation constants into two types - base relations (also called input relations) and view relations (also called output relations). View relations can appear anywhere in the program, but base relations can appear only in the subgoals of rules, not in their heads.

The input base for an open logic program is the set of all atoms that can be formed from the base relations of the program and the entities in the program's domain. An input model is an arbitrary subset of its input base.

The output base for an open logic program is the set of all atoms that can be formed from the view relations of the program and the entities in the program's domain. An output model is an arbitrary subset of its output base.

Given an open logic program P and an input model D, we define the overall model corresponding to D to be the minimal model of PD. The output model corresponding to D is the intersection of the overall model with the program's output base; in other words, it consists of those sentences in the overall model that mention the output relations.

Finally, we define the meaning of an open logic program to be a function that maps each input model for the program into the corresponding output model.

As an example, consider the parenthood example mentioned earlier. We could split this program into two parts - the data about the parent relation and an open logic program defining grandparent and ancestor. Given the parent data as input, the output of the open logic program would be the sentences in the minimal model that mention grandparent or ancestor.

Of course, this is the result for just one input. We could apply the open logic program to different parent data, leading to different results for grandparent and ancestor.

### 2.3 Game Definition Language

Game Definition Language (GDL) is a logic programming language intended for use in describing games. In GDL, we fix the meanings of some words in the language for all games (the game-independent vocabulary) while at the same time allowing game authors to use their own words for individual games (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.

The distinguished vocabulary words that support this are described below.

role(a) means that a is a role in the game.
input(t) means that t is a base proposition in the game.
base(a) means that a is an action 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,n) means that player the current state has utility n for player r. n must be an integer from 0 through 100.
terminal means that the current state is a terminal state.
distinct(x,y) means that x and y are different.

We can define the meaning of these concepts with mathematical precision. However, experience has shown that most people learn their meaning more easily through examples. To this end, let us look at a definition of one particular game, viz. Tic-Tac-Toe.

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). (Yes, 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 term 3-ary function constant cell to map a row m and a column n and a mark w to 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 it is not his turn to mark a cell). The binary function mark maps a a row m and a column n into the action of placing a mark in row m and column n. The mark paced there depend 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.

```    action(mark(M,N)) :- index(M) & index(N)
action(noop)

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 ha 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 he has control. Otherwise, so long as there is a blank cell, the only legal action is noop.

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

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

legal(B,noop) :-
true(cell(X,Y,b)) &
true(control(W))
```

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, then it remains blank. Finally, control alternates on each play.

```    next(cell(M,N,X)) :-
does(white,mark(M,N)) &
true(cell(M,N,b))

next(cell(M,N,O)) :-
does(black,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,W)) &
distinct(M,J)

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

next(control(white)) :-
true(control(black))

next(control(black)) :-
true(control(white))
```

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

```    goal(white) :- line(x)
goal(black) :- 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.

```    terminal :- line(x)
terminal :- line(o)
```

In GDL, there is no restriction on the rules one may write. That said, 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, base, action, 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.

As an exercise in logic programming and GDL, let's look at the outputs of our program . To start, we can use it to compute the roles of the game. This is simple in the case of Tic-Tac-Toe, as they are contained explicitly in the program.

```    role(x)
role(o)
```

We can also compute the feasible actions of the. The extension of the action relation in this case consists of the ten sentences shown below.

```    action(mark(1,1))
action(mark(1,2))
action(mark(1,3))
action(mark(2,1))
action(mark(2,2))
action(mark(2,3))
action(mark(3,1))
action(mark(3,2))
action(mark(3,3))
```

Similarly we can compute the relevant 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 could also compute the goal values of the state, but since the state is non-terminal, there is not much point.

More interestingly, using this state description and the logic program, we can 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.

### 2.5 Game Requirements

The preceding definitions constrain GDL to produce game descriptions from which players can compute their legal moves for each state and can compute the next state for each state the moves of all players. However, there are additional constraints required to 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 moves of that role that leads to a terminal state of the game where that role's goal value is maximal. A game description in GDL is weakly winnable if and only if, for every role, there is a sequence of joint moves 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 (expanding the entire game graph); and, for some games, faster algorithms may exist. Game descriptions used in GGP competitions should always be well-formed.

### 2.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.

Infix GDLPrefix GDL
p(a,Y)(p a ?y)
~p(a,Y)(not (p a ?y))
p(a,Y) & p(Y,c)(and (p a ?y) (p ?y c))
q(Y) :- p(a,Y) & p(Y,c)(rule (q ?y) (and (p a ?y) (p ?y c)))
q(Y) :- p(a,Y) & p(Y,c)(rule (q ?y) (p a ?y) (p ?y c))

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.

### Exercises

1. Consider the game described here. Is the game strongly winnable, weakly winnable, or neither? Is the game playable?

2. Use our simple GDL stepper to compute the state resulting from the following three joint moves.

3. Create a suicide version of this game. Give a move history that takes the game from the initial state to a terminal state in which white has won. Use the GDL stepper to show that your history works.

4. Invent a simple (but non-trivial) game of your own. Describe in English. Write a GDL rulesheet for the game. Give a move history that takes the game from the initial state to a terminal state. Use the GDL stepper to show that your history works.

5. Extra Credit. Create a stylesheet for your game that renders match data. See Match DTD for a DTD for XML match descriptions and see Matches for some examples. Create an XML match description and show the page resulting from your stylesheet.