Game Trees

By Robert Laing

Glossary

Analysis: Assumes what is required to be done is already done. What is sought as already found, what we have to prove as true.
Antecedent: A thing that existed before or logically precedes another.

My introduction to this was via a free online course, General Game Playing, which offers a nice selection of games written in a Lisp-dialect called KIF which is fairly easy to translate into Prolog. The games follow a template called Game Description Language.

In terms of Prolog, rules of a game need to have these 6 predicates:

role/1
init/1
terminal
legal/2
next/1
goal/2

Optionally, there can also be base/1 and input/2.

These rely on 2 fluents:

true/1
does/2

Fluents in Prolog are predicates which have been set either by dynamic or thread_local to make them mutable using assertz/1 and retractall/1.

Rock-Paper-Scissors

Here’s a simple example of a simultanious move game, rock-paper-scissors, I’ve written in Prolog using the GDL template:

:- thread_local true/1, does/2.

role(bart).
role(lisa).

init(control(bart)).
init(control(lisa)).

legal(Player, rock) :- role(Player).
legal(Player, paper) :- role(Player).
legal(Player, scissors) :- role(Player).

next(reveal(Player, Action)) :- does(Player, Action).

goal(Player, 50)  :- true(reveal(Player, Action)), true(reveal(Opp, Action)), Player \= Opp.
goal(Player, 100) :- true(reveal(Player, paper)), true(reveal(Opp, rock)), Player \= Opp.
goal(Player, 0)   :- true(reveal(Player, rock)), true(reveal(Opp, paper)), Player \= Opp.
goal(Player, 100) :- true(reveal(Player, rock)), true(reveal(Opp, scissors)), Player \= Opp.
goal(Player, 0)   :- true(reveal(Player, scissors)), true(reveal(Opp, rock)), Player \= Opp.
goal(Player, 100) :- true(reveal(Player, scissors)), true(reveal(Opp, paper)), Player \= Opp.
goal(Player, 0)   :- true(reveal(Player, paper)), true(reveal(Opp, scissors)), Player \= Opp.

terminal :- true(reveal(bart, _)), true(reveal(lisa, _)).

How to describe game states falls under knowledge representation and reasoning, and the system GDL uses is attributed to Jacques Herbrand (a classmate of John von Neumann who died in mountaineering accident when he was just 23). Herbrand semantics is an alternative to Tarskian semantics, and GDL’s creator Michael Genesereth described his reaons for selecting it in this article.

Rock-paper-scissors is a 1-move game ending in 9 possible terminals. A game state is a set of Herbrand bases. Since sets are a tough concept for computers, we’ll use ordered list as produced in Prolog by sort/2 to describe each possible state in this game:

[control(bart), control(lisa)].
[reveal(bart, rock), reveal(lisa, rock)].
[reveal(bart, rock), reveal(lisa, paper)].
[reveal(bart, rock), reveal(lisa, scissors)].
[reveal(bart, paper), reveal(lisa, rock)].
[reveal(bart, paper), reveal(lisa, paper)].
[reveal(bart, paper), reveal(lisa, scissors)].
[reveal(bart, scissors), reveal(lisa, rock)].
[reveal(bart, scissors), reveal(lisa, paper)].
[reveal(bart, scissors), reveal(lisa, scissors)].

All the elements of the above 10 sets are built from these 8 elements (aka Herbrand bases):

