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.

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/

This article is issued from Wikipedia - version of the Tuesday, June 17, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Indistinguishability quotient

See also

References

External links