1. Prehra na šachovnici vzorové riešenie

Zadanie

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Žabovi na

Kika s Andrejom išli spolu na výlet do Tatier. Prenajali si malú chatku uprostred hôr, z ktorej sa každý deň chystali chodiť na rôzne horské túry. Avšak hneď v prvý deň ráno začalo strašne pršať a nikam ísť nemohli. Ostali teda uväznení na chate, a keďže tam nebol žiaden signál, začali sa strašne nudiť.

Snažili sa teda nájsť čokoľvek, čím by sa mohli zabaviť. Ale jediná vec, ktorú našli, bola stará šachovnica s figúrkami. Ani jeden z nich však nevie hrať šach, akurát vedia ako sa hýbu jednotlivé figúrky, preto si vymysleli nasledovnú hru.

Na niektoré políčko šachovnice položia figúrku koňa. Následne sa striedajú v ťahoch – ťah spočíva v tom, že hráč presunie koňa podľa šachových pravidiel na iné políčko šachovnice. Naviac musí platiť, že v každom ťahu sa kôň posunie bližšie k ľavému dolnému rohu šachovnice. Formálne, očíslujme si riadky šachovnice odspodu po vrch číslami 1 až 8 a stĺpce šachovnice zľava doprava číslami 1 až 8. Potom musí platiť, že každým ťahom sa súčet súradníc, na ktorých stojí kôň zmenší. Na nasledujúcom obrázku si môžete pozrieť všetky možné ťahy, ktoré môže šachový kôň spraviť – kôň sa pohybuje v L-ku, ktorého ramená sú dĺžky 3 a 1. Štyri z týchto ťahov sú prípustné (označené zelenou fajkou), lebo zmenšujú súčet súradníc a štyri z nich sú nepovolené (označené červeným krížikom). Samozrejme, ak sa kôň nachádza na kraji šachovnice, niektoré z ťahov hráč nemôže spraviť, lebo by dostal koňa mimo šachovnicu.

Hráč, ktorý už koňom nemôže pohnúť (lebo sa nachádza v niektorom zo 4 políčok v ľavom dolnom rohu) prehráva. No a keďže Andrej je gentleman, Kika začína ako prvá.

Úloha

1. (3 body) Na obrázkoch nižšie sú zobrazené dve možné začiatočné pozície. Pre každú z nich rozhodnite, ktorý hráč vie zvíťaziť, ak budú hrať obaja optimálne. Pýtame sa teda, ktorý z hráčov vie vyhrať bez ohľadu na to, aké ťahy spraví jeho protivník. Pre obe situácie popíšte aj spôsob, akým vie daný hráč vyhrať.

2. (7 bodov) Pre každú pozíciu šachovnice \(8\times 8\) zistite, či sa podarí Kike zvíťaziť, ak bude kôň na začiatku na tejto pozície. Výsledok zapíšte do tabuľky \(8\times 8\), kde na pozíciu, z ktorej Kika vie vyhrať zapíšete číslo 1 a na pozíciu, z ktorej Kika prehrá zapíšete 0. Teda štyri políčka v ľavom dolnom rohu budú obsahovať 0, pretože ak sa na ne položí kôň, Kika nebude môcť spraviť žiaden ťah a prehrá.

   Popíšte, akým spôsobom ste túto tabuľku vypĺňali a zdôvodnite, prečo je váš postup naozaj dobrý. Potom sa pokúste zovšeobecniť váš postup aj pre šachovnice ľubovoľných rozmerov – teda veľkosti \(r\times s\). Skúste preto popísať sadu pravidiel, podľa ktorých by ste vedeli vyplniť ľubovoľne veľkú tabuľku.

3. (5 bodov) Keď ich táto verzia prestala baviť, hru si ozvláštnili tým, že na šachovnicu položili viacero koní (kľudne aj viac ako štyroch). V jednom ťahu si mohol hráč vybrať ľubovoľne veľa koní (ale aspoň jedného) a každého z nich posunúť podľa predošlých pravidiel. Nevadilo dokonca ani to, ak sa viacero koní ocitlo na tom istom políčku.

   Pomôžte Kike nájsť spôsob akým môže vyhrať, poprípade zistite, že vyhrať nevie. Napíšte teda postup, ktorým sa má v každom kroku riadiť. Tento postup musí byť dosť všeobecný, aby sa dal použiť pri ľubovoľnej situácii, ktorá na šachovnici nastane. Pri riešení môžete použiť tabuľku z podúlohy b).

