Game Description Language |

## 1. IntroductionThe 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 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 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 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 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 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 ## 3. Game Description ExampleIn 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 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 We begin with an enumeration of roles. In this case, there are just two roles, here called 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 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 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 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 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 ExampleAs 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(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(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 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 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 ## 5. Game RequirementsThe 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.
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 GDLThe 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 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. |