Finite Two-person Deterministic Games
Impartial Games
Nimbers
Danny Sleator
Andrew's Leap, 2000
Games we discuss:
2 person
perfect information
alternating move
finite number of moves at each state
finite in length
Sometimes called "tree games", cause you can draw a tree.
Examples:
tic-tac-toe
connect-4
othello
nim
sprouts
take-away-1-2-3 (A row of 12 matches, and you can take
away 1 or 2 or 3 in your move. The goal is to take
the last match.)
chess (have to assume game draw declared when 50-move or
repetition occurs)
The two players will be White and Black (White goes first)
Example .....
The "natural outcome" of a game is the best outcome that
White (the first player) can achieve if he always makes
the best possible move.
It's easy to see how to compute the natural outcome of a game. Just
propogate the values up the tree. The leaves are labeled with the
outcome (say W,D,B for White wins, Draw, or Black wins). On nodes where
it's white to move, the node is labeled with the best of the nodes below
it from white's perspective. Similarly for black.
Impartial games
Some of the games discussed have the property that the set of moves
available in a position are not dependent on whose move it is, and the
winner is the one who makes the last move. Nim, sprouts, and
take-away-1-2-3 are like this. Games like this are called impartial
games. (There are "Mise're" versions of all these games that arise if
the goal is to get stuck with the last move. The elegant theory
developed below does not work for these games.)
You can think of an impartial game as simply a set. The set is in turn
a collection of sets, where each internal set is just the game resulting
from one of the moves of the first player. All of these sets are
finite. Let @ denote the game with no moves.
Alternatively, you can think of an impartial game as a tree. We say
that two games are equal (A=B) if the trees of the two games are
isomorphic. That is, you can draw the two trees so that they look
exactly the same by reordering the children at each node.
[Some of the the following definitions and theorems come from a handout
prepared by Dana Scott.]
The RANK of a game A, denoted |A| is just:
|A| = 1 + max |b| and |@| = 0
b in A
The rank is just the maximum number of moves that can occur in the game.
(Maybe the rank is used on some induction proofs....)
The VALUE of a game, denoted ||A|| is defined as follows:
||A|| = max -||b|| and ||@|| = -1
b in A
So the value of a position that is a loss is -1 and the value of a win
is 1.
The join of two games A and B is a new game. It is denoted A*B (Dana
uses A circle-plus B). The intuitive definition is as follows. A move
in A*B is made by picking one of A or B and making a move in that
game. So, for example, if the player makes a move in A, which leaves a,
then the game that results after the move in the joined game is a*B.
Here's a more formal definiton:
A*B = {a*B | a in A} union {A*b | b in B}
A*@ = A
@*B = B
The following theorems are easy to prove:
Theorem: A*B = B*A
Theorem: A*(B*C) = (A*B)*C
One of the main goals of the theory we develop is a way to characterize
useful properties of the join of two games knowing someting about the
two games. We start with some obvious things:
Theorem: (1) If ||A|| = -1 and ||B|| = -1 then ||A*B|| = -1
(2) If ||A|| = 1 and ||B|| = -1 then ||A*B|| = 1
(3) If ||A|| = -1 and ||B|| = 1 then ||A*B|| = 1
Proof: (1). We're trying to show that there's a winning strategy for
the second player in the joined game A*B. We can prove this by
induction on the rank of the games (i,j). Assume we've shown part (1)
for all pairs (i', j') where either i'* 0. In this case we
exhibit a winning strategy for the first player. This strategy is
simply to make a move that results in a position with nimber 0. This is
of course possible (because all nimbers less than the nimber of the
position are achievable, including 0). So after the move, the resulting
position has value -1 (by induction). This completes the proof of the
theorem. Q.E.D.
As I mentioned above, it's going to turn out that [A*B] = f([A],[B]).
That is, that the nimber of the join of two games is just a function of
the nimbers of the two parts. This is very important from a
computational point of view, because it means that if you can split a
game up and evaluate the nimbers of each part, you can compute the
nimber (and thus the value) of the whole game. The purpose of the
theory is to prove this fact about nimbers.
Lemma: [A] = [B] if and only if ||A*B|| = -1
Proof: Assume [A]=[B]. Consider A*B. No matter what move the first
player makes, the result is a position that is the join of two games
with differing nimbers. The value of this position is (by induction)
therefore 1. Similarly, if [A] != [B], then the first player can move
in the game with the largest nimber and reduce its nimber to be equal to
the nimber of the other game. This, by induction, is a lost position.
An alternative formulaton of this lemma is: [A]=[B] iff [A*B]=0.
We define EQUIVALENCE of games as follows. A ~ B (A is equivalent to B)
if for all games X the following holds:
||A * X|| = ||B * X||
It turns out that nimbers allow us to determine equivalence.
Theorem: A ~ B if and only if [A] = [B]
Proof: Let's first prove that A ~ B implies [A]=[B]. Choose X=A. Then
we have: ||A*A|| = ||B*A||. By the lemma, the left side of this is -1.
And again by the lemma the right side being -1 implies that [A]=[B].
The other direction follows because the lemma tells us that the value of
a game A*X only depends on the nimbers of A and X. Thus if [A]=[B] then
the value of A*X and B*X are the same for all X. Q.E.D.
The key thing we still need to be able to do is determine the nimber of
the join of two games from the nimber of the two games. For one thing,
it's not even clear that the nimber of the join is even a function of
the nimbers of the two games being joined. We'll prove this next.
Theorem: [A*B] is a function only of [A] and [B].
Proof: First we need a bit of notation. Let denote the nim game
with one row of k matches. As noted above [] = k for any k >= 0. So
this is a simple specific game with a specific nimber. Clearly for
these games, the theorem holds. Because there is a unique such game of
this class with a given nimber. So there's some function f(.,.)
satisfying this:
[***] = f(i, j)
We want to show, for all games A and B, that:
[A*B] = f([A], [B])
Consider this quantity:
[(A*B) * (<[A]>*<[B]>)]
If we can show that this is 0, then we know that:
[A*B] = [<[A]>*<[B]>] = f([A], [B])
Let's do this.
[(A*B) * (<[A]>*<[B]>)] =
= [A * B * <[A]> * <[B]>]
= [(A*<[A]>) * (B*<[B]>)]
Now [A] = [<[A]>]. So the left part of this has nimber 0.
The right part is similarly 0. Therefore the nimber of this join is
also 0. This completes the proof. Q.E.D.
It remains to compute f(i,j). Our final theorem tells how to do this.
Theorem: [***] = f(i, j) = i^j, where "^" denotes the bitwise
exclusive or operation.
Proof:
To prove this by induction, it sufficies to prove the following
assertion:
For any i,j, the minimum non-negative integer NOT in
the set {0^i,1^i,2^i...(j-1)^i, j^0, j^1, ... , j^(i-1)}
is i^j. (Here ^ denotes xor).
First of all, clearly i^j is not in this set. Let's show that any
number k less than i^j is in the set. The fact that k < i^j means that
the first place where k and i^j differ is on some bit where i^j is 1 and
k is 0. Because in this position i^j is a 1, either i is a 1 in that
position or j is. WLOG, assume it the 1 is in i. Now we're going to
decrease i to a new number i' so that this bit becomes 0. i' can be
chosen so that the bits below that can be anything we want. In
particular we can choose them so that i' ^ j obtains the desired value,
namely k. Q.E.D.
Note: The reason we had to go through all this convoluted stuff is
because the above construction does not work for arbitrary games. It
only works for simple nim piles, like . In general in a game A, it
will be possible to make moves whose nimber is any nimber less than [A],
but it will also in general be possible to make moves that have nimbers
greater than [A]. This causes any inductionp proof like that used in
the last proof to break down. At least that's the thinking that led to
this argument.
*