The Game Description Language

The Game Description Language is tasked with being able to describe a wide variety of games: chess, checkers, connect four, the iterated Prisoner's Dilemma, and so on. It requires only that the games have a few particular properties:

• The game is turn-based.
• The game is finite: a player's choice of moves on any given turn is finite, and the game will always end in a finite number of turns.
• The game is perfect-information: On every turn, every player knows all there is to know about the state of the game. In practice, this is the biggest restriction on GDL's expressiveness; consider card games where players' hands are hidden, Battleship, or Minesweeper.
• The game is deterministic, with no random elements. In practice, there are workarounds for this.

(A variant of GDL, called GDL-II, eliminates the last two requirements, but that will be left for a later post.)

Given this level of generality, what characteristics do all these games still share? Put another way, what questions will a gamer be able to ask the rules?

• Game roles: How many players are there, and what are their names, as used by the rest of the rules?
• The initial state of the game: What is the game state at the beginning of the game?
• Terminality: At a particular game state, is the game over?
• Legal moves: At a particular non-terminal game state, what are the legal moves for each player?
• Next state: Given a state and a move for each player, what is the next state of the game?
• Goal values: At a given terminal state, did each player win, lose, draw, or place somewhere in between? (In fact, goal values may be any integral value between 0 and 100, inclusive.)

It should be a bit clearer now that the language is capable of describing a wide variety of games.

One lingering question is how game state is described. After all, what works for chess (pieces on a board) won't work for a bidding game (quantities of money and resources). The simple solution is to allow each game to specify whatever state it needs in the form of logical propositions. For example, the fact that there is a white knight on f3 may be expressed by the proposition (cell wn f 3). A player's money count may be expressed as (money player1 17). Each game's propositions need only make sense in the context of the rest of the game rules.

GDL is nothing but a set of propositions and rules about propositions that can answer the questions listed above. In fact, the list of keywords is very nearly the same as my list of questions. Here they are, with sample propositions that might appear in chess:

• Role: (role white)
• Init: (init (cell wp e 2))
• Terminal: terminal
• Legal: (legal white (move wp e 2 e 4))
• Next: (next (cell wp e 4)) -- note the similarity to init.
• Goal: (goal white 100)
• True: When computing the terminal, legal, next, or goal propositions, we supply the propositions representing the current state of the game in a form like (true (cell wp e 4)). These can be taken from sets of init or next propositions.
• Does: When computing next propositions, we supply the moves of each player using does propositions, for example (does white (move wp e 2 e 4)).

My description thus far has left out one (major) aspect of the language: How do the rules work? How do we get from a set of inputs to a set of outputs?

The short answer is, "like Prolog", because GDL is at its heart a variant of Datalog, itself a variant of Prolog. I assume that this answer will be unsatisfactory to most of my readers, so let's dig in.

A GDL rulesheet consists of propositions and rules. The propositions listed this way will always be true over the course of the game. For example, the number of players can't change midway through a game, so role propositions are always listed in this way. If the game uses any sort of arithmetic, a successor function is generally listed. Many init propositions are listed explicitly (though often, rules with variables are a more concise way to specify them).

Rules are far more expressive. Let's look at an example from tic-tac-toe:

(<= (goal xplayer 50)
    (not (line x))
    (not (line o))
    (not open))

Note that the rule is a list with five components: the operator <=, which indicates that it is a rule; the head of the rule, which is the sentence (goal xplayer 50); and three literals, which make up the body of the rule.

In rules without variables, like this one, the head is true if every literal in the body is true. Because of the rule's use of the not operator, this means that (goal xplayer 50) is true if (line x), (line o), and open are all false. In other words, if there's no place left to play on the board and neither x nor o has formed a line, then xplayer will receive only 50 of 100 points -- a typical way to indicate a draw.

There may also be multiple rules for the same sentence, as for terminal in the same game:

(<= terminal
(line x))

(<= terminal
(line o))

(<= terminal
(not open))

