
Foundations of Combinatorial Game Theory
In this page, I describe a basic nomenclature for finitary combinatorial
games.
Notice that the games are played on a board with pieces, everything
already existing.
While the modelconstruction games like those of Wilfred Hodges' BUILDING
MODELS WITH GAMES could be included with this nomenclature, I won't go
into that here.
The Definition
A Combinatorial Game is a tuple
(G, :, E, A, W, L, 0),
where:

G is the set of positions and 0 is the initial position;

s : t means that it is legal to move from position s to
position t in one move;

there is a set ð G of terminal positions, from which
no move is possible;

E is the set of positions for which it is Eloise's turn to move,
while A is the set of positions for which it is Abelard's turn
(here E union A = G  ð G);

W is the set of positions at which Eloise wins, while L is the
set of positions at which Eloise loses at once (here, W union L =
ð G).
The game starts with a marker at 0.
The game proceeds by having players make legal moves, moving the marker
from position to position.
If the marker lands on a position in W, Eloise wins; if not, either
because it landed on a position in L or because the game went on
forever, Abelard wins.
An Example: NIM
As an example, consider the Game of Nim.
In this game, you have several stacks of coins on a table.
The two players play alternately, and each move consists of removing
some nonzero number of coins from a single stack.
The first player to face an empty table loses.
Here is the game (with positions) for Eloise facing the table having
two stacks of coins, one with three coins and the other with one.
Notice that we could analyze the game by first labelling the position
where Eloise
wins with a W, and then going upwards, labelling those positions
from which Eloise goes on to win with a WIN, and we see that
Eloise should win the game, unless she makes a mistake.
An Induction for Winning
We can formalize this WINning notion as follows.
On
(G, :, E, A, W, L, 0)
let WIN be an operator on the power set of G such that for any subset
S of G, let WIN(S) be the union of W and
{s in E : there exists t (s : t & t in S)}
and
{s in A : for all t (s : t ==> t in S)}.
If S is a set of positions from which Eloise shall win, so is
WIN(S).
Thus we can set up an induction
WIN^{0} = WIN(Ø),
WIN^{x} = WIN(UNION_{z < x}WIN^{z})
WIN* = UNION_{x}WIN^{x},
so that Eloise shall win from 0 iff 0 \in WIN*.
She wins as follows: at a position s in WIN^{x}, she plays to a
position t in UNION_{z < x} WIN^{z}.
And if O is not in WIN*, then Abelard shall win, as follows:
at a position s not in WIN*, he always plays to a position
t not in WIN*.
This sort of induction is explored in P. Aczel's article in THE
HANDBOOK OF MATHEMATICAL LOGIC.
Strategies
Another approach is to dissect what is meant by the phrases "Player Q
can play" and "Player Q can win".
Given a game (G, :, E, A, W, L, 0), a run is a sequence
(t_{0}, t_{1}, ...) from G such that:

t_{0} = 0, and for each n, if t_{n} is not in ð G,
t_{n} : t_{n+1}.

if the sequence ends, it terminates with a position in ð G.
If the run terminates in W, then Eloise wins the run; otherwise, Abelard
wins.
A strategy for Eloise is a function SIGMA: E > G such
that for each t in E, t :SIGMA(t).
Similarly, a strategy for Abelard is a function TAU: A > G such that for
each t in A, t :\SIGMA(t).
If Eloise uses SIGMA and Abelard uses TAU, the result is a run SIGMA
* TAU = (t_{0}, t_{1}, ...), where:

for each n, if t_{n} in E, then t_{n+1} =
SIGMA(t_{n});

for each n, if t_{n} in A, then t_{n+1} = TAU(t_{n}).
We say that SIGMA beats TAU if Eloise wins the run SIGMA * TAU,
otherwise Abelard wins the run and TAU beats SIGMA.
If SIGMA beats every run of Abelard's we call SIGMA a winning
strategy for Eloise (similarly, Abelard can have winning strategies).
Notice that it is not possible for both Abelard and Eloise to have winning
strategies, but it is not inconceivable that niether have a winning
strategy.
This is the classical approach that one sees in papers from those in
economic game theory to logical games.
The Game Quantifier
A third approach is to use a generalized quantifier.
A finitary version of the "open game quantifier" might be constructed
as follows.
Again, we are on a game (G, \to, E, A, W, L, 0).
A quasistrategy for Eloise for this game is a set S of initial
segments of runs such that:

if (t_{0}, ..., t_{n}) in S and n > 0, then (t_{0},
..., t_{n1}) in S, and

if (t_{0}, ..., t_{n}) in S and t_{n} in E, then for
some t, (t_{0}, ..., t_{n}, t) in S, and

if (t_{0}, ..., t_{n}) in S and t_{n} in A, then for
every t satisfying t_{n} : t, (t_{0}, ..., t_{n},
t) in S.
Then the formula GAME t THETA (t)$ is the assertion that there exists a
quasistrategy S such that:

S has no infinite branches, and

for every maximal (t_{0}, ..., t_{n}) in S,
THETA(t_{n}) is true.
So presumably $\Game t W(t)$ asserts that Eloise can win the game.
Note: the (open) game quantifier GAME has a dual DGAME 
let's not go into that here.
For a survey of the transfinite theory, see the paper in MODELTHEORETIC
LOGICS by P. Kolaitis.
The Fundamental Theorem
The ZermeloGaleStewart Theorem
Let
(G, :, E, A, W, L, 0)
be a combinatorial game.
The following are equivalent.

It is true that 0 in WIN*.

Eloise has a winning strategy for the game.

Abelard does not have a winning strategy for the game.

It is true that GAME t W(t).

It is not true that DGAME t &neg W(t).
Comments.

The implications (2) ==> (3) and (4) ==> (5) are
obvious, but their converses are not: in infinitary games, the
converses may be false.

The implications (4) ==> (2) and (3) ==> (5)
require the Axiom of Choice.

The other implications are straightforward inductions.
A decent introduction to the finitary theory can be found in
G. Owen's GAME THEORY; for the infinitary theory, see
Y. Moschovakis's
book DESCRIPTIVE SET THEORY.
Now, to see what logicians can do with all this, turn to the page on
game theoretic semantics.
Escape links
Back to my research page
Back to my home page
Back to the USF Department of Mathematics Home Page

