Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there any equivalent version of the Sprague-Grundy theorem (that states that every impartial game under the normal play convention is equivalent to nim) for partizan games?

More specifically, are there any "non-trivial" examples of partizan games that are known to be equivalent?

share|improve this question
add comment

4 Answers 4

In partizan theory, the theorem is: G=H if and only if G-H is a second player win.

A Nim position with two heaps of size 1 is equal to the Hackenbush position with one red and one blue edge each connected to the ground. Both are second player win positions and so are both equal to 0. They are not trivially equivalent since either player moving in Nim leaves a Next-player win game whereas Left playing in Hackenbush leaves a Right-win game and similarly Right plays to a Left-win game. In symbols, Nim: {$*$|$*$}=0; Hackenbush: {-1|1}=0.

share|improve this answer
add comment

I think the closest thing to the Sprague-Grundy theorem in the partizan normal-play case is the corollary of Theorem 69 in On Numbers and Games. Every short game* has a unique canonical/normal form where all "dominated options" are deleted and all "reversible options" have been replaced and all options are written in their canonical forms. For the games which happen to be impartial, their canonical forms are the standard forms for Nim heaps: $\left\{\left\{|\right\}|\left\{|\right\}\right\}$ for the Nim heap of size 1 (often denoted $*$), etc.

If you don't have ONAG at hand, you can read about dominated and reversible options in An Introduction to Conway's Games and Numbers. Their theorem 2.25 is essentially Theorem 69 from ONAG, but has a subtle error: it claims that there is a unique example in each equivalence class with no dominated or reversible options (as opposed to a good unique canonical choice).

Here is a counter-example: $\left\{ \left\{|\right\} | \right\}$ is $\left\{0|\right\}=1$ and has no dominated or reversible options. But $\left\{ \left\{*|*\right\} | \right\}=\left\{ \left\{\left\{\left\{|\right\}|\left\{|\right\}\right\}|\left\{\left\{|\right\}|\left\{|\right\}\right\}\right\} | \right\}$ is equivalent to $\left\{0|\right\}=1$, and it also has no dominated/reversible options.

*A game is short if it has only finitely many positions. The Sprague-Grundy theorem usually applies to the short impartial games, stating that they're each equivalent to a single finite Nim heap.

share|improve this answer
add comment

Partizan generalizations of Sprague-Grundy are the subject of Conway's book On Numbers and Games. His later work, Winning Ways for your Mathematical Plays with Berkelamp and Guy, gives examples of how to apply the theory to games that human beings might actually want to play. I'm afraid that it's been too long since I've read it to remember any nontrivial examples.

share|improve this answer
add comment

Partizan misere games have also been studied. See Misère canonical forms of partizan games. A misere game is where the last person to move loses rather than wins.

share|improve this answer
add comment

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.