What game are we analyzing?
Consider a finite directed acyclic graph of positions. An edge is a legal move; either player has the same moves from a position, and the player unable to move loses. These are the finite impartial, normal-play assumptions. They rule out infinite play and do not cover games with player-dependent moves or different terminal rules.
Definition 5.1.1
(Mex and the value of a position)
For a finite set of nonnegative integers, is its smallest missing nonnegative integer; in particular . Define the value of a position recursively by
A terminal position has value zero. Acyclicity lets us define all values backwards.
Zero values and winning moves
Theorem 5.1.2
(Value zero means the mover loses)
In a finite impartial normal-play game, a position of value zero is a loss for the player to move with best play, and a position of positive value is a win: the player to move can move to a position of value zero.
Proof
(Backward induction on the game graph)
A position with value zero has no option of value zero, because zero is missing from its option values. A position with positive value has an option of value zero, because every nonnegative integer smaller than its mex must occur. Now induct backwards from the terminal positions, which have value zero and no move, so the player to move loses. If a position has value zero, all its options have positive value, so by induction each is a win for the player who moves next, and the mover loses. If it has positive value, the mover can move to an option of value zero, which by induction is a loss for the player to move there. This uses the stated normal-play rule.
Counterexample mode
Mex is not a move count
In a pile where a legal move removes one or two tokens, a pile of three has two legal moves, to piles of two and one. Their values are and , so its value is . Counting legal moves alone does not determine the value.
Why independent games combine by xor
Definition 5.1.3
(Sum of games)
For positions , their sum means a move changes exactly one component by one of its legal moves. The symbol on nonnegative integers denotes bitwise xor.
Theorem 5.1.4
(The xor rule for sums)
For positions of finite impartial normal-play games,
Proof
(Induction on the remaining play length)
Induct on the sum of the maximum remaining play lengths. Put , and . An option changing has value by induction, where because is missing from the option values of ; hence that option cannot have value . The same holds for an option changing .
Now take any integer with and put . At the highest bit where and differ, has and has . Since , at least one of has a at that bit. Suppose it is ; then . The definition of mex guarantees an option of with value , and the resulting sum has value . The case where the chosen component is is identical. Thus no option has value , while every value below occurs, so their mex is .
Proof X-ray
The two parts of a mex proof
The proof must show two things about the same number : that no option of the sum has value , and that every smaller value occurs. The first uses only that is missing from the option values of and from those of , the "not in the set" half of the mex definition. The second is the non-routine step: the highest bit where and differ picks a component whose value can be lowered by xoring with , and the "every smaller value occurs" half of the mex definition then supplies the option. Xor is used exactly there, in locating a component with a at that bit; the argument has no counterpart for ordinary addition of values. The induction closes because each option shortens the remaining play.
The proof applies repeatedly to finitely many components. It establishes the game value, not merely the winner. A nonzero xor permits a move to xor zero; a zero xor leaves only nonzero-xor moves.
Common mistake
(Adding values instead of xoring them)
Two piles of one token each have values and . Their sum position has value : the first player moves to and the second takes the last token, so the first player loses. Adding the values would give and wrongly suggest a win. Xor is the combining rule.
A subtraction game
Let a pile contain tokens, and allow removing or tokens when available.
Theorem 5.1.5
(Values of the remove-one-or-two game)
In this game, for every .
Proof
(Induction on the pile size)
The base values are and . For , the options have, by induction, the two residues modulo other than ; the mex definition then gives the remaining residue as .
This also establishes the values used in the counterexample above.
Worked example 5.1.6
(The first values by mex)
Position is terminal, so . Position has the single option , so . Position has options with values , so . Position has options with values , so . Position has options with values , so . Position has options with values , so . Position has options with values , so . The sequence is . The terminal case is the only one with no options, which is why its value is the mex of the empty set.
Worked example 5.1.7
(Two piles of sizes 4 and 8)
For two such piles of sizes and , the values are and , so their xor is . The player to move wins. Removing from the first pile gives with values ; removing from the second gives with values . Both moves give xor zero. The other legal first moves, to or , give nonzero xor, so these are all the winning first moves.
Worked example 5.1.8
(Three piles, one of value zero)
Take piles in the same game. The values are and their xor is , so the player to move wins. To make the xor zero, a pile must be moved to a position whose value equals the xor of the other two values: for the pile of (value ) the target is , reached by removing one token to get ; for the pile of (value ) the target is , reached by removing two tokens to get . The results and have values and . The pile of has value and offers no winning move: moving it to or gives xor or , both nonzero.
Exercises with solutions
Quick check
(What is the value of an empty pile?)
It has no options.
Solution · Answer
, the mex of the empty set.
Quick check
(What is the value of a pile of in this subtraction game?)
Use the formula for .
Solution · Answer
.
Quick check
(Who wins from under the stated rule?)
Compute both values.
Solution · Answer
Both values are zero, so the xor is zero and the player to move loses with best play.
Quick check
(Can the zero-value conclusion be transferred without proof to a rule in which the player unable to move wins?)
Which step of the induction used the terminal rule?
Solution · Answer
No. That changes the terminal condition, so the normal-play induction no longer applies as stated.