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.

A játék aktív játékosként például itt kipróbálható (a játékhoz Flash szükséges).

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. Így 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

A megoldandó programozási feladat

Írjon mmind néven olyan Erlang-függvényt, ill. 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!

A függvénynek, illetve 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 feladat megoldásaként az 1..Max értékekből álló összes olyan kódot kell előállítani amely a bemenetnek a fenti értelemben megfelel. A kódok előállításának sorrendje tetszőleges, de egy kódot csak egyszer szabad előállítani.

Az Erlang-függvény kimenete a megoldást alkotó kódok listája. A Prolog-eljárás kimenete egyetlen kód, azonban visszalépések során az összes megfelelő kódot elő kell állítania. Értelemszerűen, ha a súgás-lista ellentmondást tartalmaz, azaz nincs megfelelő kód, akkor az Erlang-függvény az üres listával tér vissza, a Prolog-eljárás pedig meghiúsul.

Természetesen a függvény, ill. 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 felsorolnia, míg az Erlang-függvény eredményének a [[3,1,4],[4,1,3]] kételemű listának kell lennie. A játszma két megoldásának sorrendje mindkét nyelv esetén felcserélhető.

A megírandó függvény és 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.

A mmind:mmind/2 Erlang-függvény típusát a következő - megjegyzésként megadott - Erlang-típusdefiníciók írják le.

%% @type code()   = [integer()].
%% @type blacks() = integer().
%% @type whites() = integer().
%% @type answer() = {blacks(),whites()}.
%% @type hint()   = {code(),answer()}.

%% @spec mmind:mmind(Max::int(),Hints::[hint()]) -> Codes::[code()].
%% @doc  Codes a Hints súgás-listának és a Max maximális kódértéknek
%%   megfelelő összes titkos kód tetszőleges sorrendű listája.

-module(mmind).
-author('email@unit.org.hu').
-vsn('year-mm-dd').
-export([mmind/2]).
%-compile(export_all).

Példa

A 2. ábrán látható példa az alábbi módon adható meg a Prolog-eljárásnak, illetve az Erlang-függvénynek, é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

Erlang

mmind:mmind(4, [{[1,1,1],{1,0}},
                {[1,2,2],{0,1}},
                {[3,1,3],{2,0}}]).
[[3,1,4],[4,1,3]]

Keretprogramok

Programjait keretprogramok segítségével próbálhatja ki. A keretprogramokat a beadáskor használthoz hasonló tesztesetekkel együtt töltheti le:

• Keretprogramok + tesztesetek (ZIP, utolsó módosítás: okt. 28.)

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 Prolog-keretprogram

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 interpretert, és töltse be a keretprogramot. Példa:

SICStus 4.1.1 (x86-linux-glibc2.7): Tue Dec 15 16:13:21 CET 2009
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.

Az Erlang-keretprogram

A kmmind.erl Erlang-keretprogram a következő függvényeket exportálja:

@spec kmmind:mmind_be(FileIn::string()) -> MMind::{integer(),[hint()]}

MMind a FileIn szövegfájlból beolvasott, a Mastermind-feladványt leíró kódértékből és súgás-listából álló pár.

@spec kmmind:mmind_ki(FileOut::string(), Codes::[code()]) -> void()

A Codes listában átadott Mastermind-megoldásokat kiírja a FileOut szövegfájlba.

@spec kmmind:megold(FileIn::string(), FileOut::string()) -> void()

Beolvas egy feladványt a FileIn szövegfájlból és összes megoldását kiírja a FileOut szövegfájlba. Ehhez felhasználja a mmind:mmind/2 függvényt.

@spec kmmind:stopper(FileIn::string(), FileOut::string()) -> void()

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

@spec teljes_teszt(Timeout::integer()) -> [done|timeout].

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

• lefuttatja a tesztet Timeout másodperces 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 a függvényt Eisenberger András egészítette ki a megoldás ellenőrzésével.

Használat: saját mmind.erl nevű programját minden változtatás után fordítsa le, és mmind.beam néven rakja a keretprogrammal azonos mappába, különben a kmmind.erl keretprogram nem találja meg. Ezután indítsa el az Erlang értelmezőt, és töltse be a lefordított keretprogramot. Példa:

Eshell V5.7.4  (abort with ^G)
1> l(kmmind).
{module,kmmind}
2> kmmind:stopper("teszt0.txt","teszt0.sol").

A keretprogram automatikusan betölti a mmind.beam programot, feltéve, hogy a keretprogrammal azonos mappában van.

Ha a saját mmind.erl programját módosítja, a lefordítása után betöltheti az l(mmind). paranccsal, de újra betöltheti a kmmind.erl keretprogramot is, ami magával húzza a módosított programot. Egyes esetekben célszerű újraindítani az Erlang értelmezőt.

Dokumentációs követelmények

Mindkét programot úgy írja meg (választása szerint vagy magyarul, vagy angolul), hogy a szövegük 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, ill. függvények feladatát és működését! Kövesse a Prolog-, ill. az Erlang-diákon használt szövegelrendezési konvenciókat! Javasoljuk, hogy ne írjon 72 karakternél hosszabb sorokat. Minden eljáráshoz és függvényhez készítsen fejkommentet!

A két programhoz készítsen közös 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
• Kódolás Erlang-, ill. Prolog-nyelven, 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, ill. az Erlang R14A rendszerekkel teszteljük.

Megoldásában Prolog nyelven tetszőleges könyvtárakat használhat, kivéve a clpfd, clpq, clpr, clpb és chr Prolog-könyvtárakat: az ezeket a könyvtárakat felhasználó megoldások a létraversenyben nem vehetnek részt, és így megajánlott jegyet sem kaphatnak.

Erlang nyelven az adatbázist vagy egyéb mellékhatást használó függvények használata tilos (erlang:get, erlang:put, digraph modul, io modul stb.). Néhány megengedett, állapotmentes modul: array, dict, gb_*, lists, math, ord*, queue, sets, string.

A programokat és az elektronikus dokumentációt webes felületen lehet majd 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.

Programját egy tízelemű tesztsorozattal automatikusan futtatjuk. A teszteseteket úgy választjuk meg, hogy legalább négy feladványt a kevésbé ötletes programok is meg tudjanak oldani. Az eredményt levélben közöljük és az ETS-ben is megnézhető.

A nagy házi feladat elkészítése nem kötelező, de megoldását mindenkinek javasoljuk: ez a deklaratív nyelvek magas szintű elsajátítását nagy mértékben segíti.

A beadási határidő után értékeljük a programokat (ez az ún. "éles" teszt). Ehhez a beadási tesztsorozathoz hasonló nehézségű teszteseteket használunk. Az időkorláton belül helyes eredményt adó tesztesetek mindegyikére 0,5–0,5 pontot adunk, a 10 tesztesetre tehát nyelvenként összesen maximum 5 pontot. Ezen felül a dokumentációt, a programkód olvashatóságát, kommentezettségét is értékeljük, nyelvenként maximum 2,5 ponttal. A mindkét nyelven beadott nagy házi feladatra tehát maximum 15 pont kapható (ez 15%-a a pluszpontok nélkül elérhető legfeljebb 100 alappontnak).

Azok a programok, amelyek az éles teszt legalább 8 feladatát helyesen és az előírt időkorláton belül megoldják, létraversenyben vesznek részt. A leggyorsabban futó Erlang-, ill. Prolog-programokra - helyezési számuktól függően - külön-külön 7,5 és 0,5 közötti pluszpont kapható. Ha valaki tehát mindkét nyelvből a leggyorsabb programot írja meg, akkor a 100 alapponton felül 15 pluszpontot kap.

Azok a hallgatók, akik mindkét nyelvből bejutnak a létraversenybe - a tantárgyi adatlapon leírt feltételek fennállása esetén - megajánlott jegyet kapnak.

A programot és dokumentációt mindenkinek saját magának kell elkészítenie. A beadott nagy házi feladatokat gépi úton hasonlítjuk össze, másolás esetén fegyelmi eljárást kezdeményezünk. Az algoritmusra vonatkozó ötletek cseréjét viszont nem tiltjuk.