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

λ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:

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

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:

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:

Note the moves to g? and ?λ may actually be the same option. ? means any number.

See also

References

This article is issued from Wikipedia - version of the Tuesday, November 17, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.