Introduction
All
games with finite
environments and
deterministic actions can be
represented by a
finite state machine, or FST. The state of the game environment is the current state, and all the
possible actions of the
players is the "arc"s going out. Using this FST presents a
problem: most games have a large enough state machine, that it cannot be fitted into
memory, e.g.
chess has 10^28 states. Furthermore, this state machine] must contain all the possible changes
coded into it. For
efficiency reasons, a compact representation is needed. Game
Description Language, or GDL, a derivative of
datalog that shares most of the syntax, was developed for this purpose. In GDL, the
game world is represented by a set of true facts. The rules of the game are described by sets of
logical rules, describing the next state in terms of the current state, and the moves of the players. This is useful for general game playing
AI.
Syntax
1. Vocabulary: a vocabulary is made up of the following:
a set of constants. e.g. a,b,c
a set of relations. with their associated arity, e.g. adjacent, on
note: a constant starts with a lower case letter, a variable doesn't
2. Term: a term is any constant or variable. e.g. A,str,boardwidth
3. Atomic Sentence: an atomic sentence is any relation that takes n inputs, being passed n inputs. e.g. p(1,2,6)
4. Literal: a literal is an atomic sentence, or the negation of one. e.g. p(1, 1, X) or ¬p(1, 1, X)
5. Ground Expression: an expression is a ground expression, if an only if it contains no variables. e.g. p(1,2,6)
6. Datalog Rule: a datalog rule is an implication(if x, then y) of the form
h ⇐ b1 ∧ · · · ∧ bn
The head, h, is an atomic sentence.
Each statement, bi, is a literal.
Safety: if a variable appears in the head or in a negative literal, it must appear in a positive literal in the body. This is due to limitations in datalog
7. Dependency Graph: let ∆ be a set of datalog rules. The nodes in the graph are the relationships in the vocabulary. There is an edge between r2 and r1 whenever there is a rule in ∆ with r1 in the head and r2 in the body. if r2 is a negitive literal, then the edge is labelled with ¬
8. Stratified Datalog Rules: a set of datalog rules is stratified if and only if there are no cycles with edges labelled with ¬.
e.g. p(X) ⇐ q(X)
q(X) ⇐ r(X) ∧ ¬p(X))
is not stratified. Their is a link from q to p, from r to q and from p to q. however as the last link is labelled with ¬, the set is not stratified.
Relations
role relation
The role relation defines the players. In the case of Tic-Tac-Toe, the roles are:
(role x)
(role o)
true relation
The relation true(fact) indicates that in the current state, fact is true. e.g.
(true (control x))
means that it's player x's turn.
init relation
init(fact) is the equivelent of true(fact) for the first state of the game. e.g.
(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))
means that player x starts, and all cells are blank.
next relation
next(fact) indicates that in the next state, fact will be true. e.g. tic-tac-toe fips between two states
(<= (next (control x))
(true (control o)))
(<= (next (control o))
(true (control x)))
does relation
does(player, move) returns true if the player made that move in the current state, otherwise returns false. e.g.
(<= (next (cell ?x ?y b))
(does ?player (mark ?m ?n))
(true (cell ?x ?y b))
(distinctCell ?x ?y ?m ?n))
(<= (distinctCell ?x ?y ?m ?n)
(distinct ?x ?m))
(<= (distinctCell ?x ?y ?m ?n)
(distinct ?y ?n))
indicates that, if a player performs the mark action on a cell, that cell is marked with that players symbol, otherwise it remains blank.
goal relation
goal(player, value) makes the current state a goal state with value, where value is from 0-100. e.g.
(<= (goal ?player 100)
(line ?player))
means that is line(player) returns true, then the state is worth 100.
terminal relation
Terminal is used to define the states that a game end with.
(<= terminal
(role ?player)
(line ?player))
means that if line returns true for ?player, then the game ends.
GDL restrictions
Let ∆ be a GDL game description, and let G be the dependancy graph
for ∆. Then each of the following conditions must hold of ∆:
The role relation only appears in ground atomic sentences (as the head of a Datalog rule with no body).
The init relation only appears in the heads of Datalog rules (not in the bodies), and in G, the init node is not in the same connected component as true, does, next, legal, goal, or terminal.
The true relation only appears in the bodies of Datalog rules (not in the heads).
The next relation only appears in the heads of Datalog rules.
The does relation only appears in the bodies of Datalog rules, and in G, there are no paths between the does node and any of legal, goal, or terminal.
The specification for GDL can be found here