\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<h$, ale nevieme potiahnu� do poz�cie s Grundyho ��slom $h$. 

Vhodn�m zmen�en�m niektor�ho z $G(Q_i)$ dostaneme �ubovo�n� $\xor$ men�� ako $h$. 
Tak�to �ah vieme urobi� z defin�cie $G(Q_i)$ a ten $\xor$ je pod�a ind. predpokladu
Grundyho ��slom v�slednej ve�kej poz�cie. �ubovo�n�m �ahom sa $\xor$ zmen�, teda 
nikdy nebude $h$. 

\section{Zhrnutie}

Ka�d� poz�cia ka�dej symetrickej hry je ekvivalentn� s k�pkou NIMu.
Ve�kos� tejto k�pky ud�va Grundyho ��slo pr�slu�nej poz�cie. 
To n�m z�rove� hovor�, �i je pr�slu�n� poz�cia vyhr�vaj�ca. 

Vyhodnoti� poz�ciu s��tu hier vieme spo��ta� tak, �e spo��tame Grundyho ��sla
mal�ch poz�ci� a prexorujeme ich. 
Takto �ahko zist�me, �i je cel� poz�cia vyhr�vaj�ca alebo nie.

In�mi slovami: akoby nahrad�me jednotliv� mal� hry pr�slu�ne ve�k�mi 
k�pkami NIMu a �alej akoby hr�me $n$-kopov� NIM, kde s� prehr�vaj�ce pr�ve
poz�cie, kde je $\xor$ ve�kost� k�pok 0. 

\section{Na z�ver}

Grundyho hra: Hr�� na �ahu zoberie k�pku a rozdel� ju na dve r�zne ve�k�. 

Pi�quorky: Na nekone�nom �tvor�ekovom papieri m� prv� hr�� neprehr�vaj�cu strat�giu.
(Sporom, ak m� druh� vyhr�vaj�cu, d� prv� kr��ik niekam n�hodne a pou�ije ju.)

\end{document}

