Frontier Software

Robert Laing's programing notes

Game Description Language

By Robert Laing

https://developer.mozilla.org/en-US/docs/Web/API/Web_Storage_API/Using_the_Web_Storage_API

Continuing from the simple example in Game Trees, I’m going to advance from abstracting the states and labels with letters and numbers to using computer data types and queries that can be generalised to nearly any game. I’m going to use Stanford University’s Game Description Language (GDL) as my starting point.

One of the advantages of using Stanford’s General Game Playing is its repository of games. These include the Tic Tac Toe example I used previously.

Possibly to create interest in both Prolog and Lisp, Stanford professor Michael Genesereth, created two styles of Game Description Language (GDL):

Infix GDL (Prolog) Prefix GDL (Lisp)
p(a,Y) (p a ?y)
~p(a,Y) (not (p a ?y))
p(a,Y) & p(Y,c) (and (p a ?y) (p ?y c))
q(Y) :- p(a,Y) & p(Y,c) (<= (q ?y) (and (p a ?y) (p ?y c)))
q(Y) :- p(a,Y) & p(Y,c) (<= (q ?y) (p a ?y) (p ?y c))

The games in the repository are written in the Lisp-style, called Knowledge Interchange Format. A snag is there’s no well supported application for KIF files that I know of.

My way to make KIF files useable is to translate them into SWI Prolog which is nearly identical to Infix GDL, with a couple of quirks.

tictactoe3.kif translated into tictactoe.pl could look like this:

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Tic Tac Toe 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Components
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

role(white).
role(black).

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(white)).
base(control(black)).

input(R, mark(2, 1)) :- role(R).
input(R, mark(2, 3)) :- role(R).
input(R, mark(3, 1)) :- role(R).
input(R, noop) :- role(R).

index(1).
index(2).
index(3).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% init
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

