I.5: Classification of Simple Games (The Sprague-Grundy Theorem)

To achieve the classification I mentioned at the end of I.4, we’ll need a lemma, which has the added benefit of helping me sidestep the issue that I haven’t formally written out what a “position” (of a Simple game) is, anyway.

1. If the set of immediately reachable positions from G is {G1,G2,…} and Gi=Hi for all i, then G is equivalent to any position H where the set of immediately reachable positions is {H1,H2,…}.
Why? Let’s play G⊕H. If you move to Gi⊕H or G⊕Hi, I’ll move to Gi⊕Hi which is a P-position since Gi=Hi. Therefore, G⊕H is itself a P-position, and G=H (by I.4.4).

This lemma basically solidifies the fact that we only care about positions up to equivalence. It will allow us to prove what I’d call the birth of CGT: The Sprague-Grundy Theorem (independently proven by Sprague and Grundy during the 30s). In I.4, we showed that the single pile positions of Nim were pairwise inequivalent. Sprague and Grundy showed:

2. Every Simple game position is equivalent to a single pile of Nim.
Every complicated game of Nim, every game of Kayles (on a circle or in a line), every common game (like Chess) turned into a Simple game,… they’re all equivalent to [n] for some n. This doesn’t mean it’ll be easy to calculate which [n] a given position is equivalent to, but we can worry about that later.

Proof of the Sprague-Grundy theorem:
For clarity, we’ll prove it in the case where the game is “short”, so that there a finitely many reachable positions in a given game. Since Simple games are non-loopy, a given starting position ends up at a position with no available moves after at most some fixed number of moves. Therefore, by the lemma (or perhaps by definition), we can just think of a Simple game as a list of reachable positions, each of which is a list of reachable positions, etc. with empty lists (or [0]’s, since all P-positions are equivalent) at the bottom (you can think of this as a tree if you like). This permits some form of induction (structural induction on trees, regular induction on the maximum number of moves until the game ends, whatever you like).

Base case: If there are no available moves, it’s a P-position, which is equivalent to [0].

Induction step:
Suppose that every available move in G is equivalent to a single pile of Nim. By our lemma, G is equivalent to a game H in which the moves are to [n1],[n2],…. We will show that such a game is equivalent to [m]=[mex(n1,n2,…)] where mex means “the minimal excluded number: the least nonnegative integer that’s not one of the ni“.

To do this, we need to play H⊕[m]. If you move to [ni] in H where ni<m, then I can move to [ni] in [m] and leave you with the P-position [ni]⊕[ni]. If you move to [n] in [m], then since m is the least excluded number, n=ni for some i, and I can still move to [ni]⊕[ni]. Finally, if you move to [ni] in H where ni>m (remember it can’t be equal to m since m was excluded), then I can just move to [m]⊕[m] since [m] is a smaller pile than [ni]. Since I can always hand you a P-position no matter what you do, H⊕[m] must be a P-position, and H=[m], as desired (since G=H). ✓

For those who happen to know about the ordinals, this proof works exactly the same way for Simple games that are not “short”, but then we’d need Nim “piles” for every ordinal.

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