Zápočtový program (Prolog)

Miroslav Spousta

1. Zadání

Zadání č. 340 -- hra NIM. Z daných N hromádek zápalek odebírají dva soupeři.
Ukončení a povolené tahy:

kdo nemá tah, prohrál
v jednom tahu lze odebírat zápalky jen z jedné hromádky
tahy jsou definovány speciálním programem v Prologu

Úkolem je odehrát optimální strategii pro tuto hru.

2. Rozbor

2.1. Zavedení pojmů

"pozice" (position) je stav hry (např. "4, 2, 3" je jeden ze stavů pro hru se třemi hromádkami).
"cílová pozice" je pozice po provedení tahu.
"prohrávající pozice" (lost position) je taková pozice, že ať táhnu jakkoli, soupeř může vyhrát.
"vyhrávající pozice" (winning position) je pozice ze které můžu táhnout na prohrávající pozici.

2.2. Rozbor hry

Hra začíná na smluvené pozici. Soupeři střídavě odebírají povolené počty zápalek. Kdo nemůže táhnout, prohrál. Hra je konečná, protože se každým tahem snižuje počet zápalek na hromádkách. Každá pozice hry může být ohodnocena jako:

silně prohávající <=> všechny tahy vedou na pozici slabě vyhrávající nebo neexistuje žádný tah (tedy ať táhnu jakkoli, vždy dostanu soupeře do vyhrávající pozice nebo nemám tah a potom jsem právě prohrál).
slabě vyhrávající <=> existuje tah na pozici silně prohrávající (tedy můžu táhnout tak, abych soupeře buď dostal do silně prohrávající pozice a nebo do pozice kde nemá žádný tah).

Musí být každá pozice jedním z těchto případů? Ano, první podmínka je totiž negací druhé a opačně. (Když existuje tah na silně prohrávající pozici tak neplatí, že všechny tahy vedou na pozice slabě vyhrávající.)

2.3. Jak to naprogramovat? -- Popis algoritmu

Úkolem je odehrát optimální strategii. To znamená, že potřebujeme (1) najít ohodnocení zadané pozice a (2) doporučit (co možná nejlepší) tah. Jak toho dosáhnout?

První úkol splníme tak, že budeme postupně zkoumat všechny pozice (od 0, 0, ..., 0) až po zadanou pozici a získané výsledky si budeme ukládat. Pro každou zkoumanou pozici zjistíme všechny z ní přípustné tahy. Ohodnocení cílových pozic těchto tahů již známe (neboť provedením tahu se sníží počet zápalek na jedné z hromádek). To nám stačí k určení hledaného ohodnocení pozice jako (silně) prohrávající nebo (slabě) vyhrávající. Neexistuje-li z některé pozice žádný tah, označíme ji jako prohrávající.

Druhý úkol je pak již jednoduchý. Podíváme se do uložených výsledků,
zjistíme ohodnocení pozice a vrátíme:

je-li vyhrávající -- jeden z tahů na prohrávající pozici
je-li prohrávající -- jeden z možných tahů
neexisuje-li tah -- prázdný argument (konec hry).

3. Realizace programu

Program je napsán v programovacím jazyku Prolog.

3.1. Reprezentace dat v programu

3.1.1 Reprezentace jedné pozice

Pro reprezentaci pozice jsem použil seznam, zejména kvůli snadné implementaci a možnosti adaptování na libovolný počet hromádek.

3.1.2. Reprezentace pozic s již známým ohodnocením

Je zřejmé, že v průběhu výpočtu si nemusím pamatovat ohodnocení každé pozice, ale jen seznam buď prohrávajících nebo seznam vyhrávajících pozic. Zvolil jsem první variantu, ale myslím, že stejně dobře jsem mohl zvolit druhou.

Samotné uložení pozic bylo možné realizovat dvěma způsoby:

uložit každou pozici do databáze Prologu
uložit do seznamu a ten teprve do databáze.

Netestoval jsem rychlost obou variant, ale předpokládám, že ukládání do databáze je časově náročnější než práce se seznamem. Proto jsem zvolil druhou variantu.

Prohrávající pozice jsou uloženy v databázi jako predikát nim_lostdb/2:

nim_lostdb(List1, List2)

kde List1 je největší prozkoumaná pozice a List2 seznam těch pozic, které
jsou prohrávající od 0, 0, ..., 0 až po List1.

3.1.3. Implicitní pozice

Implicitní pozice (viz. 3.3.1.) se ukládá do databáze prologu jako predikát nim_defpos/1:

nim_defpos(List)

kde List je pozice.

3.1.4. Reprezentace možných tahů

Je řešena jako externí program v jazyku Prolog. Každý tah je určen predikátem move/2:

move(+Pos1, -Pos2)

který musí uspět pravě když existuje tah z pozice Pos1 a vrátit cíl tahu -- pozici Pos2. Na žádnou z hromádek nesmí provedením tahu přibýt zápalka a Pos2 musí obsahovat méně zápalek než Pos1. Ve stejném externím programu jako tahy musí být definován také predikát heaps/1 (parametr je celé číslo) určující počet hromádek se kterým pracuje predikát move/2.

3.2. Popis programu

Celý program je možné rozdělit na několik částí:

"seznamové" podprogramy -- generování, porovnávání, maximum ze dvou seznamů...
podprogramy na generování a testování pozic (jsou-li prohrávající)
user-interface podprogramy -- čtení řádky textu, převod string -> číslo, výpis nápovědy, seznamu prohrávajících pozic, volání hlavních klauzulí...
hlavní klauzule generate/2 a explore/3 -- generate vytvoří databázi prohrávajících pozic, explore vrátí ohodnocení pozice a doporučený tah.
klauzule nim/1 -- hlavní klauzule zajišťující načtení databáze tahů a interakci s uživatelem.

3.3. Popis rozhraní

3.3.1. Uživatelské rozhraní

Po načtení souboru (consult('nim.pl').) se interaktivní rozhraní spustí jako volání klauzule "nim.".
Program požádá o zadání názvu souboru s tahy:

enter filename with move specs [moves]:

(implicitně je nastaveno "moves.pl", při akceptování inplicitního nastavení stačí vždy stisknout enter). Potom přečte databázi tahů, vypíše nakolika hromádkách se hraje a požádá o zadání požadované pozice:

moves compiled, 0.01 sec, 1,052 bytes. loading moves.. done. number of heaps: 2 enter current heaps (or type "help") [5, 5]:

(implicitně se nastaví 5, 5, ..., 5). Nyní můžeme napsat požadovanou pozici (např. 7, 9) a stisknout enter. Program odpoví:

[7, 9] is losing position, possible move: [3, 9]. enter current heaps (or type "help") [3, 9]:

Což znamená, že pozice "7, 9" je prohrávající a doporučí nám jeden z možných tahů (odebrat 4 zápalky z první hromádky, tedy hrát na pozici "3, 9". Implicitní hodnota se nastaví také na tuto pozici. Dalším stiskem enter dostaneme:

[3, 9] is winning position, possible move: [1, 9].

a tak dále až do pozice ze které již neexistuje žádný tah:

[0, 0] is losing position, no moves found.

Možnosti vstupu (na výzvu "enter current heaps..."):

seznam čísel -- vypíše informace o této pozici
"help" -- on-line nápověda
"list" -- vypíše aktuální databázi prohrávajících tahů uloženou v paměti.
"clear" -- zruší aktuální databázi prohrávajících tahů
"bye" -- konec práce s programem

Oddělovače čísel tvoří mezera, čárka, znaky '[' a ']', takže můžeme též napsat např: "[[3]4,,13[" ve významu stejném jako "3, 4, 13".

3.3.2. Programový interface

Hlavní klauzule lze volat samostatně, pokud jsou definovány tahy (predikátem move/1). Toto lze splnit například přečtením souboru s tahy (predikátem consult(file).)

Chceme-li zjistit ohodnocení některé pozice, je třeba:

vygenerovat seznam prohrávajících pozic klauzulí generate/2:
generate(+Pos, +Heaps)
kde Pos je požadovaná pozice a Heaps je počet hromádek (musí souhlasit s počtem hromádek pro který jsou definované tahy (move/2); seznam se generuje pouze pokud již není uložen v databázi.
zjistit ohodnocení a doporučený tah: klauzulí explore/3:
explore(+Pos, -Newpos, -Code)
kde Pos je požadovaná pozice, Newpos je doporučený tah a Code =
- 0 pokud neexistuje tah, prohrávající pozice
- 1 pokud exisuje tah, pozice je prohrávající
- 2 pokus existuje tah, pozice je vyhrávající.

4. Dodatky

Program je napsán v jazyku Prolog. Odlaďen a vyzkoušen byl v implementaci SWI-Prolog (Version 3.2.8).
Program používá tyto standartní predikáty: get0/1, write/1, nl/0, fail/0, retractall/1, assertz/1, repeat/0, consult/1 a porovnávání celých čísel.