Úvod do teorie kombinatorických her

Othello

 

Na začátku jsou na desce 8×8 polí položeny čtyři kameny, dva bílé a dva černé. Cílem hry je získat co nejvíce kamenů otočených hráčovou barvou vzhůru. První je na tahu černý. Hráči se v tazích pravidelně střídají. Hráč, který je na tahu, vezme jeden svůj kámen ležící mimo desku a položí ho na desku svojí barvou nahoru. Kameny jsou společné, takže žádnému hráči nemohou kameny během hry dojít. Kamenů je 64, z jedné strany bílých a z druhé černých Položit kámen lze pouze tak, aby spolu s jiným kamenem téže barvy, který už na desce leží, obstoupily kameny soupeře. Obstoupením se rozumí, že mezi nově položeným kamenem a jiným kamenem téže barvy leží souvislá řada kamenů opačné barvy. Obstoupená řada může ležet jak ve směru rovnoběžném s okrajem desky, tak i diagonálně.

Položením jednoho kamene lze obstoupit několik řad soupeřových kamenů současně, pokud za všemi už hlídkuje kámen barvy toho hráče, který táhne (například současně v obou ortogonálních směrech i diagonálně). V extrémním případě lze tedy obstoupit soupeřovy kameny současně ve všech osmi směrech.

Obstoupené kameny se otočí nahoru barvou hráče, který je obstoupil, a stávají se jeho kameny. Za obstoupení se nepovažuje, pokud se řada kamenů dostane mezi kameny opačné barvy jiným způsobem než položením soupeřova kamene - například přebarvením okrajového kamene na barvu soupeře, nebo položením kamene na volné místo mezi dva soupeřovy kameny. Pokud hráč nemůže provést tah podle pravidel (tj. tak, aby otočil alespoň jeden soupeřův kámen), řekne pas a hraje jeho soupeř. Pokud hráč může provést tah podle pravidel, pak ho provést musí. Tahu se nelze vzdát.

Hra končí po položení všech 64 kamenů, nebo když oba hráči po sobě nemohou provést tah podle pravidel. Vítězem je hráč, který má na konci více kamenů otočených svojí barvou nahoru. Skóre hry je počet kamenů vítězného hráče ku počtu kamenů poraženého. Pokud hra skončila před položením všech 64 kamenů, přičítají se prázdná místa na desce k dobru vítěze, jako by na nich ležely kameny jeho barvy. Součet skóre obou hráčů tedy vždy dělá 64.