Genus theory

Genus theory in impartial games is a theory by which some games played under the misere play convention can be analysed, to predict the outcome class of games.

Genus theory was first published in the book On Numbers and Games, and later in Winning Ways for Your Mathematical Plays Volume 2.

Genus of a game

The genus of a game is defined using the mex (minimum excludant) of the options of a game.

g+ is the grundy value or nimber of a game under the normal play convention.

g- or lambda₀ is the outcome class of a game under the misere play convention.

More specifically, to find g+, *0 is defined to have g+ = 0, and all other games has g+ equal to the mex of its options.

To find g-, *0 has g- = 1, and all other games has g- equal to the mex of the g- of its options.

lambda₁, lambda₂..., is equal to the g- value of a game added to a number of *2 nim games, where the number is equal to the subscript.

Thus the genus of a game is g^{lambda₀lambda₁lambda₂...}.

*0 has genus value 0¹²⁰. Note that the superscript continues indefinitely, but in practice, a superscript is written with a finite number of digits, because it can be proven that eventually, the last 2 digits alternate indefinitely.

Outcomes of sums of games

It can be used to predict the outcome of:

• Any one game given its genus
• The sum of any nimbers and any tame games
• The sum of any one game given its genus, and any number of nim games *1, *2 or *3.
• The sum of any one game given its genus, any number of nim games *1, *2 or *3, and one other nim game with nimber 4 or higher
• The sum of a restive game and any number of nim games

In addition, some restive or restless pairs can form tame games, if they are of the same species. Two games are of the same species if they have the same options, where the same options are defined as options to equivalent games. Adding an option from which there is a reversible move does not change the species of a game.

Some restive pairs, when added to another restive game of the same species, are still tame.

A half tame game, added to itself, is equivalent to *0.

See Also

Sprague–Grundy theorem

Indistinguishability quotient

References

• On Numbers and Games by John Conway
• Winning Ways for Your Mathematical Plays By Elwyn Berlekamp, John Conway and Richard Guy.