V úlohe ste mali riešiť pomerne jednoduchú hru na šachovnici. Postupy, ktoré si ukážeme v tomto vzorovom riešení sú však aplikovateľné aj na oveľa zložitejšie hry. Pustime sa teda do toho.

Podúloha a)

Na prvom obrázku máme koňa na políčku \((5, 5)\) (pri označovaní pozície budeme najskôr písať číslo riadku a potom číslo stĺpca). Našou úlohou je zistiť, ktorý hráč vyhrá ak budú obaja hrať optimálnym spôsobom. Kika ťahá ako prvá.

Prvá otázka je, čo vlastne znamená, že hráči hrajú optimálne. V podstate si to vieme predstaviť tak, že ak existuje spôsob, akým vie jeden z nich vyhrať za každých okolností a bez ohľadu na to, čo spraví jeho súper, tak sa bude podľa toho riadiť a skutočne vyhrá. Musí však vždy existovať takáto vyhrávajúca postupnosť ťahov? Ako uvidíme neskôr, musí.

Zatiaľ však nevieme spraviť nič iné, ako vyskúšať všetky možnosti. Kam teda môže Kika pohnúť koňa v prvom ťahu? Iba na pozície \((3,6)\), \((3,4)\), \((4,3)\) a \((6,3)\). Všimnime si, že tieto pozície sú si navzájom symetrické. Ak teda bude existovať vyhrávajúca postupnosť ťahov začínajúca ťahom na \((3,6)\), bude existovať aj úplne rovnaká postupnosť ťahov pre začiatok \((6,3)\), akurát vždy vymeníme riadok a stĺpec políčok, na ktoré sa máme posunúť. Pokračujme teda iba s políčkami \((3,6)\) a \((3,4)\).

Predstavme si, že Kika posunula koňa na políčko \((3,4)\). Na ťahu je teraz Andrej a možnosti, kam sa vie pohnúť sú \((1,5)\), \((1,3)\), \((2,2)\) a \((4,2)\). No ale políčko \((2,2)\) je jedno zo štyroch finálnych políčok. Hneď ako Andrej posunie koňa na toto políčko vyhral, pretože Kika už nebude môcť spraviť ďalší ťah. Ak chce Kika vyhrať, tak sa preto nemôže posunúť na políčko \((3,4)\), lebo Andrej (ktorý hrá optimálne a nemýli sa) by vedel vyhrať.

Ostáva teda možnosť, v ktorej sa Kika posunie na políčko \((3,6)\). V tomto prípade má Andrej nasledovné možnosti, kam môže koňa posunúť: \((1,7)\), \((1,5)\), \((2,4)\) a \((4,4)\). Ani z jedného z týchto políčok nevie Andrej vyhrať okamžite, tak ako v predchádzajúcom prípade. Mali by sme teda opäť skúsiť všetky možnosti. Všimnime si však, že políčko \((2,4)\) je príliš blízko cieľa a Kika by zneho vedela hneď vyhrať pohybom na \((1,2)\). Tam teda Andrej ťahať nebude. Nádejne však vyzerá políčko \((1,5)\). Z neho má totiž Kika iba jednu možnosť ako sa pohnúť a to na políčko \((2,3)\). A ak sa Kika pohne na políčko \((2,3)\), tak Andrej sa pohne na \((1,1)\) a vyhrá.

Keď sa teda Kika posunie na \((3,6)\), tak Andrej spraví krok na políčko \((1,5)\) čím si zaručí, že Kika potiahne na \((2,3)\) a on v ďalšom kole vyhrá ťahom na \((1,1)\). Vidíme teda, že bez ohľadu na to, čo spraví Kika, Andrej to vie zahrať tak aby vyhral. Pre Andreja teda existuje vyhrávajú stratégia, ktorá je znázornená aj na obrázku nižšie. Červenou sú znázornené všetky ťahy, ktoré môže robiť Kika a modrou ťahy, ktoré bude robiť Andrej s cieľom vyhrať.

