Nagyhatékonyságú deklaratív programozás

Nagy házi feladat

Mastermind

A játék ismertetése

A Mastermind játékot színes kód- és tippbábukkal, fekete és fehér válaszpálcikákkal ketten játsszák olyan táblán, amelyen több sorban lyukak vannak. A játék közismert változatában mind a tipp, mind a kód négy színes bábuból áll, a bábuk hatféle színűek lehetnek.

Az 1. ábrán egy Mastermind játszmát mutatunk be. Itt a tippbábukat az 1..6 számok jelzik, míg a fekete, illetve fehér válaszpálcikákat a B, illetve W betűkkel jelöltük.

Definíciók és jelölések

A passzív játékos feladata, hogy a színes bábukból tetszőleges variációt állítson össze, melyet titkos kódnak nevezünk (röviden kód). Azonos színű bábukból több is lehet a kódban. A passzív játékos e kódot a másik, aktív játékos által nem látható lyukakba helyezi, majd a valóságnak megfelelően válaszol az aktív játékos kérdéseire. Azt mondjuk, hogy a tipp egy bábuja és a kód egy bábuja ugyanazon a helyen vannak, ha a tábla ugyanazon oszlopában vannak, egyébként azt mondjuk, hogy különböző helyen vannak.

Az aktív játékos feladata a titkos kód kitalálása, a lehető legkevesebb lépésben. Minden lépésben tetszőleges variációt állít össze a színes bábukból, melyet tippnek nevezünk, és tippjét a tábla következő üres sorába rakja. A passzív játékos mindegyik tippről közli, hogy milyen közel van a kódhoz: annyi fekete válaszpálcikát rak a táblára, ahány egyforma színű bábu van a tippben és a kódban ugyanazon a helyen, továbbá annyi fehér válaszpálcikát rak a táblára, ahány egyforma színű bábu van a tippben és a kódban különböző helyen.

Mivel a titkos kódban (és így a tippben is) ugyanaz a szín többször is előfordulhat, ezért a fehér válaszpálcika használatát pontosítani kell. Amikor a kódban többször fordul elő egy szín, akkor az adott színű bábuk közül csak annyihoz rendelhető fehér válaszpálcika, ahányszor az adott szín a tippben a nem megfelelő helyen szerepel; ugyanez a megszorítás fordítva is fennáll. A fehér válaszpálcikák számának meghatározása így pl. a következő módon történhet:

1. Elhagyjuk mind a kódból, mind a tippből azokat a bábukat, amelyekre fekete pálcikával válaszoltunk.
2. Minden egyes szín esetén: megszámoljuk az adott színű bábukat a kódban és a tippben, majd ezen két darabszám közül a kisebbikkel megegyező számú fehér pálcikával válaszolunk.

A válaszpálcikák elhelyezése a sorban nem hordoz információt, csak a pálcikák darabszáma számít; így nem lehet tudni, hogy pontosan mely bábukra vonatkoznak. Ennek megfelelően a fekete és fehér pálcikák számából alkotott számpárt válasznak nevezzük. A válasz tehát egy titkos kódhoz és egy tipphez rendelt érték, amely a két bábu-variáció távolságát jellemzi (a 4 fekete és 0 fehér pálcika jelenti azt, hogy a tipp azonos a titkos kóddal).

• Max a megengedett színek száma
• H a kódban szereplő bábuk száma, azaz a kód hossza (értelemszerűen a tippek hossza is H)
• bábu: 1..Max intervallumba eső pozitív egész szám
• titkos kód: H elemű bábulista, az elemsorrend megfelel az oszlopsorrendnek
• tipp: H elemű bábulista, az elemsorrend megfelel az oszlopsorrendnek
• válasz: számpár, mindkét szám az 1..H intervallumba esik

Írjon mmind néven olyan CLPFD alapú Prolog-eljárást, amely a tippek és a hozzájuk tartozó válaszok egy halmazára előállítja a bemeneti adatoknak megfelelő titkos kódokat!