init(cell(1, 1, x)).
init(cell(1, 2, x)).
init(cell(1, 3, o)).
init(cell(2, 1, b)).
init(cell(2, 2, o)).
init(cell(2, 3, b)).
init(cell(3, 1, b)).
init(cell(3, 2, o)).
init(cell(3, 3, x)).
init(control(white)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% legal
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

legal(W, mark(X, Y)) :- true(cell(X, Y, b)), true(control(W)).
legal(white, noop) :- true(control(black)).
legal(black, noop) :- true(control(white)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% next
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

next(cell(M, N, x)) :- does(white, mark(M, N)), true(cell(M, N, b)).
next(cell(M, N, o)) :- does(black, mark(M, N)), true(cell(M, N, b)).
next(cell(M, N, W)) :- true(cell(M, N, W)), W \= b.
next(cell(M, N, b)) :- does(_W, mark(J, K)), true(cell(M, N, b)), (M \= J ; N \= K).
next(control(white)) :- true(control(black)).
next(control(black)) :- true(control(white)).

row(M, X) :- true(cell(M, 1, X)), true(cell(M, 2, X)), true(cell(M, 3, X)).
column(N, 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)).
line(X) :- row(_M, X).
line(X) :- column(M, X).
line(X) :- diagonal(X).
open :- true(cell(M, N, b)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% goal
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

goal(white, 100) :- line(x), \+(line(o)).
goal(white, 50) :- line(x), line(o).
goal(white, 50) :- \+(line(x)), \+(line(o)).
goal(white, 0) :- \+(line(x)), line(o).
goal(black, 100) :- \+(line(x)), line(o).
goal(black, 50) :- line(x), line(o).
goal(black, 50) :- \+(line(x)), \+(line(o)).
goal(black, 0) :- line(x), \+(line(o)).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% terminal
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

terminal :- line(x).
terminal :- line(o).
terminal :- \+(open).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Even for intermediate Prolog programmers like me, there’s plenty of confusing stuff in the above code, so I’ll run through the 6 sections the provided tic tac toe rules are split into, which is pretty much the standard template for most General Game Player rules

Components

Roles

role(white).
role(black).

Calling the X player white and O black is somewhat confusing. A point with GDL is the same code handles everything from solitaire games (ie 1 player) to N players games. The first role(Player) is the same as init(control(Player)) and all other GGP games I’ve looked at, but I’m not sure that’s a safe assumption. The rules generally start with a role(Player) for however many players there are, allocating them names.

I initially found Prolog clauses confusing in that they look like function(Argument1, Argument2, ...), whereas one should think of them as rows in a table (known as relations in computer science).

Within the swipl repl, which players there are could be queried by:

?- role(Player).
Player = white ;
Player = black.

Within Prolog programs, I generally find converting these clauses to a list with findall(+Template, :Goal, -Bag) as in:

?- findall(Role, role(Role), Roles).
Roles = [white, black].

and then iterating through this list handier. Especially as I’ll explain later, GGP handles simultanious move games, provided each player’s action is listed, even if it’s noop for a player in a conventional alternating moves game.

Bases

Herbrand base
is the set of all ground atoms that can be made with the constants appearing in the program.

This is a term which relates to Herbrand’s Base. These bases could be thought of as letters in a alphabet from which words equating to a state are built. (At least in the way I’ve implemented this, states are lists whose elements are bases).

In this example, any given tic tac toe state has 9 cell(Row, Column, Mark) clauses and a control(Role) clause. The 27 possibilities for cell(Row, Column, Mark) clauses and 2 control(Role) clauses can be obtained from the base(Base) clauses.

findall(Base, base(Base), Bases).
Bases = [cell(1, 1, x), cell(1, 2, x), cell(1, 3, x), 
         cell(2, 1, x), cell(2, 2, x), cell(2, 3, x), 
         cell(3, 1, x), cell(3, 2, x), cell(3, 3, x),
         cell(1, 1, o), cell(1, 2, o), cell(1, 3, o),
         cell(2, 1, o), cell(2, 2, o), cell(2, 3, o),
         cell(3, 1, o), cell(3, 2, o), cell(3, 3, o),
         cell(1, 1, b), cell(1, 2, b), cell(1, 3, b),
         cell(2, 1, b), cell(2, 2, b), cell(2, 3, b),
         cell(3, 1, b), cell(3, 2, b), cell(3, 3, b),
         control(white), control(black)].

The way GGP games are written is the current state is defined by a set of true(Base) facts being globally available so next(Base), legal(Role, Action), goal(Role, Utility), terminal etc don’t need to have the current state passed to them as an argument.

In earlier versions of my implementation, I did this by using assertz(+Term) and retractall(+Head) to make the current state a set of global variables — what members of the object-oriented programming cult call a singleton pattern.

update_state(State) :-
  retractall(true(_)), 
  forall(member(Base, State), assertz(true(Base))).

An advantage of doing it this way is the code as provided with a simple kif → Prolog translation works. Since the current state has to be changed often as the game tree is explored, this involves lots assertions and retractions — something older Prolog textbooks warn equates to slow programs, but apparently isn’t a problem for modern implementations like SWI Prolog.

Members of the functional programming cult whose shibboleths include immutability will find this abuse of the clausal store ideologically repugnant. Having never encountered temporal logic, I found the idea that things that are true in one state aren’t necessarily true in other states philosophically cool. However, my code got riddled with bugs from the confusion about what was currently true — turning into a practical lesson on the advantages of immutability.

The advantages of immutability have become clearer to me through learning parallel, concurrent, distributed… programming. Having several independantly running processes overwriting shared variables leads to bugs which are hard to replicate and track down.

SWI Prolog allows you to bypass the strictures of immutability by declaring certain clauses dynamic. To avoid a common problem in concurrent systems of independently running processes messing each other’s variables up, there’s thread_local to create seperate dynamic clauses for each thread.

But I’ve generally come to the conclusion that true(Base) is just an ungainly way of saying memberchk(Base, State) where State is a list [Base0, Base1, Base2, ...].

The next(Base), legal(Role, Move) etc predicates involve methodically going through each base in the current state, which I find easier to do by list iteration which ensures the order of bases is maintained from statei to statej and that no bases are accidently omitted.

Inputs

While states make up the nodes of our game tree, labels — called input symbols — make up the edges. Much as base(Base) provides us with the alphabet of states, input(Input) provides us with the alphabet of edge labels.

?- findall(does(Role, Action), input(Role, Action), Inputs).
Inputs = [does(white, mark(2, 1)), does(black, mark(2, 1)), 
          does(white, mark(2, 3)), does(black, mark(2, 3)), 
          does(white, mark(3, 1)), does(black, mark(3, 1)), 
          does(white, noop), does(black, noop)].

The examples in Michael Genesereth’s and Michael Thielscher’s book tend to be for alternate move games (eg tic tac toe) or puzzles, hiding that the GGP system handles simultanious move games.

To keep things abstract, I prefer to make the labels [does(white, mark(3, 1)), does(black, noop)] so no modifications would be needed if black could do something more interesting than wait his turn.

In GDL, does is a the label version of true which next(Base) predicates expect to find as globals.

Other components

The above example files has various auxiliary clauses like index(1) in this section, and then the next section has row(M, X), column(N, X) which I think should be components — there don’t appear to be any hard and fast rules about what goes where. kif has no knowledge of things like counting, adding etc, so the chess rules for instance laboriously lists (succ 1 2)...(succ 200 201), adding 200 lines of code to something SWI Prolog can do with succ(?Int1, ?Int2).

Init

Init is the q0 ∈ Q state I’ll explain below when tying this into automaton theory.

findall(Base, init(Base), Start).
Start = [cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
         cell(2, 1, b), cell(2, 2, o), cell(2, 3, b), 
         cell(3, 1, b), cell(3, 2, o), cell(3, 3, x),
         control(white)].

The original expected global truths for its legal(Role, Move) queries to work. I not only want every possible legal move for the control(Role) player, but a cartesian product with each players moves, which in the case is legal(Opponent, noop) for the player whose turn it isn’t. Since I’ve changed the type from legal(Role, Base) to legal(Role, [Base|Bases]) I’ve changed the name to actions.

In automaton parlance, these actions are input symbols.

%% cartprod(+S, L) is det
% S is a list of lists, so finds cartesian product for any number of players  
cartprod(S, L) :-
  findall(R, cart(S, R), L).

cart([], []).
cart([[A | _] | T], [A | R]) :-
  cart(T, R).
cart([[_ | B] | T], R) :-
  cart([B | T], R).

actions(State, Actions) :-
  findall(Role, role(Role), Roles),
  maplist(legals(State), Roles, Legals),
  cartprod(Legals, Actions).

legals(State, Role, Legals) :-
  memberchk(control(Role), State),
  marks(Role, State, [], Legals).

legals(State, Role, [does(Role, noop)]) :-
  \+memberchk(control(Role), State).

marks(_, [], Unsorted, Legals) :-
  sort(Unsorted, Legals).

marks(Control, [cell(X, Y, b)|State], Legals, Acc) :- !,
  marks(Control, State, [does(Control, mark(X, Y))|Legals], Acc).

marks(Control, [_|State], Legals, Acc) :- 
  marks(Control, State, Legals, Acc). 

It returns a cartesian product of the moves, which for an alternate move game makes it explicit the non-control player does noop.

?- actions([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
            cell(2, 1, b), cell(2, 2, o), cell(2, 3, b), 
            cell(3, 1, b), cell(3, 2, o), cell(3, 3, x), 
            control(white)], Actions).
Actions = [[does(white, mark(2, 1)), does(black, noop)], 
           [does(white, mark(2, 3)), does(black, noop)], 
           [does(white, mark(3, 1)), does(black, noop)]] ;
false.

?- actions([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
            cell(2, 1, x), cell(2, 2, o), cell(2, 3, b), 
            cell(3, 1, b), cell(3, 2, o), cell(3, 3, x), 
            control(black)], Actions).
Actions = [[does(white, noop), does(black, mark(2, 3))], 
           [does(white, noop), does(black, mark(3, 1))]] ;
false.

Next

Here I’ve abandoned global truths for a list of bases to iterate through, I’ve rewritten the provided KIF code substantially. Besides no longer expecting a true(Base) for each element of the current state, the rewritten next expects to find the action (a list of does(Role, Move) for each role in the order given at the top of the file) to figure out the changes to the next state.

The type of next has been changed from Base to [Base|Bases].

next(State, Inputs, Next) :-
  next_(State, Inputs, [], Next).

next_([], _, Reversed, Nexts) :-
  reverse(Reversed, Nexts).

% next(cell(M, N, x)) :- does(white, mark(M, N)), true(cell(M, N, b)).
next_([cell(M, N, b)|State], [does(white, mark(M, N)), does(black, noop)], Nexts, Acc) :-
  next_(State, [does(black, noop), does(white, mark(M, N))], [cell(M, N, x)|Nexts], Acc).

% next(cell(M, N, o)) :- does(black, mark(M, N)), true(cell(M, N, b)).
next_([cell(M, N, b)|State], [does(white, noop), does(black, mark(M, N))], Nexts, Acc) :-
  next_(State, [does(black, mark(M, N)), does(white, noop)], [cell(M, N, o)|Nexts], Acc).

% next(cell(M, N, b)) :- does(_W, mark(J, K)), true(cell(M, N, b)), (M \= J ; N \= K).
next_([cell(M, N, b)|State], Inputs, Nexts, Acc) :-
  memberchk(does(_, mark(J, K)), Inputs),
  (M \= J ; N \= K),
  next_(State, Inputs, [cell(M, N, b)|Nexts], Acc).

% next(cell(M, N, W)) :- true(cell(M, N, W)), W \= b.
next_([cell(M, N, W)|State], Inputs, Nexts, Acc) :-
  W \= b,
  next_(State, Inputs, [cell(M, N, W)|Nexts], Acc).

% next(control(white)) :- true(control(black)).
next_([control(white)|State], Inputs, Nexts, Acc) :-
  next_(State, Inputs, [control(black)|Nexts], Acc).

% next(control(black)) :- true(control(white)).
next_([control(black)|State], Inputs, Nexts, Acc) :-
  next_(State, Inputs, [control(white)|Nexts], Acc).

move is the δ(qi, ax) → qj transition function I’ll explain later.

?- next([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o),
         cell(2, 1, b), cell(2, 2, o), cell(2, 3, b),
         cell(3, 1, b), cell(3, 2, o), cell(3, 3, x),
         control(white)],
         [does(white, mark(3, 1)), does(black, noop)],
         Next).
Next = [cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
        cell(2, 1, b), cell(2, 2, o), cell(2, 3, b), 
        cell(3, 1, x), cell(3, 2, o), cell(3, 3, x),
        control(black)] ;
Next = [cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
        cell(2, 1, b), cell(2, 2, o), cell(2, 3, b), 
        cell(3, 1, x), cell(3, 2, o), cell(3, 3, x),
        control(black)] ;
false.

For some reason my implementation gives the same result twice.

Goal

The given rules provide values per player. For adversarial search, we want each state to have a set of values for each player.

value_(Role, Value, value(Role, Value)).

values(State, Values) :-
  findall(Role, role(Role), Roles),
  maplist(goal(State), Roles, Goals),
  maplist(value_, Roles, Goals, Values). 

goal(State, white, 100) :- line(State, x), \+line(State, o).
goal(State, white, 50) :- line(State, x), line(State, o).
goal(State, white, 50) :- \+line(State, x), \+line(State, o).
goal(State, white, 0) :- \+line(State, x), line(State, o).
goal(State, black, 100) :- \+line(State, x), line(State, o).
goal(State, black, 50) :- line(State, x), line(State, o).
goal(State, black, 50) :- \+line(State, x), \+line(State, o).
goal(State, black, 0) :- line(State, x), \+line(State, o).
?- values([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o),
           cell(2, 1, x), cell(2, 2, o), cell(2, 3, b),
           cell(3, 1, o), cell(3, 2, o), cell(3, 3, x),
           control(white)], Values).
