Indistinguishability quotient

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]


External links[edit]