Uvažujte hru Reversi pre dvoch hráčov na ploche 8x8 políčok. Hráč označený Max má krížiky (X), hráč označený Min má kolieska (O). Hráči (vždy keď je to možné) ťahajú – vkladajú svoje kamene striedavo. Hráč môže položiť svoj kameň len vedľa kameňa protihráča, aj to len vtedy, keď je za týmto kameňom neprerušená postupnosť kameňov takých, že aspoň jeden z tých kameňov je vlastný. Po položení nového kameňa sa zmenia všetky súperove kamene na úsečke medzi týmto kameňom a prvým vlastným kameňom na vlastné. V každom kroku sa teda zmení aspoň jeden kameň. Ak niekto nemôže urobiť takýto ťah, má pauzu a znovu ťahá súper. Príklad hry je možné vidieť tu.
Hra sa vždy začína v stave s* a na ťahu je Max.
| s* = |
|
e(s) = (počet možných ťahov pre Max) -
(počet možných ťahov pre Min).
V počiatočnom stave s* môže každý vykonať práve štyri ťahy a teda (s*) = 4 - 4 = 0 (bez ohľadu, či je na ťahu Min
alebo Max).
Používajú sa aj iné odhady, napríklad počet zmenených kameňov v tomto ťahu (často sa používa v kombinácii s predchádzajúcim ohodnotením) alebo náročnejšie odhady uvažujúce kamene uzavreté vo vnútri a nezmeniteľné kamene na okraji alebo v rohu hracieho poľa. Aj možný ťah je inak ohodnotený podľa toho, ako ďaleko je od kraja hracej plochy. Teraz ich však nemusíte uvažovať.
Riešenia posielajte len počas cvičenia svojmu cvičiacemu na jeho e-mailovú adresu v AIS alebo <meno.priezvisko> <at> stuba.sk. Predmet: [UI] problemik 11.
Nezabudnite uviesť Vaše meno!
Riešenie je možné odovzdať počas cvičenia aj na papieri (ale čitateľné!).