3
$\begingroup$

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?

$\endgroup$

4 Answers 4

4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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 Berlekamp 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.

$\endgroup$
1
  • 1
    $\begingroup$ @Mark S, I knew there were other Mark Ss on MO, but I'm pleasantly surprised there's another who would be looking at a CGT question. Hello. $\endgroup$
    – Mark S.
    Apr 23, 2019 at 21:21
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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