imported>Tc14Hd: Added short description

2024-07-24T13:31:14Z

Added short description

New page

{{Short description|Mathematical theory of misère games}}
{{multiple issues|
{{confusing|date=March 2009}}
{{more citations needed|date=January 2019}}}}

In the mathematical [[game theory|theory of games]], '''genus theory''' in [[impartial game]]s is a theory by which some games played under the [[misère play convention]] can be analysed, to predict the [[outcome (game theory)|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 theorem|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 (mathematics)|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....

<nowiki>*</nowiki>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==
* [[Indistinguishability quotient]]

==References==
* ''[[On Numbers and Games]]'' by [[John Horton Conway]]
* ''[[Winning Ways for Your Mathematical Plays]]'' by Elwyn Berlekamp, John Conway and [[Richard K. Guy|Richard Guy]].

[[Category:Combinatorial game theory]]

Genus theory - Revision history

imported>Tc14Hd: Added short description