Values = [value(white, 0), value(black, 100)] ;
false.

?- values([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
           cell(2, 1, x), cell(2, 2, o), cell(2, 3, o), 
           cell(3, 1, b), cell(3, 2, o), cell(3, 3, x),
           control(white)], Values).
Values = [value(white, 50), value(black, 50)] ;
false.

Terminal

terminal(State) :- line(State, x).
terminal(State) :- line(State, o).
terminal(State) :- \+open(State).

Testing the rewritten terminal predicate on different boards:

?- terminal([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
             cell(2, 1, x), cell(2, 2, o), cell(2, 3, b), 
             cell(3, 1, o), cell(3, 2, o), cell(3, 3, x),
             control(white)]).
true ;
false.

?- terminal([cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
             cell(2, 1, x), cell(2, 2, o), cell(2, 3, o), 
             cell(3, 1, b), cell(3, 2, o), cell(3, 3, x),
             control(white)]).
false.

Automatons

Games written in GDL have different sections which losely tie into the mathematical represenations of automatons (pedantically, just one type of automatons: Deterministic Finite Automaton (DFA)).

Automatons have the following 5 things:

1. Q, a finite set of states {q0, q1, q2, …, qn}

Except for some simple puzzles, GGP rules don’t provide us with the full set of states, only with a starting state and rules to generate the rest of the state machine.

