Sciencemag.cz
Doporučujeme
Tuto hru vymyslel v roce 1942 Piet Hein. V roce 1948 ji pak znovuobjevil Nash. Říká se, že na tento nápad přišel, když si prohlížel šestiúhelníkové dlaždice na záchodcích matematického oddělení v Princetonu. Je pravda, že tam takové dlaždice skutečně jsou, ale Nash mi řekl, že mu inspirací rozhodně nebyly.
Hex je hra pro dva hráče, černého a bílého, která se hraje na rovnoběžníkovém poli složeném z šestiúhelníků (viz obrázek). Na začátku hry patří každému hráči území dvou protilehlých stran. Bílý táhne první a poté se střídá s černým. V každém tahu může hráč položit jeden ze svých žetonů na libovolné prázdné políčko. Cílem hry je spojit protilehlé strany svými žetony – hru na obrázku 10 tedy vyhrál černý.
Stejně jako v šachách bychom teoreticky mohli zjistit maximinové výplaty hráčů pomocí zpětné indukce, ale hrací pole je příliš velké, než aby to bylo praktické. Přesto ale víme, že maximinová výplata bílého je výhra. Existuje tedy strategie, která prvnímu hráči zajistí výhru, ať se druhý hráč brání jakkoliv. Jak to ale víme?
Nejprve si všimněte, že Hex nemůže skončit remízou: představte si černé žetony jako vodu a bílé žetony jako pevninu. Po úplném obsazení herní plochy může nastat jedna ze dvou situací – buď mezi dvěma jezery, která černému patřila na začátku, poteče voda, anebo budou oddělena pevninou. V prvním případě by vyhrál černý a v druhém bílý. Jeden z hráčů tedy musí mít výherní strategii.
Nash pomocí metody „kradení strategií“ ukázal, že vítězem bude bílý. Jde o důkaz sporem. Kdyby černý hrál výherní strategii, mohl by ji bílý ukrást následujícím způsobem:
1. První žeton položte kamkoli.
2. V dalších tazích si vždy představte, že poslední žeton, který jste položili, neexistuje, a že všechny ostatní bílé žetony jsou černé – a naopak.
3. Proveďte tah, který by v této situaci provedl v souladu se svou výherní strategií černý. Pokud už na příslušném políčku žeton máte, táhněte kamkoli.
Tato strategie vám zaručí výhru, protože děláte to samé, co by mělo údajně zaručit výhru černému – ale o tah dříve. Je možné, že vyhrajete dříve než by na vašem místě vyhrál černý, protože máte ve hře o žeton víc, ale to vám jistě vadit nebude.
Vítěz může být jen jeden, takže náš předpoklad, že černý má výherní strategii, musí být mylný. Vítězem je tedy bílý, ale při Hře na velkém hracím poli nám tato znalost nebude nic platná, protože obecná výherní strategie pro bílého dosud nebyla nalezena.
Všimněte si, že metoda kradení strategií nám o výherní strategií samotné nic neříká. Pokud chce mít bílý jistou výhru, rozhodně nemůže položit svůj první žeton, kam chce. Pokud ho například položí do rohu s ostrým úhlem, očividně existuje ve zbytku hry výherní strategie pro černého (tento tah bílému nijak nepomáhá, takže obě strany si tak de facto vymění role).
(Poznámka PH: Na tomto místě má snad ještě smysl poznámka, proč podobný princip nelze aplikovat na šachy. V Hexu je tah k dobru totiž vždy výhodou, respektive nemůže znamenat nevýhodu. V šachách naopak nastávají i pozice s nevýhodou tahu, kde např. platí, že kdo je na tahu, prohraje.)
Existuje také jiná, možná o něco zábavnější verze Hexu, kterou si prý matematici v Princetonu utahovali z návštěvníků. Tato verze má o jednu řadu šestiúhelníků navíc, takže bílé strany jsou od sebe dál než černé. Nejenže má teď výherní strategii černý, ale dokonce ji dokážeme sepsat. Jenže když návštěvníci hráli za bílého proti počítači, hrací pole bylo na obrazovce zobrazeno tak, že jeho asymetrie zdánlivě zmizela. Návštěvníci si proto mysleli, že hrají normální verzi Hexu a nesmírně je frustrovalo, když počítač pořád vyhrával.
Tento text je úryvkem z knihy
Ken Binmore: Teorie her … a jak může změnit váš život
Argo a Dokořán 2025 (nové vydání)
O knize na stránkách vydavatele