Az eljárásnak két bemenő paramétere van. Az első a Max paraméter, azaz a kódban megengedett maximális érték. A második egy nem-üres lista, a súgás-lista, amelynek elemei a játszma egy-egy lépésének felelnek meg: egy tippet és az arra adott választ tartalmazzák.

A játék H (hossz) paramétere implicit módon van megadva: a (nem-üres) súgás-lista elemeiben szereplő tippek mind H hosszú listák. Nem szükséges ellenőriznie, hogy ezek a listák egyforma hosszúságúak-e.

Azt mondjuk, hogy egy K titkos kód megfelel egy SL súgás-listának és egy Max maximális kódértéknek (színszámnak), ha

• K az 1..Max intervallumba eső egész számokból áll;
• továbbá az SL súgás-lista minden elemére fennáll, hogy az adott súgás-elemben megadott tipp és a K titkos kód együtteséhez a súgás-elemben megadott válasz tartozik.

A megirandó Prolog-eljárás kimenete egyetlen kód, azonban visszalépések során az összes megfelelő kódot elő kell állítania, mégpedig mindegyiket egyszer; a felsorolás sorrendje érdektelen. Értelemszerűen, ha a súgás-lista ellentmondást tartalmaz, azaz nincs megfelelő kód, akkor a Prolog-eljárás meghiúsul.

Természetesen az eljárás által előállítottott kódok hossza is H kell legyen, azaz meg kell egyezzen a bemenő paraméterben szereplő tippek hosszával.

Vegyük például a következő befejezetlen játszmát, amelyben négy szín használható:

Ennek a játszmának két megoldása van, amely megfelel a bemenetnek: [3,1,4] és [4,1,3]. A Prolog-eljárásnak ezt a két megoldást a visszalépések során fel kell sorolnia (tetszőleges sorrendben).

A megírandó eljárás specifikációja

A mmind/3 Prolog-eljárás típusát a következő - megjegyzésként megadott - Prolog-típusdefiníciók írják le.

% :- type code     == list(int).
% :- type blacks   == int.
% :- type whites   == int.
% :- type answer ---> blacks/whites.
% :- type hint   ---> code-answer.

% :- pred mmind(int::in, list(hint)::in, code::out).
% mmind(Max, Hints, Code): Code egy olyan titkos kód, amely megfelel a
%    a Hints súgás-listának és a Max maximális kódértéknek.

Példa

A 2. ábrán látható példa az alábbi módon adható meg a Prolog-eljárásnak, és a megoldást is az itt leírt módon várjuk (de nem feltétlenül ebben a sorrendben).

Prolog

| ?- mmind(4, [[1,1,1]-1/0,
               [1,2,2]-0/1,
               [3,1,3]-2/0], Code).
Code = [3,1,4] ? ;
Code = [4,1,3] ? ;
no

A keretprogram

