Genus theory
In the mathematical theory of games, genus theory in impartial games is a theory by which some games played under the misère 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.
Unlike the Sprague–Grundy theory for normal play impartial games, genus theory is not a complete theory for misère play impartial games.
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 λ0 is the outcome class of a game under the misère play convention.
More specifically, to find g+, *0 is defined to have g+ = 0, and all other games have g+ equal to the mex of its options.
To find g−, *0 has g− = 1, and all other games have g− equal to the mex of the g− of its options.
λ1, λ2..., 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λ0λ1λ2....
*0 has genus value 0120. 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:
- The sum of any nimbers and any tame games
- The sum of any one game given its genus, any number of nim games *1, *2 or *3, and optionally one other nim game with nimber 4 or higher
- The sum of a restive game and any number of nim games of any size
In addition, some restive or restless pairs can form tame games, if they are equivalent. Two games are equivalent 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 affect equivalency.
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.
Reversible moves
It is important for further understanding of Genus theory, to know how reversible moves work. Suppose there are two games A and B, where A and B have the same options (moves available), then they are of course, equivalent.
If B has an extra option, say to a game X, then A and B are still equivalent if there is a move from X to A.
That is, B is the same as A in every way, except for an extra move (X), which can be reversed.
Types of games
Different games (positions) can be classified into several types:
- Nim
- Tame
- Restive
- Restless
- Half tame
- Wild
Nim
This does not mean that a position is exactly like a nim heap under the misère play convention, but classifying a game as nim means that it is equivalent to a nim heap.
A game is a nim game, if:
- it has a genus 01, 10, 22, 33...
- it has moves only to single nim heaps, i.e. move to a position *1, or *2, but not e.g. *x+*y (but see next point)
- it may also have moves to games which are not nim, provided they are not required to determine the genus, and those games each have at least one option to a nim game of the same genus
Tame
These are positions which we can pretend are nim positions (note difference between nim positions, which can be many nim heaps added together, and a single nim heap, which can only be 1 nim heap). A game G is tame if:
- it has a genus 01, 10, or 00, 11, 22, 33...
- all options of G are tame
- G may also have wild options (positions which are not tame or nim) if they do not affect the genus, and each option have reversible moves to tame games with genus g? and ?λ.
Note the moves to g? and ?λ may actually be the same option. ? means any number.
See also
References
- On Numbers and Games by John Horton Conway
- Winning Ways for Your Mathematical Plays by Elwyn Berlekamp, John Conway and Richard Guy.