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 λ₀ 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.

λ₁, λ₂..., 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 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:

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 0¹, 1⁰, 2², 3³...
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 0¹, 1⁰, or 0⁰, 1¹, 2², 3³...
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.

References

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