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 model-construction 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⁰ = WIN(Ø), WIN^x = WIN(UNION_{z < x}WIN^z) WIN* = UNION_xWIN^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₀, t₁, ...) from G such that:

t₀ = 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₀, t₁, ...), 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₀, ..., t_n) in S and n > 0, then (t₀, ..., t_n-1) in S, and
if (t₀, ..., t_n) in S and t_n in E, then for some t, (t₀, ..., t_n, t) in S, and
if (t₀, ..., t_n) in S and t_n in A, then for every t satisfying t_n :- t, (t₀, ..., 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₀, ..., 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 MODEL-THEORETIC LOGICS by P. Kolaitis.

The Fundamental Theorem

The Zermelo-Gale-Stewart 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