Kombinatorická teorie her

V teorii jsou dva hráči, kteří se nazývají levá a pravá strana. Hra je něco, co umožňuje levici a pravici provádět tahy do jiných her. Například v šachové hře je obvyklé výchozí rozestavení. Lze však také uvažovat o šachové partii po prvním tahu jako o jiné hře s jiným nastavením. Každá pozice se tedy také nazývá hra.

Hry mají zápis {L|R}. L {\displaystyle L} jsou hry, do kterých se může levý hráč přesunout. R {\displaystyle R} jsou hry, do kterých se může přesunout pravý hráč. Pokud znáte šachovou notaci, pak je obvyklým šachovým uspořádáním hra

Tečky "..." znamenají, že existuje mnoho tahů, takže nejsou zobrazeny všechny.

Šachy jsou velmi složité. Je lepší myslet na jednodušší hry. Například Nim je mnohem jednodušší na přemýšlení. Nim se hraje takto:

1. Je zde nula nebo více hromádek žetonů.
2. V jednom tahu si hráč může vzít z jedné hromádky tolik žetonů, kolik chce.
3. Hráč, který nemůže provést tah, prohrává.

Nejjednodušší hra Nim začíná bez počítadel! V takovém případě se žádný z hráčů nemůže hýbat. To je znázorněno jako {|}. Obě strany jsou prázdné, protože žádný z hráčů se nemůže pohnout. Hráč, který je na řadě jako první, se nemůže pohnout, a proto prohraje. V CGT se často píše {|} jako symbol 0 (nula).

Další nejjednodušší hra má pouze jednu hromádku s jedním počítadlem. Pokud jde levý hráč jako první, musí si vzít počítadlo a pravý hráč nemá žádný tah ({|} nebo 0). Pokud místo toho táhne jako první pravá strana, levá strana už nebude mít žádné tahy. Levá i pravá strana tedy mohou provést tah na 0. Ten se zobrazí jako {{|}|{|}}, neboli {0|0}. Vyhrává hráč, který provede tah jako první. Hry rovnající se {0|0} jsou velmi důležité. Zapisují se symbolem * (hvězdička).