Miroslav Týnovský (tynovsky (at) seznam (dot) cz)
Hru NIM hrají dva hráči tak, že se střídají v odebírání zápalek z několika hromádek. V jednom tahu smí hráč odebrat nějaký počet zápalek z právě jedné hromádky. Kdo táhne poslední prohrává. Počet odebíraných zápalek v jednom tahu, celkový počet zápalek a počet hromádek se stanovuje před zahájením hry.
Je dáno N - maximální počet zápalek, K - maximální počet hromádek a I - výčet počtů zápalek odebíraných v jednom tahu. Pro každé rozmístění maximálně N zápalek na maximálně K hromádek (dále jen pozice) chceme určit, zda hráč, který je na tahu, prohraje nebo vyhraje (a případně výherní strategii).
Po načtení souboru spustíme program zavoláním klauzule start.
Program požádá o zadání maximálního počtu sirek, maximálního počtu hromádek a seznamu možných počtů odebíraných zápalek. Po korektním zadání vygeneruje pozice s ohodnocením, v případě vyhrané pozice uvede prohranou pozici, na kterou lze táhnout. Při čtení odspodu lze tak najít celou cestu výherní strategie.
Pro naprogramování této úlohy je třeba vyřešit dva dílčí problémy:
Prvním je, jak vygenerovat všechny pozice bez zbytečných symetrií (permutací stejného rozmístění). Jednoduchý způsob, jak symetrie odstranit, je generovat pozice jako uspořádané posloupnosti K čísel reprezentující počet zápalek v jednotlivých hromádkách.
Druhým (a obtížnějsím) problémem je, jak u pozice určit, zda je vyhraná nebo prohraná, a v případě vyhrané pozice najít způsob, jak výhry dosáhnout.
Definujme prohrávající pozici jako pozici, ze které všechny tahy vedou na pozici vyhrávající a pozici vyhrávající jako pozici, ze které existuje tah vedoucí na pozici prohrávající. Důležitým pozorováním je, že každá pozice může být ohodnocena jako vyhrávající nebo prohrávající. To plyne z toho, že jedna definice je negací druhé. Ohodnotit tedy znamená pro danou pozici vyzkoušet všechny tahy a ověřit, zda některá ze vzniklých pozic je prohraná (nebo zda všechny vzniklé pozice jsou vyhrané).
Pokud budeme pozice generovat a ohodnocovat tak, že všechny tahy z právě vygenerované pozice vedou na pozice již ohodnocené, pak máme zajištěno korektní ohodnocení každé pozice. Samozřejmě, pozice, z nichž neexistuje žádný tah, ohodnotíme triviálné jako vyhrané.
Pro reprezentaci pozice je použita zřejmě nejpřirozenější alternativa - seznam hromádek, kde každá hromádka je reprezentována jako číslo odpovídající počtu sirek.
Díky tomu, že ohodnocení nabývá pouze dvou stavů, můžeme ohodnocené pozice reprezentovat jako seznam prohraných nebo seznam vyhraných pozic. V programu je uchováván seznam prohraných pozic.
Tahy jsou implementovány jako klauzule, které pro zadaný seznam I (výčet počtů odebíraných zápalek) a pozici odpovídají všechny pozice vzniklé odebráním "něčeho z I" z některé z hromádek.
Jednou z možností, jak algoritmus v Prologu implementovat je napsat (zjednodušeně)
(1) klauzuli, které by pro dané N a K odpovídaly všechny pozice
(2) klauzuli, která by pro danou pozici a seznam známých prohraných pozic určila, zda je pozice vyhravající nebo prohrávající
a klauzuli (2) zavolat v klauzuli (1).
Nevýhodou tohoto přístupu je, že je třeba nějak globálně uchovávat seznam prohraných pozic. Musel by se ukládat do prologovské databáze, což je časově náročné.
Použitá implementace sice není tak přímočará, zato však nevyžaduje ukládání seznamu prohraných pozic. Klauzule, které odpovídají všechny pozice pro dané N a K, je nahrazena klauzulí která pro danou pozici vygeneruje následující. Díky tomu je vygenerování všech pozic zajištěno rekurzivním voláním, a tak může být seznam prohraných pozic předáván jako argument.
Podrobnější popis jednotlivých klauzulí je uveden v komentářích ve zdrojovém kódu programu.
Asi není třeba ovládat program jinak než standardním rozhraním, snad jediné smysluplné by mohlo být zavolání klauzule
prohrana(+Icka, +Pozice, +Prohrane, _). ,
ktere pro
Icka ... seznam počtů odebíraných zápalek
Pozice ... nějaká pozice
Prohrane ... seznam známých prohraných pozic
určí, zda z Pozice vede nějaký tah na nějakou pozici z Prohranych a pokud ano, vypíše "vyhraná", v opačném případě vypíše "prohraná".
Program je napsán v jazyce Prolog, odladěn a vyzkoušen byl v implementaci SWI-Prolog verze 5.1.0