V tejto podúlohe bol však aj druhý obrázok, v ktorom bol kôň na začiatku na políčku \((6,7)\). Musíme opäť skúšať všetky možnosti? Nie, ak budeme šikovný a všimneme si, že jeden z možných ťahov, ktoré vie Kika spraviť je posunúť koňa na políčko \((5,5)\). Čo je presne predchádzajúci prípad. A o tom sme si ukázali, že hráč, ktorý začína s koňom na pozícii \((5,5)\) zaručene prehrá. Keď však Kika spraví prvý ťah na políčko \((5,5)\), v podstate vytvorí novú hru, kde kôň začína na políčku \((5,5)\) a začínajúcim hráčom je Andrej. Tým pádom bude Kika vedieť robiť to isté čo Andrej pred chvíľou a tým pádom vyhrať. V druhej hre preto zvíťazí Kika.

Podúloha b)

V podúlohe b) je našou úlohou vyplniť celú tabuľku \(8\times 8\) číslami 0 a 1, pričom 0 znamená, že ak bude kôň na začiatku na tejto pozícii, Kika prehrá a 1 znamená, že z tejto pozície Kika vyhrá. Napríklad sme už zistili, že okrem štyroch rohových políčok, bude 0 aj na políčku \((5,5)\). Na políčku \((6,7)\) však bude 1, lebo z tejto pozície Kika vyhrá.

Toto označenie však nie je úplne najšťastnejšie, lebo na definovanie používa Kiku. Ak by teda napríklad Kika nezačínala, museli by sme všetky čísla prepísať. Namiesto toho budeme používať nasledovné dva pojmy:

• prehrávajúca pozícia (označená 0) – ak je kôň na tejto pozícii, hráč, ktorý je na ťahu prehrá
• vyhrávajúca pozícia (označená 1) – ak je kôň na tejto pozícii, hráč, ktorý je na ťahu vyhrá

Vcelku jednoduché a stále je to tá istá vec, ktorú po nás chcelo zadanie. Všimnime si teraz, čo to znamená, pre náš druhý príklad. Kika začínala na pozícii \((6,7)\), ktorá ako už vieme je vyhrávajúca. Následne koňa presunula na pozíciu \((5,5)\), ktorá je prehrávajúca a naozaj, Andrej, ktorý bol v tom momente na ťahu vyhrať nevedel. Táto pozícia bola pre neho ako hráča naťahu naozaj prehrávajúca.

Pozrime sa teraz na nasledovný obrázok. Sú na ňom vyznačené políčka, o ktorých zaručene vieme, že sú vyhrávajúce. Z každého z týchto políčok sa totiž vieme posunúť do jedného zo štyroch rohových miest. Tieto rohové pozície sú prehrávajúce, lebo ak sa na nich ocitne kôň, hráč, ktorý je na ťahu prehrá. A teda hráč, ktorý vie koňa premiestniť zo svojej pozície na jedno z týchto políčok je vo vyhrávajúcej pozícii.

Z týchto pozorovaní vieme vyvodiť dve pravidlá:

• Pozícia je vyhrávajúca, ak aspoň jeden ťah, ktorý z tejto pozície vedie, ide do prehrávajúcej pozície.
• Pozícia je prehrávajúca ak všetky ťahy z tejto pozície vedú do vyhrávajúcej pozície.

Správnosť týchto úvah je zjavná. Ak z našej pozície vedie ťah do prehrávajúcej pozície, môžeme tento ťah spraviť, náš súper sa ocitne v prehrávajúcej pozícii a teda vieme vyhrať. Naopak, ak sme v prehrávajúcej pozícii, nech spravíme čokoľvek, stav, v ktorom sa ocitne náš súper po ľubovoľnomi našom ťahu bude vyhrávajúci a preto prehráme. Tieto dve definície sa navyše doplňujú a preto pre každé políčko platí práve jedna z nich – každé políčko je teda buď prehrávajúce alebo vyhrávajúce.

Ako teda v mriežke \(r\times s\) zitíme, ktoré pozície sú prehrávajúce a ktoré vyhrávajúce? Vždy keď chceme o nejakom políčku \((x,y)\) zistiť, či je vyhrávajúce alebo prehrávajúce, potrebujeme túto informáciu poznať o políčkach \((x+1, y-2)\), \((x-1, y-2)\), \((x-2, y+1)\) a \((x-2, y-1)\). Pričom o štyroch rohových políčkach vieme, že sú prehrávajúce. Naviac, aby sme tieto informácie mali vždy k dispozícii, budeme tieto hodnoty počítať po diagonálach.

Pre každé políčko sa teda pozrieme na všetky štyri políčka, na ktoré sa z neho vieme dostať. Ak je medzi nimi aspoň jedna 0, tak vieme, že toto políčko je vyhrávajúce (označíme 1) a ak sú medzi nimi iba 1, tak toto políčko bude prehrávajúce. Tento postup bude samozrejme fungovať pre ľubovoľne veľkú šachovnicu.