A keretprogram bemenete egy olyan szövegfájl, amelynek első sora a Max számot, azaz a kódban felhasználható legnagyobb értéket tartalmazza, minden egyes további sorában pedig egy tipp és a rá adott válasz áll. A tipp pozitív egészek egy vagy több szóközzel elválasztott sorozata. Egy vagy több szóköz után következik a válasz, amely a fekete és a fehér válaszpálcikák száma, `/' jellel elválasztva.

A 3. ábra a 2. ábrán bemutatott példát leíró bemeneti fájl tartalmát mutatja.

3. ábra: A keretprogram egy lehetséges bemenete

4   1 1 1 1/0 1 2 2 0/1 3 1 3 2/0

A keretprogram kimenete a 4. ábrán bemutatotthoz hasonló tartalmú szövegfájl.

[[3,1,4],[4,1,3]].

A kmmind.pl Prolog-keretprogram a következő eljárásokat exportálja exportálja:

% :- pred mmind_be(file::in, int::out, list(hint)::out).

A megnevezett szövegfájlból beolvassa a Mastermind-feladványt leíró maximális kódértéket és súgás-listát, és mindkettőt visszaadja.

% :- pred mmind_ki(file::in, list(code)::in).

A megnevezett szövegfájlba kiírja a feladvány második paraméterként átadott összes megoldását.

% :- pred megold(file::in, file::in).

Beolvas egy feladványt az első paraméterrel megnevezett szövegfájlból, és kiírja az összes megoldását a második paraméterrel megnevezett szövegfájlba. Ehhez felhasználja a mmind/3 eljárást.

% :- pred stopper(file::in, file::in).

Mint megold/2, de a végén kiírja a feladvány nevét, a megoldások számát és a futási időt is.

% :- pred teljes_teszt(int::in).

A tests könyvtárban levő összes testXXXd.txt tesztállomány esetén:

• lefuttatja a tesztet az első paraméterben megadott, másodpercben értelmezett időkorláttal,
• ellenőrzi, hogy a testXXXs.txt állományban megadott megoldáshalmazt kapta,
• olvasható formában (lásd megold/2) kiírja az eredményt a tests_out könyvtár testXXXt.txt nevű állományába.

A fenti állománynevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl.
Ezt az eljárást Eisenberger András ültette át Prologra.

A keretprogram felhasználja a file típust:

% :- type file == atom.

A file típusú paraméterben a user atomot megadva a terminálról vihetünk be, ill. a terminálra írathatunk ki adatokat. Egyébként a megadott nevű fájlba írunk, ill. fájlból olvasunk.

Használat: saját programját a mmind.pl nevű fájlba tegye, különben a kmmind.pl keretprogram nem találja meg. Ezután futtassa a SICStus Prolog rendszert, és töltse be a keretprogramot. Példa:

SICStus 4.3.5 ...
Licensed to BUTE-DP-course
| ?- [kmmind].
% compiling ...
% compiled ... in module mmind_keret, 15 msec 29792 bytes
yes
| ?- stopper('teszt0.txt','teszt0.sol').

A stopper/2, ill. megold/2 eljárások meghívása a mmind.pl programot automatikusan betölti (ha szükséges), ezért ennek módosításakor nem kell sem a SICStus interpretert újraindítania, sem a keretprogramot újra betöltenie.

Dokumentációs követelmények

A programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövege jól olvasható legyen: válasszon értelmes neveket, specifikálja a paraméterek és más azonosítók szerepét és értelmezési tartományát, magyarázza meg az egyes eljárások feladatát és működését! Kövesse a diákon használt szövegelrendezési konvenciókat! Minden eljáráshoz készítsen fejkommentet!

A programhoz készítsen dokumentációt; vagy magyarul, vagy angolul. A dokumentáció tartalma legalább a következő legyen:

• Követelmények elemzése
• Tervezés, az egyes eljárások, ill. függvények specifikálása
• CLP modellezés, korlátok megválasztása, kódolás Prologban, az algoritmusok ismertetése
• Tesztelési megfontolások
• Kipróbálási tapasztalatok

Fogalmazzon világosan és tömören, ügyeljen a helyes nyelvhasználatra és a helyesírási szabályok betartására! Az indokoltan elvárható formai követelmények be nem tartását, a gondatlan kivitelt szankcionáljuk.

A dokumentációt elektronikus alakban adja be HTML, PDF, esetleg ASCII formátumban.

Egyéb követelmények és tudnivalók

A programok készülhetnek MS Windows alatt is, de Linux alatt is működniük kell. A beadott programokat Linux környezetben a SICStus Prolog 4.x.y, rendszerrel teszteljük.

A programokat és az elektronikus dokumentációt webes felületen lehet külön-külön feltölteni az Elektronikus Tanársegéd HF beadás menüpontjában. A beadást többször is megismételheti, az utoljára beadott megoldást tekintjük érvényesnek.