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
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.
The role relation defines the players. In the case of Tic-Tac-Toe, the roles are:
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(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(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(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(player, value) makes the current state a goal state with value, where value is from 0-100. e.g.
(<= (goal ?player 100)
means that is line(player) returns true, then the state is worth 100.
Terminal is used to define the states that a game end with.
means that if line returns true for ?player, then the game ends.
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