proving two partizan games are equivalent - MathOverflow

proving two partizan games are equivalent

2010-01-16T21:27:02Z

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?

Answer by Richard Nowakowski for proving two partizan games are equivalent

2010-01-21T20:26:22Z

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.

Answer by David Speyer for proving two partizan games are equivalent

2010-01-21T20:31:27Z

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.

Answer by John Mangual for proving two partizan games are equivalent

2010-01-21T22:46:57Z

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.

Answer by Mark S. for proving two partizan games are equivalent

2013-01-10T23:06:33Z

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.