base(control(bart)).
base(control(lisa)).
base(reveal(bart, rock)).
base(reveal(lisa, rock)).
base(reveal(bart, paper)).
base(reveal(lisa, paper)).
base(reveal(bart, scissors).
base(reveal(lisa, scissors)).

The current state true(Base), transition state next(Base) and starting state init(Base) form a kind of family since they all hold the same type as their sole argument.

Similarly legal(Role, Action), does(Role, Action), and input(Role, Action) are related:

input(bart, rock).
input(bart, paper).
input(bart, scissors).
input(lisa, rock).
input(lisa, paper).
input(lisa, scissors).

Arthur Samuel

1. Tree Generator

2. Position Evaluator

3. Minimax Procedure

My main reference is Introduction to Automata Theory, Languages, and Computation by Johne Hopcroft, Rajeev Motwani and Jeffrey Ullman.

Chapter 10 Patterns, Automata, and Regular Expressions of Al Aho’s and Jeff Ullman’s Foundations of Computer Science gives a briefer (and free) overview.

A chess automata

It is downright sinful to teach the abstract before the concrete. — quote attributed to Z. A. Melzack by Donald Knuth in Concrete Mathematics

I’m going to use Portable Game Notation to try give a concrete explanation of automata. Huge numbers of chess games in this format (ie text files with .pgn suffixes) can be downloaded from PGN Mentor and elsewhere.

Below is the first game taken from a file called Kasparov.pgn, describing a game played in 2004 between then world chess champion Garry Kasparov and Magnus Carlsen who has held that title since 2013.

[Event "Reykjavik Blitz"]
[Site "?"]
[Date "2004.03.17"]
[Round "?"]
[White "Kasparov, Garry"]
[Black "Carlsen, Magnus"]
[ECO "A16"]
[WhiteElo "2831"]
[BlackElo "2484"]
[Result "1-0"]

1. c4 Nf6 2. Nc3 g6 3. g3 c5 4. Bg2 Nc6 5. Nf3 d6 6. d4 cxd4 
7. Nxd4 Bd7 8. O-O Bg7 9. Nxc6 Bxc6 10. e4 O-O 11. Be3 a6 
12. Rc1 Nd7 13. Qe2 b5 14. b4 Ne5 15. cxb5 axb5 16. Nxb5 Bxb5 
17. Qxb5 Qb8 18. a4 Qxb5 19. axb5 Rfb8 20. b6 Ng4 21. b7 

1-0

Part of a transition diagram for the above game could look like this:

Chess has a start state, conventionally written q₀, from which the white player can choose one of 20 actions {a3, a4, b3, b4, c3, c4, d3, d4, e3, e4, f3, f4, g3, g4, h3, h4, Na3, Nc3, Nf3, Ng3}.

Black can then respond to each of these with 20 actions {a6, a5, b6, b5, c6, c5, d6, d5, e6, e5, f6, f5, g6, g5, h6, h5, Na6, Nc6, Nf6, Ng6}.

Drawing this as a game tree would lead to 20 states in the level after 20, followed by 400 to include all of black’s responses — making a full game tree of chess very busy.

Automata basic components

Textbooks generally split automata into three scales:

Alphabets Σ
Strings Σ^*
Languages L ⊆ Σ^*

Let’s take a “big picture” approach by starting a the language level of PGN and then working down to strings and alphabets.

Languages

The mathematical definition of languages are sets of words conventionally denoted L = {w₁, w₂, w₃, …, w_n} where each of these words w is a string of zero or more characters in the alphabet.

The PGN specification splits however many games in a given .pgn file into a Tag pair section which provides the who, what, where, when… information which I’m going to ignore here.

The Movetext section is a list of inputs which move from the conventional chess start state to wherever the game ended, and finally provide the score as 1-0 for white victory, 0-1 for black victory, or 1/2-1/2 for stalemate.

Alphabet Σ

For computer program interpreters or compilers, alphabets tend to be synonymous with character encoding methods, which at time of writing tends to be utf-8. The convention is to denote the alphabet of an automata as a set of characters Σ = {…}. Using utf-8, we could made our alphabet look something like:

Σ = {♔, ♕, ♖, ♗, ♘, ♙, ♚, ♛, ♜, ♝, ♞, ♟,…}

The section of the PGN standard titled Lexicographical issues says it uses ISO 8859/1, a hint it dates back to the nineties. Everything is simple plain text, with pawn = “P”, knight = “N”, bishop = “B”, rook = “R”, queen = “Q”, and king = “K”.

PGN notation doesn’t require the colour of a piece to be given since that can be deduced from its position after the turn count, eg 1. c4 Nf6 means the white pawn moves to c4, then the black knight moves to f6. In chess, turn means two plies, ie white does an action, and then black (unless game-over).

Other alphabet elements (ie characters) we’ll need are for saying where the above pices are, which in chess follows the convention that columns are labelled a to h, and rows are labelled from bottom up 1 to 8. PGN includes a couple of other characters such as x for a capturing move, + check, # checkmate, *=" pawn promotion, …

Strings Σ^*

A common use of automata is for language parsing. In the Unix world, parsers are traditionally written in two steps: firstly, the rules for how to split the provided stream of characters into a given language’s words and punctuation are written in flex; secondly, the rules for how to form sentences in a given language from these lists of tokens are written in bison.

The Python implementation of this pair is called ply, which is a bit confusing in Game Theory where ply means a given player’s turn in a round.

Prolog offers an alternative way of parsing, called definite clause grammar (DCG), which I personally find easier than flex and bison.

Many programing languages, including SWI-Prolog, use string interchangeably with text. As described in The string type and its double quoted syntax, Prolog in a sense has two types of text, single or unquoted atoms which are typically used for literals or identifiers, and double-quoted text which is syntactic-sugar for a list of characters (ie a list of elements from alphabet Σ).

Something I found confusing about automata is the same idea is applied at various scales. For a lexical analysis automata, the input string is read character-by-character. But once turned into tokens, the string in the case of PGN becomes [c4, Nf6, Nc3, g6, g3, c5, Bg2, Nc6, Nf3, d6, d4, cxd4…]. Once a word-by-word automata has converted these to sentences, a higher-scale automata could process those.

For instance, in chess, common opening moves are grouped into patterns with names like Sicilian, Queen’s Gambit Declined, King’s Indian… so a higher level automata could use groups of moves rather than individual moves as its inputs.