\documentclass{article} \usepackage{slovak} \usepackage{epsfig} \usepackage{a4wide} \def\xor{\mathop{\rm xor}} \begin{document} \centerline{\Large\sc Prednáška o Combinatorial Game Theory} \medskip \centerline{\large MišoF. -- Počúvadlo, jar 2004} \bigskip\hrule\bigskip \section{Čo sú kombinatorické (matematické) hry} Dvaja hráči, úplná informácia (teda nie karty). Žiaden vplyv náhody (teda ani kocky). Hráči striedavo ťahajú. Výsledok je že jeden hráč vyhral a druhý prehral (niekedy povolíme remízu). Vieme definovať prípustné {\em pozície} a {\em ťahy} -- presuny medzi nimi. Jedna pozícia je začiatočná. Koncová pozícia -- taká, v ktorej neexistuje ťah. Kto vyhral? Klasická definícia: prehráva ten, kto v danej situácií nemá prípustný ťah. (Napr. v šachu keď dostal mat -- žiaden ťah nie je prípustný, lebo kráľ ostane ohrozený. V piškvorkách môžeme jednoducho povedať, že v pozícii, v ktorej už niekto spravil piškvorku, sa už nič nedá robiť.) {\em Vyhrávajúca stratégia} -- postup, ktorý hráčovi zaručí víťazstvo bez ohľadu na hru súpera. {\em Symetrické} hry -- obaja hráči majú v danej pozícii rovnaké možné ťahy. (Šach aj piškvorky sú hry s úplnou informáciou, ale nie sú symetrické.) Od tohto okamihu sa hráme len symetrické hry. {\em Konečnosť}: z každej pozície hra v konečnom počte ťahov skončí. \section{Príklad: jednoduchý NIM} NIM (pravdepodobne od slovného základu "brať") je skupina hier, väčšinou s kôpkami zápaliek (či iných objektov). Jednoduchý príklad: 3-NIM. Je 21 zápaliek, hráč na ťahu berie 1, 2 alebo 3. Kto nemá ťah, prehráva. (Teda vyhráva ten, čo zoberie poslednú zápalku.) Táto hra je symetrická. \section{Vyhrávajúce a prehrávajúce pozície} Ako v predchádzajúcej hre zistiť, kto vyhrá? Od konca "ofarbíme" pozície na {\em vyhrávajúce} (hráč na ťahu má vyhrávajúcu stratégiu) a {\em prehrávajúce} (nutne má vyhrávajúcu stratégiu druhý hráč). Toto vždy funguje. Problémy neskôr. \begin{itemize}\itemsep -3pt \item Všetky koncové pozície sú zjavne prehrávajúce. \item Ak z danej pozície vieme potiahnuť do prehrávajúcej (pre súpera!), je vyhrávajúca. \item Ak z danej pozície všetky ťahy vedú do vyhrávajúcich pozícií (pre súpera), je prehrávajúca. \end{itemize} \section{$n$-kopový NIM} Jednokopový NIM ako triviálny príklad. Dvojkopový NIM ako príklad stratégie "ťahám symetricky so súperom". Ako odbočka hra s margarétkou. Trojkopový NIM. Toto bude príklad prístupu "uhádneme riešenie a dokážeme ho". Pozície s niektorou kopou 0 už vieme. Pozície $(x,x,y)$ pre $x,y>0$ sú vyhrávajúce. Pozícia $(1,2,3)$ potom musí byť prehrávajúca. Ďalšie prehrávajúce pozície sú $(1,4,5)$ a $(2,4,6)$. Začína vyzerať ako súčet. Nie je. Prehrávajúca je aj $(3,5,6)$. Opravíme hypotézu. Prehrávajúce sú tie, kde $\xor$ je 0. Odbočka: Čo je $\xor$, vlastnosti: $a\xor 0=a$, komutatívnosť, asociativita, $(a\xor b)\xor b=a$. Intuície ako "parita počtu jednotiek" a "negácia bitov $a$ určených maskou $b$". Dajme pozíciám názvy "dobrá" a "zlá" podľa toho, či je $\xor$ veľkostí kôp nenulový. Rozpíšeme veľkosti kôp v dvojkovej sústave, ukážeme, že naozaj vieme z každej dobrej pozície dostať zlú, zo zlej vždy dostaneme dobrú a že všetky koncové pozície sú zlé. Potom ale nutne dobré=vyhrávajúce a zlé=prehrávajúce. Charakterizácia pozícií nám dáva aj návod, ako hrať -- hľadáme ťah do prehrávajúcej pozície. Všimnime si, že $\xor$ funguje aj pre jedno- a dvojkopový NIM. A dokonca aj pre $n>3$. \section{Grafová hra} Daný je DAG, hráči hýbu figúrku po hranách. Uvedomte si, že takto vieme popísať ľubovoľnú symetrickú hru. (Addon: asymetrické ak farebné hrany.) \section{Súčet hier} Z viacerých kombinatorických hier môžeme poskladať jednu -- stoly s hracími plánmi, hráč na ťahu si vyberie stôl a na tom potiahne. Poskladanú hru budeme volať {\em veľká}, pôvodné hry {\em malé} a hovoríme, že veľká hra je {\em súčtom} malých. Súčtom hier môžeme dostať omnoho zložitejšiu hru ako boli pôvodné hry -- trojkopový NIM je súčtom troch jednokopových! Malé hry môžu byť navzájom rôzne -- jeden stôl so šachovnicou, druhý so štvorčekovým papierom, na treťom sa hrá 3-NIM, atď. Problém: Priestor možných pozícií pri súčte hier exponenciálne rastie s ich počtom, nedá sa ho celý prezrieť. To, čo by sme potrebovali, je dokázať povedať, či je pozícia vyhrávajúca alebo prehrávajúca len na základe jednotlivých "podpozícií". Zjavne informácia, či sú podpozície vyhrávajúce, nestačí -- súčtom troch prehrávajúcich pozícií môže byť ako vyhrávajúca, tak aj prehrávajúca pozícia. \section{Sprague-Grundyho čísla} O každej pozícii každej hry vyhlásime, že sa "podobá" na kôpku NIMu. Princíp bude nasledovný: Koncové pozície sa podobajú na kôpku veľkosti 0. Majme teraz pozíciu $P$, z nej sa dá ťahať do $P_1,\dots,P_k$, tie sa podobajú na kôpky veľkostí $a_1,\dots,a_k$. Potom pozícia $P$ sa bude podobať na kôpku veľkosti $a$, kde $a$ je najmenší prvok $N_0\setminus\{a_i\}$. Intuícia: vieme ťahať do pozícií, ktoré zodpovedajú všetkým menším kôpkam. Rovnako, ako sme počítali V/P-pozície, vieme spočítať pre každú pozíciu, na ako veľkú kôpku NIMu sa podobá. Tieto hodnoty nazveme Grundyho čísla. Property: $G(P)=0$ iff $P$ je prehrávajúca. Nič teda nestratíme, ak namiesto toho, ktoré pozície sú vyhrávajúce, budeme počítať Grundyho čísla pozícií. Neskôr ukážeme, že pri súčtoch hier tým niečo získame. Príklady: Grundyho čísla pre jednokopový NIM, pre 3-NIM. \section{Sprague-Grundyho veta} Ukážeme, že naozaj platí naša analógia pozícií a kôpok NIMu. Majme veľkú hru. Tvrdíme, že keď nahradíme všetky pozície v malých hrách im podobnými kôpkami zápaliek (s ktorými sa bude hrať NIM), výsledok hry (t.j. vyhrávajúcosť pozície) sa nezmení. Ukážeme, ako z Grundyho čísel pre pozície malých hier spočítať Grundyho číslo celej veľkej pozície. Bude to samozrejme rovnako ako pri $n$-kopovom NIMe: Nech sa pozícia $P$ skladá z malých pozícií $Q_i$, tie majú Grundyho čísla $G(Q_i)$. Potom $G(P)=G(Q_1)\xor\dots\xor G(Q_k)$. Formálny dôkaz by bol indukciou, postupne berieme pozíciu $P$ čoraz ďalej od konca. Aby sme tvrdenie dokázali pre konkrétne $P$ (ak už platí pre všetky pozície, kam vieme ťahať z $P$), potrebujeme ukázať, že hodnota $h$ na pravej strane spĺňa definíciu $G(P)$. Inými slovami, že z $P$ vieme potiahnuť do pozícií $P_i$ takými, že $G(P_i)=i$ pre všetky $i