mohli postupne vypočítať hľadané hodnoty.

Podúloha c)

V tejto podúlohe je na šachovnici položených viacero koní. To, že je viac koní na jednom políčku nám neprekáža a v jednom ťahu môže hráč posunúť ľubovoľne veľa koní podľa predchádzajúcich pravidiel. Musí však posunúť aspoň jednu figúrku.

Ak chceme riešiť podobnú úlohu, asi je dobré si ju vyskúšať s dvoma, troma koňmi a sledovať, ako sa takáto hra správa. To však v tomto vzorovom riešení robiť nebudeme. Skúsime sa nad tým iba zamyslieť. Všimnime si, že hráči hrajú akoby viacero hier naraz, pričom v každom ťahu môžu spraviť ťah v ľubovoľnom množstve týchto hier.

Často nám tiež pomôže, ak sa zamyslíme, čo je úplne posledná pozícia, ktorá v tejto hre nastane. Je jasné, že hra skončí ak budú všetky kone v štyroch rohových políčkach šachovnice. Teda na políčkach, kde boli v predpošlej hre napísané 0.

S týmto pozorovaním už vieme vymyslieť správne riešenie. Toto riešenie definuje vyhrávajúce a prehrávajúce pozície nasledovne:

• Pozícia je prehrávajúca, ak všetky kone stoja na políčkach s číslom 0 (čísla vypočítané v predchádzajúcej podúlohe.)
• Pozícia je vyhrávajúca, ak aspoň jeden kôň stojí na políčku s číslom 1 (čísla vypočítané v predchádzajúcej podúlohe.)

Ostáva už len dokázať, že takéto riešenie je správne, teda overiť, že z každej vyhrávajúcej pozície vedie ťah do prehrávajúcej pozície a z každej prehrávajúcej vedú všetky ťahy do vyhrávajúcej pozície (prečítajte si túto vetu ešte raz a poriadne sa zamyslite čo hovorí).

Ak sme vo vyhrávajúcej pozícii, niektoré kone (aspoň jeden) stoja na políčkach s číslom 1. Toto sú hry, v ktorých vyhrávame (sme v ich vyhrávacej pozícii). Ak sa teda každým z týchto koní posunieme na políčko s 0 (podľa podúlohy b) takéto políčko existuje), súper ostane v situácii, keď budú všetky kone na políčku s 0 a teda bude v prehrávajúcej pozícii.

Naopak, ak sme v prehrávajúcej pozícii a pohneme ľubovoľným koňom, posunieme ho na políčko s číslom 1. A keďže aspoň jedného koňa pohnúť musíme, zanecháme našeho súpera vo vyhrávajúcej pozícii bez ohľadu na to, čo spravíme.

Ak chce teda Kika vyhrať, musí spraviť nasledovné. Pre každé políčko šachovnice si spočíta, či je daná pozícia 0 alebo 1, presne tak ako v podúlohe b). Následne pohne každého koňa, ktorý stojí na pozícii s číslom 1 na pozíciu s číslom 0. Tým zanechá Andreja v pozícii so samými 0 a Andrej prehrá. Ak však na začiatku všetky kone stoja na pozícii s 0, tak Kika vie, že prehrá bez ohľadu na to čo spraví.

Postupy, ktoré ste videli v tomto vzorovom riešení sa dajú aplikovať všeobecne. Definícia prehrávajúcich a vyhrávajúcich pozícii bude zakaždým rovnaká, aj keď ich počítanie môže byť rôzne. S ich pomocou by sme teda mali byť schopní vyhrať ľubovoľnú hru dvoch hráčov, ktorú neovplyvňuje náhoda (Monopoly alebo Človeče asi víťaznú stratégiu nemá) a takisto žiadna informácia nie je skrytá (napr. kartové hry, v ktorých náš ťah závisí od toho, aké karty má na ruke náš protihráč). Napríklad pre hru šach existuje víťazná (v skutočnosti skôr neprehrávajúca, teda vedúca k remíze) stratégia. Jediný problém je, že šach má natoľko rôznych možných ťahov a stavov, že sa nám pre ňu nedarí zistiť, ktoré pozície sú vyhrávajúce a ktoré prehrávacjúce. S dostatočne silným počítačom (ktorý zatiaľ ešte neexistuje) by sme to však mali vedieť zistiť.