Here, terminal is true if any one of the rules is fulfilled. The game ends if either player makes a line or if there is no open space on the board.

Relations and rules provide a way to specify that a sentence is true, but the logicians out there may be asking: How do we know when a sentence is false? Here, we rely on a rule known as negation as failure in the context of logical systems. It says that a sentence is false if it cannot be shown to be true. (In addition, GDL has some restrictions on negation and recursion (not described here) to prevent contradictory rules along the lines of (<= p (not p)).)

Finally, we have the use of variables in rules and the distinct operator, again from tic-tac-toe:

(<= (next (cell ?m ?n b))
(does ?player (mark ?j ?k))
(true (cell ?m ?n b))
(or (distinct ?m ?j) (distinct ?n ?k)))

First, note the use of the or operator. This is not actually part of the GDL standard as originally written, but is an "unofficial standard" of sorts, used widely across GDL rulesheets. As expected, it is true if any of its contained literals are true.

Next we have the distinct operator. This takes two arguments and is true when the arguments are not the same value.

Finally, we have the use of variables throughout the rule. Variables have names starting with a question mark. For every possible assignment of variables to values, the rule applies. For example, in the case where ?m = 2, ?n = 1, ?player = xplayer, ?j = 2, and ?k = 3:

(<= (next (cell 2 1 b))
(does xplayer (mark 2 3))
(true (cell 2 1 b))
(or (distinct 2 2) (distinct 1 3)))

The general form of the rule says that if any cell is blank ("b") and either player makes a move that differs from the cell in either coordinate, then the cell stays blank. (Note that the rule, as written, relies on the assumption that one and only one player makes a mark each turn.)

Every variable must be defined in a sentence literal in the rule, as opposed to a not or distinct literal. This restriction means that all the values of the variables are grounded, and came from somewhere in the original rules of the game. This keeps the set of possible sentences that can be in the game finite. (There is in fact a minor qualification of that statement, which I may post about at some point in the future.)

There's one last pair of keywords to mention: the base and input keywords, which are optional when constructing a game. (These are also not yet an official part of GDL.) These have no effect on the game itself, but provide some metadata which may be useful to a gamer. They explain, respectively, what sentences could possibly be part of the game state and what moves could possibly be made. They would be structured like the true and legal propositions, respectively: (base (cell wp e 4)) and (input white (move wp e 2 e 4)).

Why is this useful? Take the moves of checkers as an example. How many triple jumps are possible for each player? Well, there are 32 squares from which the piece may start, and each jump could be made in one of four directions (as it may be a king). This gives an upper bound of 32 * 4 * 4 * 4 = 2048 triple jumps. By contrast, a player doing simple static analysis might know only that each of the eight indices listed is one of eight values, and consider there to be 8^8 = 16,777,216 triple jumps! Techniques that rely on keeping all these possibilities in memory (like propositional networks) can greatly benefit from the more accurate specification.

There are a number of additional restrictions on games. The GGP-Base project includes a StaticValidator program that can check most of the potential syntactic errors. More important are the semantic restrictions:

• The game always ends in a finite number of moves. As a consequence of this, there cannot be any loops in the game state. Many games include an explicit "step counter" that ends the game after a certain number of moves to meet this requirement.
• Every player has at least one legal move in every possible state of the game. When players take turns, there is typically a "noop" move for the non-active player(s) to make.
• In every possible terminal state of the game, each player has exactly one goal value specified. (A stronger version of this requirement says that this should also be true in non-terminal states, though this isn't always followed. The GDL paper's stated requirement that goal values only increase over time is no longer useful and can be safely ignored.)
• A game should be weakly winnable for each player; that is, each player should be theoretically capable of getting a score of 100, though it might require the other players' cooperation.

Note that these deal with "possible" states of the game: These are the states that are actually possible to reach in the game tree. These restrictions don't apply to arbitrary combinations of game state propositions that are unreachable in practice.

That covers most of the syntax and requirements of the language, but there is still much to cover on how to write and test games in practice. That will be the subject of future posts.