proving two partizan games are equivalent - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T05:39:42Z http://mathoverflow.net/feeds/question/12020 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/12020/proving-two-partizan-games-are-equivalent proving two partizan games are equivalent serargus 2010-01-16T21:27:02Z 2013-01-10T23:18:34Z <p>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?</p> <p>More specifically, are there any "non-trivial" examples of partizan games that are known to be equivalent?</p> http://mathoverflow.net/questions/12020/proving-two-partizan-games-are-equivalent/12562#12562 Answer by Richard Nowakowski for proving two partizan games are equivalent Richard Nowakowski 2010-01-21T20:26:22Z 2010-01-21T20:26:22Z <p>In partizan theory, the theorem is: G=H if and only if G-H is a second player win. </p> <p>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: {$<em>$|$</em>$}=0; Hackenbush: {-1|1}=0.</p> http://mathoverflow.net/questions/12020/proving-two-partizan-games-are-equivalent/12563#12563 Answer by David Speyer for proving two partizan games are equivalent David Speyer 2010-01-21T20:31:27Z 2010-01-21T20:31:27Z <p>Partizan generalizations of Sprague-Grundy are the subject of Conway's book <em>On Numbers and Games</em>. His later work, <em>Winning Ways for your Mathematical Plays</em> 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.</p> http://mathoverflow.net/questions/12020/proving-two-partizan-games-are-equivalent/12581#12581 Answer by John Mangual for proving two partizan games are equivalent John Mangual 2010-01-21T22:46:57Z 2010-01-21T22:46:57Z <p>Partizan <em>misere</em> games have also been studied. See <a href="http://front.math.ucdavis.edu/0703.5565" rel="nofollow">Misère canonical forms of partizan games</a>. A misere game is where the last person to move <em>loses</em> rather than wins.</p> http://mathoverflow.net/questions/12020/proving-two-partizan-games-are-equivalent/118585#118585 Answer by Mark S. for proving two partizan games are equivalent Mark S. 2013-01-10T23:06:33Z 2013-01-10T23:18:34Z <p>I think the closest thing to the Sprague-Grundy theorem in the partizan normal-play case is the corollary of Theorem 69 in <em><a href="http://en.wikipedia.org/wiki/On_Numbers_and_Games" rel="nofollow">On Numbers and Games</a></em>. 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: <code>$\left\{\left\{|\right\}|\left\{|\right\}\right\}$</code> for the Nim heap of size 1 (often denoted $*$), etc.</p> <p>If you don't have ONAG at hand, you can read about dominated and reversible options in <a href="http://arxiv.org/abs/math/0410026v2" rel="nofollow"><em>An Introduction to Conway's Games and Numbers</em></a>. Their theorem 2.25 is essentially Theorem 69 from ONAG, but has a subtle error: it claims that there is a <em>unique</em> example in each equivalence class with no dominated or reversible options (as opposed to a good unique canonical choice). </p> <p>Here is a counter-example: <code>$\left\{ \left\{|\right\} | \right\}$</code> is <code>$\left\{0|\right\}=1$</code> and has no dominated or reversible options. But <code>$\left\{ \left\{*|*\right\} | \right\}=\left\{ \left\{\left\{\left\{|\right\}|\left\{|\right\}\right\}|\left\{\left\{|\right\}|\left\{|\right\}\right\}\right\} | \right\}$</code> is equivalent to <code>$\left\{0|\right\}=1$</code>, and it <em>also</em> has no dominated/reversible options.</p> <p>*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.</p>