The main goal of this class is to learn how to model turn games in a rule based language. After finishing the class, student should be able to model simple games and point out the difficulties related with this task.
GDL (Game Description Language) is a language designed to describe turn games. It was created to be used in so called General Game Playing, a subdomain of the AI, focused on creating bots able to play in any game that can be formally described.
The class is based on a tutorial from Stanford and slides from the university in Dresden.
There are two main approaches to model the world of the game:
GDL belongs to the fine-grained family, so there are:
We will show the basic features of the GDL on the example of the popular tic-tac-toe game.
Let's start with players “nought” and “cross”. There is a special fact role
just to do that:
role(nought) role(cross)
Syntax is the same as in the Prolog (or Datalog) language with the only difference, that there is no dot at the end of the sentence. All constants start with a lower-cased letter and variables are upper-cased.
Now we should define fluents that make up the game state. In a Tic-Tac-Toe game there are 29 fleunts:
x
) in the cell (9 fluents)o
) in the cell (9 fluents)b
) (9 fluents)
To define the fluents one uses the base
facts:
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(R)) :- role(R) index(1) index(2) index(3)
Here :-
represents an implication ←
. &
is a logical “and”. In natural language the first line means: “if M and N represent cells' indexes, then there is a fluent for cell with (M, N) coordinates, telling there is a cross in it”. If we didn't use rules, we could write all the fluents by hand:
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(nought)) base(control(cross))
Rules in GDL have one special feature: they can recurse, but they can't loop forever. More details here.
Now, we should model available actions, there are 20 of them here:
noop
per user, telling that player does do nothing
Thee noop
action exists only in order to simulate the players' turns. When one player makes the action then the second one has to take the noop
action.
In order to define an action we use the input
predicate:
input(R, mark(M,N)) :- role(R) & index(M) & index(N) input(R, noop) :- role(R)
The input
predicates takes two arguments, first is the player, second is the action itself.
Knowing the available actions, we have to define when the action is a legal move with a legal
predicate. We use the true
predicate to check if the fluent is true at the moment..
legal(W,mark(X,Y)) :- true(cell(X,Y,b)) & true(control(W)) legal(nought,noop) :- true(control(cross)) legal(cross,noop) :- true(control(nought))
In other words - player may mark a cell only if it is empty and it is his turn. If it is not his turn, he can only perform the 'noop' action.
Now we have to define the initial state of the game (draw the empty board). The init
predicate serves this purpose. For the tic-tac-toe every cell should be empty, and the nought
player should play first.
init(cell(M,N,b)) :- index(M) & index(N) init(control(nought))
Now the most difficult part — how does the state evolve in the game. We assume that the new state is created after the very move and depends only on the previous state and actions made by the players. On could notice the frame problem occurring here. The etymology of the frame
is the movie tape, where every frame differs in details from the previous one. Similarly here, we would like the next state to be exactly like the previous one except some changes made explicitly by the players. The problem is that in our case we have also to model lack of changes :(
To define the state evolution we use the next
predicate, defining the fluent state in the next turn. The 'does' predicate check what actions were made by the players during the current turn.
next(cell(M,N,x)) :- does(cross,mark(M,N)) & true(cell(M,N,b)) next(cell(M,N,o)) :- does(nought,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(nought)) :- true(control(cross)) next(control(cross)) :- true(control(nought))
The defined actions mean that:
distinct
checks equality of the arguments), then it will stay the same next turnIt's worth to note, that actions 3 and 4 are designed only to cope with the frame problem.
Every player knows that there are two ways to finish the game: make a line or fill all the available cells. Now we will check if there was a line made by the player.
line(Z) :- row(M,Z) line(Z) :- column(M,Z) line(Z) :- diagonal(Z) row(M,Z) :- true(cell(M,1,Z)) & true(cell(M,2,Z)) & true(cell(M,3,Z)) column(N,Z) :- true(cell(1,N,Z)) & true(cell(2,N,Z)) & true(cell(3,N,Z)) diagonal(Z) :- true(cell(1,1,Z)) & true(cell(2,2,Z)) & true(cell(3,3,Z)) diagonal(Z) :- true(cell(1,3,Z)) & true(cell(2,2,Z)) & true(cell(3,1,Z))
The true(line(naught))
query will tell if there is a line made of the 'o's on the board.
Now we can define the ending conditions with the terminal
predicate:
terminal :- line(x) terminal :- line(o) terminal :- ~open open :- true(cell(M,N,b))
Game ends when:
The '~' operator means negation. Similarly to the Prolog it follows the closed world assumption, ie. sentence is false if can't prove otherwise. In GDL ther are additional restrictions we want worry about for now (more info here).
Bots don't have feelings but we still should give them prize for the good game. And we do this with the goal
predicate:
goal(cross,100) :- line(x) & ~line(o) goal(cross,50) :- ~line(x) & ~line(o) goal(cross,0) :- ~line(x) & line(o) goal(nought,100) :- ~line(x) & line(o) goal(nought,50) :- ~line(x) & ~line(o) goal(nought,0) :- line(x) & ~line(o)
According to the rules above winner gets 100 (so much win!), in case of tie only 50, and loser gets 0. We don't what this number represent but it has to be something good like cookies.
There is no arithmetics in GLD — numbers are only used to define indexes, prizes, time, etc.
That's all folks, you've just modeled a simple tic-tac-toe game.
Let's take an even simpler game:
role(white) role(black) base(p) base(q) base(r) base(s) input(R,a) :- role(R) input(R,b) :- role(R) input(R,c) :- role(R) input(R,d) :- role(R) init(s) legal(white,a) legal(white,b) legal(white,c) legal(black,d) next(p) :- does(white,a) & ~true(p) next(p) :- ~does(white,a) & true(p) next(q) :- does(white,b) & true(p) next(q) :- does(white,c) & true(r) next(q) :- ~does(white,b) & ~does(white,c) & true(q) next(r) :- does(white,c) & true(q) next(r) :- ~does(white,c) & true(r) goal(white,100) :- terminal goal(white,0) :- ~terminal goal(black,100) :- terminal goal(black,0) :- ~terminal terminal :- true(p) & true(q) & true(r)
Answer the following questions:
Please model the 'crosses and crosses' game. The rules are similar to the tic-tac-toe, again we have nine cells, but both players use the crosses. Player loses when he first creates the line.
Please model the “Rock Paper Scissors Lizard Spock” game. You can learn the rules from this video. The image on the right is also a good reference. You can practice it with a colleague or like a modern man: online....
Everything we learned so far is true, but the GDL has an alternative syntax used to store and transfer the games: the Knowledge Interchange Format. It's based on a lisp and uses a prefix notation. Moreover :-
operator is replaced with ⇐
, &
with and
, negation ~
with not
. The variables start with the ?
. Below you can see an example of translation between Prolog:
p(a,Y) ~p(a,Y) p(a,Y) & p(Y,c) q(Y) :- p(a,Y) & p(Y,c) q(Y) :- p(a,Y) & p(Y,c)
and KIF:
(p a ?y) (not (p a ?y)) (and (p a ?y) (p ?y c)) (<= (q ?y) (and (p a ?y) (p ?y c))) (<= (q ?y) (p a ?y) (p ?y c))
For every example below, tell if the KIF version is a faithful translation of the Prolog one.
r(a,b) :- p(a) & q(b) (<= (r a b) (and (p a) (q b)))
r(a,b) :- p(a) & q(b) (<= (r a b) (p a) (q b))
r(x,y) :- p(x) & q(y) (<= (r ?x ?y) (p ?x) (q ?y))
r(X,Y) :- p(X) & q(Y) (<= (r ?x ?y) (p ?x) (q ?y))
Download the KIF version of the tic-tac-toe game. What are the differences between it and our model?
Read the simple blocks' world model.
Translate all the models you've created today to the KIF format.
The instructions below require an Eclipse IDE.
Please run the Eclipse IDE and:
File → Import Project
https://github.com/ggp-org/ggp-base.git
master
branchggp-base
project to be imported
In the project directory go to the games/games
catalogue and create there three directories tic-tac-toe
, cross-cross
and spock
. Every directory should contain two files:
<name>.kif
file with the modelMETADATA
file containing:{ "gameName": "<game name>", "rulesheet": "<kif file name>" }
From the Eclipse run the Validator
app (one of the targets next to the play
button).
Validator
will check if the model is a valid GDL model.
Repository
field choose Local Game Repository
Game
field select Tic-Tac-Toe
Validate
— There should be no failure
Run the Kiosk
app in the Eclipse (select from the list next to the play
button).