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 egy olyan táblán, amelyen több sorban lyukak vannak. A játékosok egyike, a passzív játékos állítja be a titkos kódot, amit az aktív játékos megpróbál kitalálni a passzív játékostól a tippjeire kapott válaszokból. 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ámokkal, a fekete, illetve fehér válaszpálcikákat a B, illetve W betűkkel jelöltük (jelentésüket lásd a következő szakaszban).

A játék aktív játékosként kipróbálható például itt (a játékhoz Flash szükséges), vagy itt (angol nyelven, Flash nem 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 ezt a kódot az 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 tippeire. Azt mondjuk, hogy a tipp egy bábuja és a kód egy bábuja azonos helyen vannak, ha a tábla azonos 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, mégpedig 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 azonos 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. Más szóval, a fekete válaszpálcikák a pontos, a fehér válaszpálcikák a pontatlan találatok számát adják meg.

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. 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 a 0..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, és
• 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ított 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, míg az Erlang-függvény eredményének a [[3,1,4],[4,1,3]] két elemű 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

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

% :- type code     == list(int).          A code típus egy int típusú elemekből álló listát jelent
% :- type blacks   == int.                A blacks típus azonos az int típussal
% :- type whites   == int.                A whites típus azonos az int típussal
% :- type answer ---> blacks/whites.      Az answer típusú érték egy olyan kétargumentumú struktúra, amelynek
                                          neve '/', első argumentuma blacks típusú, a második pedig whites típusú
% :- type hint   ---> code-answer.        A hint típusú érték egy olyan kétargumentumú struktúra, amelynek
                                          neve '-', első argumentuma code típusú, a második pedig answer típusú

% :- 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.

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

-type code()   :: [integer()].         %% A code() típus egy integer() típusú elemekből álló lista típusa
-type blacks() :: integer().           %% A blacks() típus azonos az integer() típussal
-type whites() :: integer().           %% A whitess() típus azonos az integer() típussal
-type answer() :: {blacks(),whites()}. %% Az answer() típusú érték egy olyan pár, amelynek első eleme blacks(), második eleme whites() típusú.
-type hint()   :: {code(),answer()}.   %% A hint() típusú érték egy olyan pár, amelynek első eleme code(), második eleme answer() típusú.

-spec mmind:mmind(Max::integer(), Hints::[hint()]) -> Codes::[code()].

%% 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: 2018. okt. 27.)

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:

% :- 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 az mmind/3 eljárást.

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

Mint megold/2, de kiírja a feladvány nevét, a megoldások számát és a futási időt, a harmadik paraméterben pedig visszadja a megoldások listáját.

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

A tests mappában levő összes testXXXd.txt tesztfájlra:

lefuttatja a tesztet az első paraméterben megadott, másodpercben értelmezett időkorláttal,

ellenőrzi, hogy a tests mappában lévő testXXXs.txt fájlban megadott megoldáshalmazt kapta-e eredményül,

ha még nem létezik, létrehozza a tests_out_pl mappát,

olvasható formában (lásd megold/2) kiírja az eredményt a tests_out_pl mappában létrehozott testXXXt.txt nevű fájba.

A fenti fájlnevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl.

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 az mmind.pl nevű fájlba tegye be, különben a kmmind.pl keretprogram nem találja meg. Ezután futtassa a SICStus interpretert, és töltse be a keretprogramot. Példák az eljárások meghívására:

SICStus 4.4.1 (x86_64-linux-glibc2.17): Fri Mar 16 07:52:32 PDT 2018
Licensed to BUTE DP18a Course
| ?- [kmmind].
% compiling ...
% compiled ... in module mmind_keret, 18 msec 29792 bytes
yes
| ?- megold('tests/test00d.txt','test00m.txt').
| ?- stopper('tests/test00d.txt','test00m.txt',Sols).
| ?- stopper('tests/test00d.txt','test00m.txt',_).
| ?- teljes_teszt(10).

A megold/2, stopper/3, ill. teljes_teszt/1 eljárás meghívása az 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 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 mmind_ki(FileOut::string(), Codes::[code()]) -> none().

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

-spec megold(FileIn::string(), FileOut::string()) -> none().

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 az mmind:mmind/2 függvényt.

-spec stopper(FileIn::string(), FileOut::string()) -> none().

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

-spec stopper(FileIn::string(), FileOut::string(), FileSol::string()) -> none().

Mint kmmind:stopper/2, de ha a FileSol fájlban értelmezhető megoldás van, ezt összeveti az eredményül kapott mgoldással.

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

A tests mappában lévő összes testXXXd.txt tesztfájlra:

lefuttatja a tesztet Timeout másodperces időkorláttal,

ellenőrzi, hogy a tests mappában lévő testXXXs.txt fájlban megadott megoldáshalmazt kapta-e eredményül,

ha még nem létezik, létrehozza a tests_out_er mappát,

olvasható formában (lásd megold/2) kiírja az eredményt a tests_out_er mappában létrehozott testXXXt.txt nevű fájlba.

A fenti fájlnevekben XXX egy tetszőleges hosszúságú számjegysorozatot jelöl.

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éldák a függvények meghívására:

Eshell V5.7.4  (abort with ^G)
1> l(kmmind).
{module,kmmind}
2> kmmind:megold("tests/test00d.txt","test00m.txt").
3> kmmind:stopper("tests/test00d.txt","test00m.txt").
4> kmmind:stopper("tests/test00d.txt","test00m.txt","test00s.txt").
5> kmmind:teljes_teszt(10).

A keretprogram automatikusan betölti az 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 PDF 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.4 ill. az Erlang R16A 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íz elemű 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.

¹ Ezt az eljárást Eisenberger András ültette át Prologra. Vissza
² Ezt a függvényt Eisenberger András egészítette ki a megoldás ellenőrzésével. Vissza