2.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, 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) it has restrictions that assure that all questions of logical entailment for any description in the language are decidable and (2) it includes some reserved words that specialize it for the description of games.

This chapter is an introduction to GDL and the issues that arise in using it to describe games. We start with an introduction to the modeling games as dataset graphs, and we illustrate with the game of Tic Tac Toe. We then introduce GDL, and we show how to encode the rules of Tic Tac Toe as rules in GDL. Finally, we talk about additional features of games that ensure that they are interesting.

2.2 Games As Dataset Graphs

The GDL model of games starts with entities and relations. Entities represent objects presumed or hypothesized to exist in the game. Relations represent properties of those objects or relationships among them.

In our examples here, we refer to entities and relations using strings of letters, digits, and a few non-alphanumeric characters (e.g. "_"). For reasons described below, we prohibit strings beginning with upper case letters; all other combinations are acceptable. Examples include x, o, 123, and white_king.

The set of all entities that can be used in a game is called the domain of the game. The set of all relations in a game is called the signature of the game. In GDL, domains and signatures are always finite (albeit in some cases very, very large).

The arity of a relation is the number of objects involved in any instance of that relation. Arity is an inherent property of a relation and never changes.

A game schema consists of a domain, a signature, and an assignment of arities for each of the relations in the signature.

Given a game schema, we define a proposition to be a structure consisting of an n-ary relation from the signature and n objects from the domain. In what follows, we write propositions using traditional mathematical notation. For example, if r is a binary relation and a and b are entities, then r(a,b) is a proposition.

The propositional base for a game is the set of all propositions that can be formed from the relations and the entities in the game's schema. For a schema with entities a and b and relations p and q where p has arity 1 and q has arity 2, the propositional base is {p(a), p(b), q(a,a), q(a,b), q(b,a), q(b,b)}.

In GDL, propositions are usually partitioned into disjoint classes, viz. base propositions and effectory propositions (more commonly called actions). Base propositions represent conditions that are true in the state of a game, and effectory propositions represent actions performed by game players. (Later, in order to deal with partial information, we add sensory propositions (or percepts) to this partition. For now, we ignore percepts.)

2.4 Tic Tac Toe As a Dataset Graph

As an example, let us look at a conceptualization of the states for the game of Tic-Tac-Toe as datasets. We can think of states in terms of two relations. The cell relation holds of a row and a column and a filler if and only if the cell in the specified row and column contains the specified filler. The filler can be the mark of either player or the symbol b (indicating that the cell is blank). The control relation holds of the player whose turn it is to play. the table below lists all of the possible propositions that can be formed using this conceptualization.

cell(1,1,x)
cell(1,2,x)
cell(1,3,x)
cell(2,1,x)
cell(2,2,x)
cell(2,3,x)
cell(3,1,x)
cell(3,2,x)
cell(3,3,x)

cell(1,1,o)
cell(1,2,o)
cell(1,3,o)
cell(2,1,o)
cell(2,2,o)
cell(2,3,o)
cell(3,1,o)
cell(3,2,o)
cell(3,3,o)

control(x)
control(o)

cell(1,1,b)
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)

In Tic Tac Toe, there is only one type of action a player can perform - it can mark a cell. The binary operation 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 action base for this model is shown below.

mark(1,1)
mark(1,2)
mark(1,3)

mark(2,1)
mark(2,2)
mark(2,3)

mark(3,1)
mark(3,2)
mark(3,3)

The dataset shown below represents the initial state of Tic Tac Toe. All of the cells are blank and the x player is in control.

cell(1,1,b)
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(x)

Given the rules of Tic Tac Toe, all nine possible moves are legal in this state.

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

The graphs consists of all feasible states with arcs defining transitions. Too large too draw (here some 5040) states.

2.5 Game Description Language

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 through 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 seven 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.

action(a) means that a is a feasible action in the game.

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

legal(a) means it is legal for the player in control 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.

A GDL description is 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 relation and the game-specific base relations.

We can describe these concepts abstractly. However, experience has shown that most people learn their meaning more easily through examples. In the next section, we look at a definition of one particular game, viz. Tic Tac Toe.

2.6 Tic Tac Toe Game Rules

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

    role(white)
    role(black)

We can characterize the propositions of the game as shown below.

    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(white))
    base(control(black))

We can characterize the feasible actions for each role in similar fashion.

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

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

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(M,N,b)) :- index(M) & index(N)
    init(control(x))

With our declarations out of the way, we can get down to the dynamics of the game. First, we define legality. It is legal to mark a cell if that cell is blank.

legal(mark(M,N)) :- cell(M,N,b)

In GDL, symbols that begin with capital letters are variables, while symbols that begin with lower case letters are constants. The :- operator is read as "if" - the expression to its left is true if the expressions that follow it are true. See the next chapter for a full description of syntax and semantics of rules.

Next, we look at the update rules for the game. The first rules says that, if w is the player in control, and w marks the cell in row m and column n, then that cell contains a w in the next state. The second rule says that the cell is no longer blank. The third and fourth rules describe the change of control that occurs when a player marks a cell.

mark(M,N) :: control(W) ==> cell(M,N,W)
mark(M,N) :: ~cell(M,N,b)
mark(M,N) :: control(x) ==> ~control(x) & control(o)
mark(M,N) :: control(o) ==> ~control(o) & control(x)

Goals. The x player gets a score of 100 if there is a line of x's and no line of o's. It gets 0 points if there is a line of o's and no line of x's. Otherwise, it gets 50 points. The rewards for the o player 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(Z) :- row(M,Z)
line(Z) :- column(M,Z)
line(Z) :- diagonal(Z)

row(M,Z) :- cell(M,1,Z) & cell(M,2,Z) & cell(M,3,Z)
column(N,Z) :- cell(1,N,Z) & cell(2,N,Z) & cell(3,N,Z)
diagonal(Z) :- cell(1,1,Z) & cell(2,2,Z) & cell(3,3,Z)
diagonal(Z) :- cell(1,3,Z) & cell(2,2,Z) & cell(3,1,Z)

Termination. A game terminates whenever there is a line of marks of the same type or if the game is no longer open, i.e. there are no blank cells.

terminal :- line(x)
terminal :- line(o)
terminal :- ~open

open :- cell(M,N,b)

Note that, 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, goal, and terminal in terms of cell and control. 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. That said, the resulting descriptions are more verbose and more expensive to process.

2.7 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.