Jump to content

Indistinguishability quotient

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Ronald Ping Man Chan (talk | contribs) at 02:24, 22 February 2009. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

For an impartial game under the misere convention, finding the indistinguishability quotient of all the positions in a game makes it possible to predict the outcome of the sum of any number of games(positions) in a game.

The indistinguishability quotient of a game is expressed as the product of a number of symbols. Usually, the the quotient of games is found bottom up, with quotients for subsequently larger positions found.

When a position cannot be expressed as the sum of other smaller positions, a new symbol is created to represent it. Other positions which can be expressed as a sum of other positions is given a quotient that is the product of all the positions that it can be expressed as. A position can be expressed as a sum of other positions if it is equivalent (see Sprague-Grundy theorem).

A set of equations with equivalent quotients is also kept to keep the quotients shorter. For example, with many misere games, 2+2+2=2 is true. Then if 2 is assigned a quotient of a, the equation can be expressed as a3=a.

Finally, a kernel of quotients which are losing positions is kept.

With this information, the outcome of any sum of games can be found by multiplying the quotient of each individual game together, simplifying with the equations found, and looking up whether the quotient is in the kernel.


See also

Sprague-Grundy theorem

Genus Theory