2. q0, a start state which can be any state in Q

In this example q0 is:

findall(Base, init(Base), Start).
Start = [cell(1, 1, x), cell(1, 2, x), cell(1, 3, o), 
         cell(2, 1, b), cell(2, 2, o), cell(2, 3, b), 
         cell(3, 1, b), cell(3, 2, o), cell(3, 3, x),
         control(white)].

The start state isn’t necessarily the root of the game tree, it can be whatever qi ∈ Q happens to be the current state. Usually with tic tac toe, the start state would be a blank board. But here we’ve picked a q0 which could be thought of as a root of a subtree within the overall tic tac toe game tree.

3. ∑, a finite set of input symbols {a0, a1, a2, …, ai}

The Components section of the provided rules file has clause to generate this set:

The GGP notation handles simultanious move games. Most of the examples are for two player, alternate move games with an assumed input(white, noop). Making the input symbols a compound term that includes each player’s actions, even it’s noop, means simultanious move games are handled without any addaptions.

Games differ from DFAs in that the possible moves from a given state need to be figured out, for which GDL rules include legal(Role, Move) predicates.

4. δ(qi, ax) → qj, a transition function

For Prolog, which doesn’t have functions which tranform themselves into a result, this is represented by something like δ(qi, ax, qj). In simple English, the transition function tells us that if we are in a given state qi, and of its options of actions select ax, we get to the next state qj.

The next(Base) predicates in the provided rules. The first snag with the provided next predicates is they don’t read the current state and action as arguments, but assume every base in the current state is accessible as in the clausal store as true(Base) and that the action is available from the clausal store as does(Role, Move).

5. F ⊂ Q, a subset of states called final or accepting states

Game playing jargon differs from DFAs in that these are typically split into wins, draws, or losses.

GDL has a predicate terminal which again assumes true(Base) facts in the clausasl store, so need to be rewritten for the current state to be an input argument.

Last updated on 12 Jan 2021
Published on 12 Jan 2021

Content Footer