Některé nestranné kombinatorické hry pro dva hráče
Kombinatorické hry jsou 1) hrami pro dva hráče (levý a pravý) s úplnou informací, bez náhody (všechny možné tahy jsou dopředu známy). 2) hráči se v tazích pravidelně střídají a začíná se v nějakém základním postavení (předem dohodnutá pozice, konfigurace). Hra je určena všemi možnými pozicemi. Hráč se nemůže svého tahu vzdát. 3) Pokud pravidla hry nerozlišují hráče, hru nazýváme absolutně nestrannou, v opačném případě partyzánskou. 4) hra končí po konečném počtu tahů. Hráč, který táhnul jako poslední (konec hry), vyhrál. Hráč, který nemá pravidly povolený tah, prohrál. Kdo bude začínat se může určit třeba losem.
Deset fazolí
Základní postavení: Na hromádce je deset fazolí.
Pravidla: Tahem je odebrání 1 nebo 2 fazole z hromádky.
Koncová pozice, vyhrává: hráč, který odebere poslední fazoli.
Přičítání čísel do sta
Základní postavení: Číslo nula.
Pravidla: Hráči střídavě říkají čísla od jedničky do desítky. Tato
čísla se sčítají.
Koncová pozice, prohrává: ten hráč, který první překročí stovku.
(Betlová varianta hry!)
Pozice "číslo 99" je vítězná. Tohoto čísla lze dosáhnout tehdy, pokud mu předchází číslo 89-98. Další vítězné číslo je 88, ... Takto lze pokračovat směrem k počátku hry. Dospějeme k tomu, že nejnižší vítězné číslo je 11. Pak následuje 22, 33, 44, atd. V této hře existuje vyhrávající strategie pro druhého hráče. Pokud první hráč řekne číslo x, druhý hráč odpoví číslem 11 - x. Úloha: Řešte analogickou hru v normální tvaru, tj. vyhrál ten hráč, který svým posledním tahem nepřekročí stovku.
Dvě hromádky
Základní postavení: Dvě hromádky předmětů. Na jedné hromádce je 6
předmětů a na druhé hromádce je devět předmětů.
Pravidla: Hráč, který je na tahu, odebere z jedné, z druhé, nebo z obou
zároveň: nejvýše tři předměty.
Koncová pozice, vyhrává: hráč, který odebral poslední předmět.
Čtyři nebo pět
Základní postavení: Dvě hromádky kamenů.
Pravidla: Hráč, který je na tahu, může odebrat nejvýše čtyři kameny z
první hromádky, nebo nejvýše pět kamenů z druhé hromádky, vždy ale
nejméně jeden kámen.
Koncová pozice, vyhrává: hráč, který odebral poslední kámen.
Následující hra není nestranná, ale je přirozeným zobecněním dvou předcházejících her:
Partyzánská hra s odebíráním
předmětů.
Základní postavení: Jedna hromádka kamenů.
Pravidla: První hráč může odebírat jeden nebo čtyři předměty, druhý
hráč odebírá dva nebo tři předměty z hromádky.
Koncová pozice, vyhrává: hráč, který odebral poslední předmět.
Nim
21
Základní postavení: Hraje se s 21 kameny
Pravidla: Tahem je odebrání 1, 2 nebo 3 kamenů
Koncová pozice, vyhrává: hráč, který odebere poslední kámen (normální
varianta hry Nim 21).
Při analýze se může postupovat zpětnou indukcí nebo rozložením do několika podproblémů. Soustřeďme se na několik koncových pozic. Jsou-li na stole 1, 2, nebo 3 předměty, první hráč vyhraje (přesněji: existuje vyhrávající strategie pro prvního hráče). Je-li na stole 5 předmětů, první hráč odebere jeden předmět a vyhraje. Je-li na stole 5-7 kamenů, první táhne tak, aby na hromádce zbyly 4 kameny, tedy opět pro něj existuje vyhrávající strategie... Ve hře Nim 21 existuje vyhrávající strategie pro prvního hráče. Při analýzách her je možné používat tabulky pro nestranné hry a tabulky hry s odebíráním předmětů.
Přirozeným zobecněním hry Nim 21 je hra s jiným počtem kamenů (Bachetova hra NIM s počtem mezi 15 a 25 kameny), popř. s jinou množinou dovolených tahů (třeba mocniny dvou, čtvercová čísla, prvočísla, odebírání 1,3 nebo 4 předměty, hry s nepravidelným vyloučením, hry na více hromádkách, odebírání nevlastních dělitelů, ...). Půlený NIM: Z hromádky kamenů hráč může odebrat nejvýše polovinu kamenů. Hra se hraje v normální variantě. Vyhrávající strategie pro druhého hráče je udržování pozic v hodnotách k = 3.2^{n-1}-1, pro n = 1, 2, 3... a Proporciální NIM:: Počáteční pozice je hromádka kamenů. Dovoleným tahem je odebrání z hromádky o n předmětech kladný počet kamenů, ostře menší než n/2+1. Hráč, který odebral poslední předmět, vyhrál.
Pravidlo pro analýzu kombinatorických her (analýza NP stavu) 1) Koncové stavy hry označme P, 2) Pozice, které vedou na stav P označíme N. 3) Stav, ze kterého vedou všechny tahy na P stav, označíme N. 4) Stav, ze které ho vede nějaká možnost táhnout do stavu N, označíme P. (Všimněte si duality!) Tato analýza hry je induktivně zřejmá. Obtížnost je ovšem dána nalezením všech možných NP stavů hry. Příklad je MINIŠACH Hraje se na desce 3 × 3 a na první (resp. poslední) řadě jsou postaveny tři bílé (resp. černé) kameny (pěšci). Tah spočívá v posunutí jednoho kamene své barvy o jedno políčko, nebo braní soupeřova kamene po diagonále. Hra končí, když některý z hráčů nemá tah. (Všimněte si, že se nejedná o nestrannou hru!) Pro analýzu her typu Nim lze použít i tuto tabulku.
Metoda kradení strategie pro nestranné hry: Předpokládejme, že nestrannou kombinatorickou hru lze rozdělit na dvě identické, totožné jednodušší hry. Potom druhý hráč může vždy vyhrát, a to tak, že kopíruje tahy, které soupeř dělá ve zbývající jednodušší hře. Hráč tahá symetricky. Návod, jak neprohrát ve hře šachy: Hrajte hru na dvou šachovnicích současně, na jedné s bílými a na druhé s černými kameny.
Nim
Základní postavení: Na hrací desce máme několik hromádek mincí (Obvykle
tři hromádky se 3, 5 a 7 mincemi).
Pravidla: Hráč, který je na tahu, může odstranit libovolný nenulový
počet mincí z některé hromádky.
Koncová pozice, vyhrává: hráč, který odebere poslední minci (normální
varianta).
Pozici se třemi hromádkami s 3, 5 a 7 mincemi označíme trojicí (3,5,7). Koncová pozice je (0,0,0). Stavy (1,0,0),(0,1,0),(0,0,1) jsou N stavy. Princip symetrie: Při dvou hromádkách jsou P stavy právě ty, v nichž mají obě hromádky stejný počet kamenů. Dále: stavy (1,1,1),(1,1,2),(1,2,2) jsou N, stav (1,2,3) je P.
Hře Marienbad se věnujeme na jiném místě.
Vytvořit strom všech pozic pro mnoho kamenů a velký počet hromádek je často obtížné. Najdeme kriterium pro P a N stavy, navíc i optimální tah. Metoda je založena na dvojkové soustavě a využívá se logická spojka XOR, vylučovací nebo. Tato spojka je definována takto: a XOR b = (a OR b) AND (NOT (a AND b)). Spojka XOR je sčítání ve dvojkové soustavě bez přenosu do vyššího řádu.
XOR | 0 | 1
----------
0 | 0 | 1
----------
1 | 1 | 0
Definice (Nim-součet (nim-sum)): Nim součtem čísel x = (xm...x2 x1x0)2, y = (ym...y2 y1y0)2 je číslo x Å y = ((xm+2ym) ...(x2+2y2)(x1+2y1)(x0+2y0))2.
Příklad: Počáteční konfigurace jsou 4 hromádky se 3, 6, 8, a 9 kameny.
3 = (0011)2
6 = (0110)2
8 = (1000)2
9 = (1001)2
3 Å 6 Å 8 Å 9 = (0100)2 = 4.
Operace Å je komutativní, asociativní, idempotentní s nulovým prvkem 0, s vlastností krácení. Struktura Nim čísel s operací Å je Abelova grupa. Navíc x Å y ≤ x + y, ale x Å y a x + y mají stejnou paritu.
Věta (Bouton, [Nim,1902]): Stav (x,y,z) v NIMu je P-stavem, právě tehdy, když x Å y Å z = 0.
Poznámka: Rozmyslete si, že nám stačí vyslovit tuto větu pouze pro tři hromádky!
Máme-li pouze jednu hromádku, první hráč odebere včechny
předměty a vyhrál. Na dvou hromádkách máme identický počet předmětů je
opět triviální příklad. Použijeme symetrii, existuje vyhrávající
strategie pro druhého hráče. Označíme-li symbolem ·n hromádku s n předměty, potom ·n + ·n
= 0. Je-li různý počet na dvou hromádkách, potom dorovnáme v prvním
tahu počty předmětů, a tedy existuje vyhrávající strategie pro prvního
hráče (problém jsme převedli na předcházející případ). Máme-li tři
hromádky, kde dvě mají shodný počet předmětů, potom existuje
vyhrávající strategie pro prvního hráče. Zajímavý je tedy případ, kdy
na třech hromádkách máme různý počet předmětů! Analogicky pro vyšší
počet hromádek (disjunktní součet).
Hodnotu hry ·n + ·m nalezneme jako ·(n XOR m). Algebra s hrami Nim
vede na teorii Nimbles.
3 = (0011)2
8 = (1000)2
10 = (1011)2
(0000)2
= 3 Å 8 Å 10 = 0 je P-stavem,
3 = (0011)2
6 = (0110)2
8 = (1000)2
9 = (1001)2
(0100)2
= 3 Å 6 Å 8 Å 9 = 4 je N-stav.
Poznámka: Z Boutonovy věty poznáme, zda se jedná o N-stav
(prohrávající postavení), resp. P-stav (vyhrávající postavení).
Současně nám ale i napoví, jak vypadá optimální tah v P-pozici. Stačí
přidat (odebrat) z nějaké hromádky nenulový součet x Å y Å
z. Konkrétně v posledním příkladu odebrání 4 kamenů z druhé hromádky je
optimální první tah, zaručující vítězství. Protože odebíráním kamenů se
čísla zmenšují, vyhledáme nejlevější sloupec s lichým počtem jedniček a
ten zmenšíme o výsledek operace Å.
(Odebrat tak, aby ve sloupcích byly samé pospárované prvky).
Vyhrávající pozice jsou všechny ty, u kterých je jejich nim-sum
Å roven nule.
Příklad: Uvažujme konfiguraci (6,7,8). Nim-součet je 6 Å 7 Å
8 = 9. Dále 6 Å 9 = 15
> 6, 7 Å 9 = 14
> 7, 8 Å 9 = 1
< 8. Tedy odečteme-li z poslední hromádky 7 kamenů, dostaneme
konfiguraci (6,7,1), což je 6 Å
7 Å 1 = 0.
Úloha: Zjistěte, zda v pozici (3,6,9,12) existuje vyhrávající strategie pro prvního hráče.
Hra Stříbrný
dolar a Dědictví
Hra stříbrný dolar se někdy hraje tak, že na políčkách může být i více
kamenů. Tah spočívá v přemístění kamene vlevo. Hra končí, jsou-li
všechny kameny na nejlevějším políčku. Hráč, který udělal poslední tah,
vyhrál. Tuto variantu hry nazýváme Nimbles.
I hra dědictví má svoji vícerozměrnou variantu.
Zlatý dolar
Základní postavení: Na pásku rozděleném na jednotlivá políčka jsou
rozmístěny mince, z nichž jedna je zlatý dolar. Pásek končí na hraně
stolu.
Pravidla: Tah hráče spočívá v přesunutí libovolné mince doleva ke hraně
stolu. Pokud je mince přemístěna až za hranu stolu, je ze hry
odstraněna. Na polích je nejvýše jedna mince, žádná mince se nesmí
přeskočit. Minci lze přesunout maximálně k bezprostředně předcházející
minci.
Koncová pozice, vyhrává: hráč, který odebere ze stolu „zlatý dolar“.
Poznámka: Soustřeďte se na počet mezer mezi jednotlivými mincemi.
I hra dědictví má svoji zlatou variantu.
Hře Kayles se věnujeme na jiném místě.
Poznámka: Hra Kuželky (Kayles) se někdy hraje tak, že je možné položit pouze dvě vedle sebe stojící kuželky. S osamělými a položenými kuželkami se již dále nehraje. Této variantě se říká Dawson's Kayles.
Daisy
Základní postavení: Mince jsou postaveny tentokrát do kruhu.
Pravidla: Tahem je odebrání jedné mince, nebo dvou sousedních.
Koncová pozice, vyhrává: hráč, který odebral poslední minci.
Převracení želv
Základní postavení: Mince jsou položeny v jedné řadě, některá lícem,
jiné rubem nahoru.
Pravidla: Hráč otočí jednu minci z líce na rub a může otočit i jiné
mince vlevo od vybrané.
Koncová pozice, vyhrává: Hráč, který jako první dosáhne, že všechny
mince jsou naruby. (Turning turtles) Úloha:
Analyzujte hru v postavení O O P P O P P (orel, panna).
Převracení nejvýše tří želv
Základní postavení: Mince jsou položeny v jedné řadě, některá lícem,
jiné rubem nahoru.
Pravidla: Hráč otočí jednu minci z líce na rub a může otočit i jiné
mince (ale nejvýše 3) vlevo od vybrané.
Koncová pozice, vyhrává: Hráč, který jako první dosáhne, že všechny
mince jsou naruby. (Je hra skutečně konečná?)
Mooreův
Nimk
Základní postavení: Na hrací desce máme několik hromádek mincí
Pravidla: Hráč, který je na tahu, může odstranit mince z libovolných k
hromádek (počet mincí ze které je libovolný), přitom ale musí odebrat
alespoň jednu minci. Koncová pozice, vyhrává: hráč, který odebere
poslední minci (normální varianta).
Věta (Moore, 1910): Stav (x,y,z,...) je v Nimk P-stav, právě když je počet jedniček na všech místech binárního zápisu čísel x, y, z, ... násobkem k + 1 (tj. čísla zapíšeme binárně a provedeme operaci XOR).
Také následující hra není nestranná a dokonce ani není kombinatorickou hrou (připouští opakování tahů), ale může být řešena jako hry Nim.
Poker Nim
Základní postavení: Na stole je několik hromádek předmětů. Hráči na
začátku mají ještě v kapse každý stejný počet předmětů.
Pravidla: V každém tahu hráč, který je na tahu, může, stejně jako ve
hře Nim, odebrat libovolný kladný počet předmětů z libovolné hromádky,
nebo přidat nenulový počet předmětů z kapsy na nějakou hromádku.
Koncová pozice, vyhrává: jako obvykle hráč, který odebere poslední
předmět ze stolu.
Úloha: Počáteční pozice je (2,4,6) a hráči mají po padesáti dalších kamenů. První hráč odebere jeden předmět z prostřední hromádky.
Autobus
Základní postavení: Hraje se jako obvyklý Nim na několika hromádkách.
Pravidla: Tahy jsou jako v Nimu (hráč vybere libovolnou hromádku a z ní
odebere kladný počet předmětů) a navíc s tímto tahem: Hráč, který je na
tahu, může vybrat hromádku, odebrat z ní nenulový počet předmětů a tyto
předměty přidat na nějakou jinou hromádku.
Koncová pozice, vyhrává: hráč, který táhne jako poslední. První hráč,
který již nemůže táhnout, prohrál.
Nápověda: Strategie je stejná, jako v obyčejném Nimu. Pokud první hráč
je v nulové pozici, odebere a přesune nějaké kameny, druhý hráč tyto
kameny odebere.
Northcottova hra
(tato hra sice není nestrannou, ale může se analyzovat jako
nestranná):
Základní postavení: Hraje se na šachovnici s bílými a černými pěšci, v
každém řádku je po jednom černým a jednom bílým pěšci. Bílý hráč tahá s
bílými figurami, černý s černými.
Pravidla: Pěšci mohou táhnout vpřed i vzad, ale nesmí se přeskakovat.
Musíte přesunout jednu z vašich figurek na jiné volné místo v téže řadě.
Koncová pozice, vyhrává: hráč, který táhne jako poslední. (Návod:
Všimněte si políček mezi kameny!) tato hraje variantou hry Autobus.
Wythoffova hra
Základní postavení: Dvě hromádky s m, n mincemi.
Pravidla: Na tahu můžete odstranit libovolný počet mincí z jedné
hromádky, nebo stejný počet mincí z obou hromádek současně .
Koncová pozice, vyhrává: hráč, který odebere poslední minci. (Nalezněte
vzorec pro vítězné pozice v této hře! Sprague-Grundy funkce je periodická.
Úlohu řešte pro postavení (16,23).) Pozn. hru je možné zobecnit např.
tak, že se mince mohou odebírat ze tří, popř. ze všech hromádek
současně.
Dvojrozměrný Nim
Základní postavení: Hraje se na čtvercové síti, kde je umístěn konečný
počet kamenů (na jednom poli může být i více kamenů).
Pravidla: Tah spočívá v přesunu jednoho kamene směrem vlevo ve stejném
řádku, nebo na pole v některém nižším řádku.
Koncová pozice, vyhrává: hráč, který odebere poslední kámen. (Nalezněte
vzorec pro vítězné pozice v této hře!) Varianta této hry připouští tahy
s celou hromádkou dolů, nebo vlevo, popř. odebrat z hromádky předmět.
Hra Nim na schodech
Základní postavení: Na jednotlivých n stupních schodů jsou položeny
kameny (na jednom poli může být i více kamenů).
Pravidla: Tah spočívá v přesunu několika kamenů (alespoň jednoho) o
schod níže. S kameny, které dosáhnou 0tého stupně, se dále již nehraje.
Koncová pozice, vyhrává: všechny kameny jsou již na 0tém schodu,
poslední hráč, který táhnul, vyhrává.
Hra
Grundy
Základní postavení: Hromádka obsahující N kamenů.
Pravidla: Hráč vybere libovolnou hromádku a tu rozdělí na dvě nenulové
hromádky s různým nenulovým počtem mincí
Koncová pozice, vyhrává: hráč, který udělal poslední tah. (Tato hra je
ekvivalentní jedné hře uvedené dříve!)
Antigrundy hra
je nestranná hra dvouhráčů na hromádkách s fazolemi. Počet fazolí na
každé hromádce musí být kladný. Jako obvykle vyhrává hráč, který táhne
jako poslední. Hráči se pravidelně ve svých tazích střídají. Tahem je
označení nějaké hromádky a její rozdělení na dvě nebo více hromádek,
ale tak, že nově vzniklé hromádky mají stejný počet. Např. označíme-li
hromádku s n fazolemi symbolem n, potom 6
může být 2 + 2 + 2,
nebo 3 + 3, nebo 1
+ 1 + 1 + 1
+ 1 + 1, po následujícím tahu
můžeme např. dostat: 1 + 1 + 2
+ 2 a pod.
Laskerův Nim
Základní postavení: Hromádky kamenů.
Pravidla: Hráč vybere libovolnou hromádku a tu rozdělí na dvě nenulové
hromádky, nebo z libovolné hromádky odebere nenulový počet kamenů.
Koncová pozice, vyhrává: hráč, který udělal poslední tah.
Pegggy Nim
Základní postavení: Hromádky kamenů.
Pravidla: Hráč může odebírat z jedné hromádky sudý počet kamenů (ale ne
celou). V případě, že na hromádce je lichý počet kamenů, může odebrat i
celou hromádku.
Koncová pozice, vyhrává: hráč, který udělal poslední tah.
Nápověda: Úlohu řešte nejdříve pro jednu hromádku, nalezněte Grundyovu
funkci a použijte součet her. Ukažte, že např. postavení (7,6,8,4) je
nenulové, prvním dobrým tahem je odebrání celé první hromádky.
Bílá věž o tři
Základní postavení: Šachovnice s jednou bílou věží.
Pravidla: Věž se může posunout po řádcích vlevo, po sloupcích dolů,
vždy ale nejvýše o tři políčka.
Koncová pozice, vyhrává: hráč, který udělal poslední tah. (Ta hra je
ekvivalentní s jednou již dříve uvedenou hrou: hra Nim se dvěma
hromádkami, a s tahy odebírání 1-3 předmětů s tím, že v každém tahu si
hráč může svobodně vybrat ze které hromádky předměty odebere!)
Hry na šachovnici jsou velmi populární (např. Minišach). Následující hra sice opět není nestranná, ale při její analýze nám pomůže naše znalost o hře Nim.
Šestnáct věží
Základní postavení: Šachovnice s osmi bílými a černými věžemi v
základním postavení na prvním, resp. osmém řádku.
Pravidla: Věže se mohou posunovat nahoru nebo dolů (po sloupcích).
Cílem hry je zamezit pohybu věží protihráče. Začíná bílý hráč.
Koncová pozice, prohrává: hráč, již nemůže táhnout. (Tato hra není ani
kombinatorickou hrou, dovoluje opakování tahů). Nápověda 1: Hru
nejdříve hrajte na menší šachovnici. Nápověda 2: Soustřeďte se na
vzdálenost mezi dvěma protilehlými věžemi. Počet prázdných políček bude
odpovídat počtu předmětů na hromádce ve hře Nim.
Wyt Queen
Základní postavení: Šachovnice s jednou bílou královnou.
Pravidla: Královna se může posunout po řádcích vlevo, po sloupcích
dolů, popř. po diagonále vlevo dolů, a to o libovolný nenulový počet
poliček.
Koncová pozice, vyhrává: hráč, který udělal poslední tah. (Ta hra je
ekvivalentní s jednou již dříve uvedenou hrou!) Hra se hraje i s více
figurami. Zahrajte si také některou variantu této hry (Věž:
tahy pouze vlevo nebo dolů; Jezdec: tahy
dolů nebo vlevo.).
Poznámky: Někdy se analyzují i NP hry s remízou (patem). Stromečková analýza hry je podobná, jak již bylo uvedeno dříve: 1) Všechny vítězné pozice označme P. 2) Všechny prohrávající pozice označme N. 5) označme patové stavy D 6) Pokud neplatí 3) a 4) (viz výše), předcházející pozice označme také D, a také všechny stavy N.
Euklidova hra
Základní postavení: Je dána uspořádaná dvojice (x,y) kladných celých
čísel x, y.
Pravidla: Hráč, který je na tahu, může odečíst od většího čísla
nenulový celočíselný násobek menšího čísla tak, aby výsledek byl ještě
kladný.
Koncová pozice, prohrává: hráč, který je na tahu a nemůže již táhnout.
Prohrávající pozice jsou (d,d), kde d = NSD(x,y). Poslední hráč, který
zahrál svůj tah, vyhrál.
Euklidova hra se někdy zobecňuje: pravidla hry jsou stejná až na to, že odebírat lze jen jisté násobky pevně stanovených čísel.
Nestranná hra. Pozice se nazývá nestrannou, pokud oba hráči v pozici mají stejné možnosti. Hra je (abs.) nestrannou hrou, pokud v každé pozici oba hráči mají identické možnosti. Slovo absolutně budeme vynechávat. Kdo u nestranných her vyhraje záleží jenom na tom, kdo začíná.
Při analyzování nestranných her se nám může hodit zpětná indukce, tj. nebudeme se zajímat pouze o vyhrávající pozici, ale i o všechny předcházející tahy. Díky definici nestranné hry to lze. Předpokládejme, že nějakou hru nestrannou kombinatorickou hru umíme rozložit na dvě jednodušší identické hry. Druhý hráč má vyhrávající strategii, když bude kopírovat tahy soupeře ve druhé hře. Jinými slovy hra je nenulový Nim na jedné hromádce, kam přisypáváme kameny!
Následující věta nám dává globální pohled na nestranné hry:
Věta (Sprague-Grundy) o nestranných hrách (Sprague 1936, Grundy 1939) Všechny pozice v nestranných kombinatorických hrách jsou rovnocenné (až na reverzibilní tahy) s jedinou hromádkou hry Nim. Počet ekvivalentních předmětů na hromádce nazýváme hodnotou Nim. Vyhrávající pozice má hodnotu Nim rovnu nule, tj. musíme mít takovou vyhrávající strategii, aby nám zaručila přechod do hodnoty 0.
Výpočty hodnoty Nim - Představme si, že jsou dány dvě hry, které se hrají současně. Ve svém tahu můžeme hrát v jedné z nich. Poslední hráč, který táhne, hru vyhrál. Pokud hodnoty Nim počáteční pozice pro dvě hry jsou hodnotami A a B, pak hodnota společné hry je A XOR B. Z tohoto důvodu se bitový xor také někdy nazývá Nim-sum.
Výpočty hodnoty Nim - pravidlo mex (Mex = mex = minimum excluded) Předpokládejme, že chceme vypočítat hodnotu Nim pro nějakou konkrétní pozici P nestranné kombinatorické hře, a že hodnoty Nim všech jeho možností (tahů v této hře) jsou v1, v2, v3, ... vn. Výsledná hodnota Nim v pozici P je mex(v1, v2, v3, ... vn) = nejmenší nezáporné celé číslo, které se nerovná vi pro všechna i.
Označme ·n hromádku s
n-předměty. Nalezněme ·p
+ ·q!
·p + ·q = { ·(p-1)
+ ·q, ·(p-2) + ·q,...
,·2 + ·q, ·1
+ ·q, ·0 + ·q,
·p + ·(q-1), ·p
+ ·(q-2),...,... , ·p + ·0)
| ... }. Všechny pravé tahy jsou stejné, jako levé tahy. Navíc všechny
tyto hry jsou jednodušší než hra ·p
+ ·q (všechny se
narodily dříve). Induktivně pro ·(p-1)
+ ·q,... jsou všechny
výsledky rovny nějaké hodnotě Nim (počtu předmětů na hromádce). Potom ·p + ·q
se bude rovnat {·α, ·β, ·γ,...
| ... } pro nějaké α, β, γ, ... a je nějakému ·δ,
kde δ = mex(α, β, γ, ...), tj. nejmenší nezáporné číslo, které není ve
výčtu α, β, γ, ....
Příklad: mex(0,1,2,3,4,5) = 6, mex(0,2,4,6) = 1, mex() = 0,
mex(1,3,5,2,2,0) = 4, ....
Důkaz by bylo chybou vynechat. Uvažme nejdříve, že ·δ = - ·δ.
Potom bude stačit dokázat, že (·p
+ ·q) + ·δ je nulová hra. Stačí
vyšetřovat případ, kdy začíná hrát levý hráč. Levý hráč může zahrát do
hry ·α + ·δ. Protože α ≠ δ, pravý hráč
odpoví do symetrické hry - δ je hodnotou mex, odebere |α - δ| pro
největší hromádku. Pokud levý hráč zahraje ve hře δ, dostaneme se do
hry ·p + ·q + ·ε,
kde ε je menší hromádka než ·δ.
Protože ale δ je hodnotou mex, ε nutně musí být jedno z výčtu α, β, δ,
..., opět vyhraje pravý hráč výběrem ekvivalentní hromádky. Tedy máme:
pokud začíná levý, existuje vyhrávající strategie pro pravého (druhého)
hráče. Jiná varianta nemůže nastat. Odtud (·p
+ ·q) + ·δ je nulová hra, což znamená, že
(·p + ·q) = ·δ.
Doposud jseme vyšetřovali hry v normální tvaru, tj. hráč, který táhnul jako poslední (konec hry), vyhrál. Hráč, který nemá pravidly povolený tah, prohrál. Někdy se zase vyšetřují hry betlové (misère) takové, že poslední hráč hru prohrál. Studium takových her je mnohem obtížnější, než her normálních. Betlová analýza varianty nestraných her je ale úplná.
Disjunktní součet. Doposud jsme používali tzv. Nim-sum (XOR na bitech čísel ve dvojkové soustavě +2). Rozlišujeme ale tento součet s obyčejným (tzv. disjunktním součtem her. Disjunktní součet dvou paralelních (simultáních) her znamená, že hrajeme na dvou hrách současně, tedy můžeme si vybrat, v které hře zahrajeme. Slovo disjunktní budeme často vynechávat. Součet na více hromádkách je možné dodefinovat indukcí. Součet je návod na vytvářeni složitějších her, ale umožňuje i zpětnou analýzu. Typickou ukázkou je Nim na třech hromádkách, každá je samostatná hra. Sprague-Grundy funkce na součtu her je Nim-sum Sprague-Grundy hodnota na všech komponentách hry (Zobecnění Boutonovy věty!). Induktivní důkaz lze přeskočit. Každá nestranná hra je ekvivalentní nějakému Nimu; totiž každá nestranná hra se jako sčítanec součtu her chová stejně jako hra Nim s jedinou hromádkou oceněné právě hodnotou Sprague-Grundy této hry. Mnoho dalších příkladů funkce Sprague-Grundy čtenář nalezne v [OGAN] pod heslem 'výtvarný zákon'.
Příklad: Mějme tři hromádky, na hromádkách je 12, 17 a 23 kamenů, z první můžeme odebrat nejvýše pět, z druhé nejvýše tři a z poslední hromádky nejvýše 4 kameny v každém tahu. Označme G(m) že z jedné hromádky můžeme odebrat nejvýše m předmětů. Potom G = G(5) + G(3) + G(4). Poměrně jednoduše lze zjistit, že Sprague-Grundy funkce G(m) je gm(n) = n mod m+1. Potom g((12,17,23)) = g5(12) Å g3(17) Å g4(23) = 0 Å 1 Å 3 = 2.
Ve třicátých letech minulého století byla pracemi Laskera, Grundyho a Sprague završena analýza nestranných her. Vyšetřovali vlastnosti her typu Nim, disjunktní sčítání (abs.). Jejich výsledky lze shrnout tak, že každá pozice v nestranné hře je hra typu Nim (tj. může být nahrazena součtem her Nim). Při vyšetřování her je zase někdy výhodné nalézt její ekvivalenci s hrou obracení mincí.
Každá nestranná kombinatorická hra je ekvivalentní s nějakou hrou hrou Nim. Tato ekvivalence znamená, že každá nestranná hra x má nějakou hru ·n takovou, pro kterou x + ·n = ·0.
Odtud též plyne jednoduchý návod na počítání hodnot funkce Sprague-Grundy. Nejdříve se určí hodnoty g(1), g(2), g(3), ... a tak dále. Následující hodnoty se určí pomocí Nim-sum. Tedy určí se hodnoty ve dvou krocích: nejdříve na jedné hromádce a potom na více hromádkách.
V 70. létech minulého století John H. Conway studuje tzv. partyzánské hry (ve kterých již neplatí, že v každé pozici hry mají oba hráči přesně stejné tahy - možnosti), které vedou na reálná a mj. na tzv. transfinitní čísla, ... Příklad:
Černo-bílý
Nim
Základní postavení: Na stole je několik sloupců černých a bílých kamenů.
Pravidla: Hráč, který je na tahu, vybere nějaký kámen (pouze z jedné
uspořádané hromádky) své barvy a odebere tento kámen a s ním i všech
kameny, které jsou nad ním.
Koncová pozice, vyhrává: hráč, který udělal poslední tah.
Poznámky: Losem se určí, kdo bude ve hře začínat. Je evidentní, že tato
hra nemusí být nestrannou. Bílé kameny budeme značit x, černé o; místo
sloupců, budeme používat žížaly - odebírání zprava, levá strana je
'spodní'. Například máme hru: xxxx, ooo, oxx, oxo, ox. To znamená, 5
hromádek a např. na posledním sloupci je od zdola černý, bílý kámen.
Hra je ekvivalentní s hrou Tyčinky (zjednodušený Hackenbush). Opět nás
bude zajímat, který hráč má výhodu (má lepší postavení), a pokud ji má,
tak jakou? Jednotlivým pozicím přiřadíme čísla. Např. x = 1, o = -1, xx
= 2, ... podle pravidla: kolik má ještě tahů. Jednotlivým pozicím
(konfiguracím) budeme přiřazovat racionální čísla, levý hráč odebírá
křížky x, pravý hráč odebírá kolečka o. Hře x, o přiřadíme nulu 0 a
také všem hrám, kde existuje vyhrávající strategie pro druhého hráče.
Např. pozice xo, xo, x = 0. Vedle sebe stojící sloupce budeme chápat
jako (disjunktní) součet her, např. z posledního příkladu plyne, že xo
= 1/2 a pod. Příklad x = 1, o = -1 nás vede k domněnce, že opačný prvek
znamená změnu barvy kamenů. Kladné hry jsou takové, ve kterých existuje
vyhrávající strategie pro levého (ten, který odebírá x) hráče, záporná
hra je taková, kde má naopak výhodu černý hráč. A přitom nezáleží na
tom, který hráč ve hře začíná jako první. Příklad: xo. Černobílé
sloupce budou vždy zastupovat racionální čísla se jmenovatelem mocniny
dvou. Např. xoxo, xoxo, ox = 0, tedy xoxo = 1/4 a pod. Několik dalších
prvních 'složitějších' her, které je možné rekurzivně analyzovat: x = {
0 | } = 1, xo = { 0 | 1 } = 1/2, xox = { 0, 1/2 | 1 } = 3/4, xoxo = {
0, 1/2 | 3/4, 1 } = 5/8, xoxoo = { 0, xo | xoxo, xox, x } = { 0, 1/2 |
5/8, 3/4, 1 } = 9/16 a podobně. Úloha:
Ukažte, že pozice xooox má hodnotu 1/16! Zápisy typu { a, b, c, ... |
k, l , m, ...} znamenají možné tahy pro bílého hráče a, b, c,..., pro
tahy černého hráče k, l, m, ... Několik dalších periodických
nekonečných her: xoxoxoxoxo... = 1/3, xxxxxxx... = ω, x, xxxxxxx... = ω
+ 1, xoooooo.... = 1/ω a podobně. Všimněte si, že každá subhra (všechny
možnosti hráčů) je konečná!