In combinatorial game theory, and particularly in the theory of impartial games in misère play, an indistinguishability quotient is a commutative monoid that generalizes and localizes the Sprague–Grundy theorem for a specific game's rule set. In the specific case of misere-play impartial games, such commutative monoids have become known as misere quotients.
Example: Misere Nim variant Suppose the game of Nim is played as usual with heaps of objects, but that at the start of play, every heap is restricted to have either one or two objects in it. In the normal-play convention, players take turns to remove any number of objects from a heap, and the last player to take an object from a heap is declared the winner of the game; in Misere play, that player is the loser of the game. Regardless of whether the normal or misere play convention is in effect, the outcome of such a position is necessarily of one of two types:
N The Next player to move has a forced win in best play; or P The Previous player to move has a forced win. We can write down a commutative monoid presentation for the misere quotient of this 1- and 2-pile Nim game by first recasting its conventional nimber-based solution into a multiplicative form, and then modifying that slightly for misere play.
Normal-play analysis The nimbers that occur in the normal play of such positions are *0, *1, *2, and *3.
These four nim values combine according to the Klein four-group:
+ ∗ 0 ∗ 1 ∗ 2 ∗ 3 ∗ 0 ∗ 0 ∗ 1 ∗ 2 ∗ 3 ∗ 1 ∗ 1 ∗ 0 ∗ 3 ∗ 2 ∗ 2 ∗ 2 ∗ 3 ∗ 0 ∗ 1 ∗ 3 ∗ 3 ∗ 2 ∗ 1 ∗ 0 {\displaystyle {\begin{array}{c|ccc}+&\ast 0&\ast 1&\ast 2&\ast 3\\\hline \ast 0&\ast 0&\ast 1&\ast 2&\ast 3\\\ast 1&\ast 1&\ast 0&\ast 3&\ast 2\\\ast 2&\ast 2&\ast 3&\ast 0&\ast 1\\\ast 3&\ast 3&\ast 2&\ast 1&\ast 0\end{array}}}
The Klein four-group is also defined by the commutative group presentation
V = ⟨ a , b ∣ a 2 = b 2 = 1 ⟩ {\displaystyle \mathrm {V} =\langle a,b\mid a^{2}=b^{2}=1\rangle } . The elements of V = { 1 , a , b , a b } {\displaystyle \mathrm {V} =\{1,a,b,ab\}} can be thought of as in one-to-correspondence with the nim values
{ ∗ 0 , ∗ 1 , ∗ 2 , ∗ 3 } {\displaystyle \{\ast 0,\ast 1,\ast 2,\ast 3\}} that occur in the play of this simplified Nim game; they combine exactly in the same way. So far, this formal introduction of the Klein four-group has added nothing new to the conventional analysis of 1- and 2-pile Nim using nimbers and nim-addition. Instead, we have merely recast the theory into a multiplicative form.
Misere-play analysis The advantage of the multiplicative form is that it allows us to write down a similar solution for the misere quotient of Nim played with heaps of size one and two only. We introduce the commutative monoid presentation
M = ⟨ a , b ∣ a 2 = 1 , b 3 = b ⟩ . {\displaystyle \mathrm {M} =\langle a,b\mid a^{2}=1,\ b^{3}=b\rangle .}
whose six elements are { 1 , a , b , a b , b 2 , a b 2 } . {\displaystyle \{1,a,b,ab,b^{2},ab^{2}\}.}
The solution to the correct play of misere Nim was already fully described by Bouton in 1902. In the final sentence of that paper, Bouton writes that in misere Nim, "the safe combinations are the same as before, except that an odd number of piles, each containing one, is now safe [ie, is an P-position], while an even number of ones is not safe [ie, is an N-position]." The misere quotient formulation above is easily seen to be equivalent in the case of Nim played with heaps of size one and two only.
… excerpt ends here. Continue reading the full article.
