Indistinguishability quotient

The Sprague-Grundy theory of normal-play impartial combinatorial games generalizes to misere play via a local construction known as the indistinguishability quotient.

Suppose $A$ is a set of impartial combinatorial games that is closed in both of the following senses:

(1) Additive closure: If $G$ and $H$ are games in $A$, then their disjunctive sum $G + H$ is also in $A$.

(2) Hereditary closure: If $G$ is a game in $A$ and $H$ is an option of $G$, then $H$ is also in $A$.

Next, define on $A$ the indistinguishability congruence ≈ that relates two games $G$ and $H$ if for every choice of a game $X$ in $A$, the two positions $G+X$ and $H+X$ have the same outcome (i.e., are either both first-player wins in best play of $A$, or alternatively are both second-player wins).

One easily checks that ≈ is indeed a congruence on the set of all disjunctive position sums in $A$, and that this is true regardless of whether the game is played in normal or misere play. The totality of all the congruence classes form the indistinguishability quotient.

If $A$ is played as a normal-play (last-playing winning) impartial game, then the congruence classes of $A$ are in one-to-one correspondence with the nim values that occur in the play of the game (themselves determined by the Sprague-Grundy theorem).

In misere play, the congruence classes form a Monoid#Commutative monoid, instead, and it has become known as a misere quotient.

See also

• Sprague–Grundy theorem
• Genus theory

References

• Plambeck, Thane E. (2005-07-19). "Taming the Wild in Impartial Combinatorial Games" (PDF). Integers: Electronic Journal of Combinatorial Number Theory (PDF) 5 (G05). Retrieved 2010-12-21.

External links

• http://miseregames.org/