I.6: A Strategy for Nim

The Sprague-Grundy theorem in I.5 wasn’t known when Bouton first solved Nim, but we can use it to make solving Nim very approachable. We can begin by analyzing how Nim piles below [8] behave under ⊕.

First, remember [1,2,3]=([1]⊕[2])⊕[3] was a P-position, so [1]⊕[2]=[3]. Now consider [1,4,5]: If the next player to move doesn’t do something stupid (eliminate a pile or make two piles equal), then we can move to [1,2,3]. Thus, [1]⊕[4]=[5]. Also, if the next player to move in [2,4,6] doesn’t do something stupid, then we can either move to [1,4,5] or [1,2,3] so [2]⊕[4]=[6].

Finally, consider [1,2,4,7]. Eliminating a pile invites the opponent to make [1,2,3] or [1,4,5] or [2,4,6]. Making two piles equal invites the opponent to make the position something like [a,a,b,b], which is an obvious P-position. [1,2,3,7] and [1,2,4,3] invite [1,2,3], [1,2,4,5] invites [1,4,5], and [1,2,4,6] invites [2,4,6]. Thus, [1]⊕[2]⊕[4]=[7]. Therefore, for the powers of 2: 1,2,and 4, we know that ⊕ acts like addition for distinct powers of 2.

By writing things as sums of powers of 2, we can use this to calculate all of the combinations of Nim piles no bigger than [7]: e.g. [3]⊕[7]=([1]⊕[2])⊕([1]⊕[2]⊕[4])=([1]⊕[1])⊕([2]⊕[2])⊕[4]=[4]. If we conjecture that this pattern continues (distinct powers of 2 add normally), then ⊕ would be equivalent to bitwise xor. We can use induction to prove this is correct.

1. [m]⊕[2n]=[m+2n] if m<2n
Why?
Suppose, for sake of induction, that we have shown the claim for all lower n and for all lower m with the same value of n. If m=0 the claim is obvious. Otherwise, we must show that [m,2n,m+2n] is a P-position by showing how to respond to any move. A move to [m,2n,k] with k≥2n invites a move to [k-2n,2n,k] which is a P-position by inductive hypothesis. A move to [m,2n,k] or [m,k,m+2n] with k<2n invites a move to [m,xor(m,k),k] (modulo ordering), which is a P-position by expanding everything out as powers of two (by inductive hypothesis) and cancelling like powers. ✓

If you’re familiar with ordinals, this proof works verbatim in that generalized situation, although you have to invoke a special version of Cantor Normal Form (note that under ordinal exponentiation, 2ω=ω) to write an ordinal uniquely as a sum of distinct ordinal powers of 2.

With fact 1 in hand, a strategy for normal-play Nim presents itself, and can be described in a variety of ways. One way would be “write the pile sizes in base 2, add them up but with no carrying, and then make a move that changes precisely those bits that were 1 when you added things up”. If there were no such move, then all of the moves would be to N-positions, which would contradict either fact 1 or the Sprague-Grundy theorem. An explicit way to find such a move is essentially “Lemma 2” in this Wikipedia section.

So we now know that every Simple game is really a pile of Nim, and how to combine piles of Nim/play Nim perfectly. We haven’t solved every Simple game, though. For instance, if we want to play Kayles perfectly, we need to know “what Nim pile is n pins in a row equivalent to?” for all n. That’ll be covered in the next post.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s