Tato stránka obsahuje informace, které jsou nezbytné pro pochopení a hraní kombinatorických her.
Kombinatorické hry můžeme definovat jako hry dvou hráčů, kteří mají o hře v každém okamžiku k dispozici úplné informace a provádějí tahy bez jakéhokoli prvku náhody. Hra se skládá z (obvykle konečné) množiny pozic, přičemž se hráči střídají v tazích, kterými se snaží dosáhnout pro ně výhodné pozice. Po dosažení konečné pozice (angl. terminal position), je jeden hráč prohlášen za vítěze a druhý za poraženého. Konečná pozice je obvykle taková pozice, ze které neexistují žádné další tahy.
Existují dva hlavní typy pravidel, které popisují podmínky vítězství. Podle normálního pravidla (angl. normal play rule) vyhrává hráč, který provedl poslední tah hry. Naopak při uplatnění misère pravidla (angl. misère play rule ) takový hráč prohrál.
Kombinatorické hry je dále možné rozdělit do dvou kategorií. Nestranné hry (angl. impartial games) se vyznačují tím, že oba hráči mají z jakékoli pozice k dispozici stejnou množinu tahů. Naopak v případě partyzánských her (angl. partyzan games), může být množina tahů z konkrétní pozice pro hráče rozdílná. Tato stránka obsahuje pouze nestranné kombinatorické hry, hrané podle normálního pravidla.
Odebírací hry jsou podmnožinou her kombinatorických. Z hromádky žetonů hráči střídavě žetony odebírají a pokud hráč ve svém tahu již nemůže žádný žeton odebrat, prohrává. Kolik žetonů může hráč ve svém tahu odebrat je nutné předem specifikovat v pravidlech hry. Na těchto stránkách můžete najít tyto typy odebíracích her:
Normální: Hráči odebírají žetony dle odebírací množiny (množina celých čísel, které reprezentují, kolik žetonů může hráč odebrat). Hráč, který ve svém tahu nemůže táhnout, prohrává.
Dim: Hráč může odebrat c žetonů z hromádky n žetonů, pokud je c dělitelem n, včetně 1 a n. Hráč, který ve svém tahu nemůže táhnout, prohrává.
Nim: Hráč může odebrat libovolný počet žetonů (alespoň jeden). Hráč, který ve svém tahu nemůže táhnout, prohrává.
Aliquot: Hráč může odebrat c žetonů z hromádky n žetonů, pokud je c dělitelem n. Nemůže však odebrat n žetonů. Hráč který ve svém tahu nemůže táhnout, prohrává.
Sudá/lichá: Hráč může odebrat sudý počet žetonů, pokud to není celá hromádka. Může ale také odebrat lichý počet žetonů v případě, že odebírá celou hromádku. Hráč, který ve svém tahu nemůže táhnout, prohrává.
Polovina: Hráč může odebrat maximálně polovinu žetonů. Hráč, který ve svém tahu nemůže táhnout, prohrává.
Jednotlivé pozice v kombinatorické hře můžeme dělit na P-pozice a N-pozice. P-pozice jsou takové, které jsou optimální pro hráče, který zrovna dokončil svůj tah. N-pozice jsou naopak ty, které jsou vítězné pro hráče, který má aktuálně svůj tah provést. Vítězné v tomto případě znamená, že hráč vyhraje, pokud bude i nadále provádět optimální tahy.
P-pozice a N-pozice jsou dále definovány pomocí těchto vlastností:
K určení typu pozice můžeme využít následující algoritmus:
Kombinatorické hry, které jsme již popsali, lze definovat také pomocí orientovaných grafů. Pozice, ve kterých se hra nachází jsou v grafu reprezentovány jeho vrcholy, zatímco hrany grafu reprezentují jednotlivé tahy.
Odebírací hry na orientovaných grafech můžeme popsat pomocí P-pozic a N-pozic. Kromě toho je však můžeme analyzovat funkcí Sprague-Grundy.
Definice: g(x) = min{ n ≥ 0 : n ≠ g(y) : y ∈ F(x) }
Tato definice říká, že g(x) je nejmenší nezáporné celé číslo, které nepatří do množiny hodnot Sprague-Grundy funkce následovníků x. Pro ty vrcholy grafu, které reprezentují konečné pozice, platí g(x) = 0. Vrchol x totiž nemá žádné následovníky, F(x) = ∅. Dále platí, že pokud vrchol x následují pouze vrcholy konečné, pak g(x) = 1. Stejně tak můžeme rekurzivně najít SG hodnoty pro všechny zbylé vrcholy.
Znalost hodnot SG funkce pro jednotlivé vrcholy grafu nám pomáhá analyzovat konkrétní hru, kterou graf reprezentuje. Pozice x, pro které platí g(x) = 0, jsou P-pozice. Všechny ostatní jsou N-pozice.
Velice známou odebírací hrou je hra Nim. Hra se skládá z libovolného počtu hromádek, kde v každé hromádce může být rovněž jakýkoli počet žetonů. Hráči se střídají v tazích, při kterých si vyberou jednu z hromádek a odeberou z ní žetony. Ve svém tahu může hráč odebrat žetony pouze z jedné hromádky, ale žetonů může odejmout kolik chce (alespoň 1 žeton). Vyhrává hráč, který vezme poslední žeton.
Hru Nim tedy můžeme klidně hrát pouze s jednou hromádkou. Optimální tah je v tu chvíli odebrat všechny žetony najednou. Pokud hru hrajeme se dvěma hromádkami, je pro hráče na tahu výhodné přenést hru do pozice, kdy obsahují obě hromádky stejný počet žetonů. Druhý hráč pak nemá jinou možnost, než svým tahem jednu z hromádek zmenšit. První hráč může opět velikost hromádek vyrovnat. Tímto způsobem mohou hrát tak dlouho, dokud první hráč nevyrovná hromádky do stavu, ve kterém budou obě prázdné. Pozice (0,0) je totiž konečná, tudíž se první hráč stal vítězem.
S rostoucím počtem hromádek se hra nevyhnutelně stává komplikovanější a méně přehlednou. Rozhodnout, jestli je např. pozice (11,5,12,20) P-pozice, nebo N-pozice je na první pohled velmi obtížné. Určit typ pozice nám pomáhá tzv Nim-Součet (angl. Nim-sum).
Definice: Nim-Součet dvou nezáporných, celých čísel, je jejich součet v binárním tvaru, kde ale zároveň nepřenášíme jedničky do vyšších řádů. Tato operace se také nazývá XOR, neboli exkluzivní disjunkce.
Stručně řečeno, pokud provedeme operaci XOR mezi všemi hromádkami, získáme číslo, které nám říká, jestli se jedná o P-pozici, nebo N-pozici. Pokud je výsledné číslo 0, jedná se o P-pozici, v opačném případě o N-pozici.
Z jednotlivých kombinatorických her můžeme tvořit složitější hry podle následujících pravidel. Mějme několik her a každé z nich přidělme počáteční pozici. Hráči se střídají v tazích, při kterých si hráč vybere jednu z her a provede v ní legální tah. Ve zbylých hrách neproběhne žádná změna. Hráči hrají dokud není ve všech hrách dosaženo konečné pozice (další tah není možný). Hráč, který provede poslední tah, vyhrál. Hra, kterou tímto způsobem vytvoříme je disjunktivní součet (angl. disjunctive sum) jednotlivých her.
Následující věta nám říká, jak můžeme z SG funkcí jednotlivých her získat SG funkci výsledné součtové hry.
Věta: Sprague-Grundy funkce součtu kombinatorických her (jejich grafů), je nim-součtem hodnot SG funkce her, ze kterých se skládá.
Nim součet je vlastně operace XOR mezi jednotlivými SG hodnotami sčítaných her. Stejně jako u hry Nim platí, že pokud je součet roven nule, jedná se o P-pozici. Pokud součet není nulový, jedná se o N-pozici.