Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.

What does the equivalence relation thus defined tells us about a certain game? What are some specific uses of the theorem (besides making the calculation of N and P positions easier)?

share|improve this question
    
Cross-posted on mathoverflow. –  Martin Brandenburg Apr 26 '12 at 13:14

1 Answer 1

Equivalence

Two (optionally impartial) normal-play combinatorial games (plus some assumptions I'm sweeping under the rug) $G$ and $H$ are equivalent exactly when $G+J$ has the same winner as $H+J$ for all (impartial) games $J$, where the plus sign here represents the act of combining games; $A+B$ means "make a new game where on your turn you can make a move in either summand ($A$ or $B$) if you have a move there".

Therefore, the equivalence class tells you just enough information to determine who wins every combination of that game with another normal-play combinatorial game. Turning this around, the equivalence relation lets us throw out irrelevant things like "wording of the rules" or "differences in imperfect play".

The other important fact about this equivalence relation is a theorem that states "if you replace all of the positions you can move to with equivalent ones, the new game is equivalent to the original one". That's important to make sure you can ignore differences between equivalent games in all contexts.

Sprague-Grundy

Sprague-Grundy tells us that in the impartial case, the only equivalence classes are the equivalence classes of single piles of nim, called nimbers. This tells us that for the purposes of seeing who wins combinations, there's a relatively tidy bunch of equivalence classes. If you want to know how to play some impartial game in combinations, all you need to know is which nimber is it equivalent to (and the nimbers for the things you're combining it with). This is a surprising result in that there might have been tons of different games, but for the purposes of combinations, everything is like a single pile of Nim (and all $\mathcal{P}$ positions are equivalent).

As far as I know, the specific uses of the theorem are essentially what you said, making the calculations of $\mathcal{N}$ and $\mathcal{P}$ positions easier. This is only really helpful with games that break up into combinations of smaller ones, like octal games.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.