Zdroj: http://www.lenivyrodic.sk

Hru Mastermind zřejmě všichni mí čtenáři znají: hrají ji dva hráči, přičemž jeden se snaží uhodnout barevnou kombinaci zvolenou druhým, který přesnost pokusů oceňuje udělením takového počtu černých (případně barevných) kolíků, kolik posic má hádající hráč správně, a takového počtu kolíků bílých, kolikrát se hádající strefil do barvy, ale ne do posice, přičemž je-li posici udělen černý kolík, nemůže již dostat bílý.

Klasický Mastermind se hraje se šesti barvami a čtyřmi posicemi, jeho vylepšená verse má barev osm a posic pět. Ta se distribuovala pod názvem Super Mastermind nebo Logik, pod kterýmžto názvem se vyráběla od konce 70. let i v Československu.

Donald Knuth ukázal již v r. 1976, že pro vyřešení Mastermindu postačí pět pokusů, přičemž ale není dostatečná naivní strategie, kdy každý další pokus může být hledanou kombinací, nýbrž za určitých okolností musí být zvolena kombinace, která úlohu zcela určitě neřeší (tj. je v rozporu s výsledkem některého předchozího pokusu).

Chtěl bych Mastermind ve versi Logik, v obou směrech, tedy počítač jako sestavující i hádající hráč, implementovat pro PMD 85. Jeho paměťová kapacita a malý výkon CPU se arci prozatím ukazuje neřešitelnou překážkou, a nejsem si jist, zda ji budu schopen překonat.

Pro sestavování vhodného pokusu existuje celá řada strategií, popsaných dobře např. v této práci, od Knuthova minimaxového algorithmu po genetické algorithmy, které populaci vhodných pokusů postupně kultivují.

Zásadním problémem je redukce stavového prostoru. Kombinací je 8^5, tj. 32768, a takový počet mohu do paměti PMD umístit (jsou to pouhé 4 kilobyty), ale mám-li všechny možnosti projít, např. abych zjistil, zda odpovídají výsledku, který počítači avisoval hráč, dostávám se do potíží, protože každých 62 T-stavů, které s pokusem strávím, znamená ve výsledku jednu sekundu; a do takového času vměstnám tak zhruba holou šestnáctibitovou smyčku.

Proto jsem udělal to samé, co Knuth pro jednodušší variantu hry, a vygeneroval si strom řešení, s úvahou, že by ho bylo možno v nějaké zkomprimované formě vložit do programu. Není to časově úplně nenáročné, musel jsem opustit Python, který běžně pro pomocné práce užívám, a použít C, a počítač se i tak docela nadřel. Výsledek je zde.

Analysou souboru zjistíme, že každou možnou kombinaci můžeme uhádnout přinejhorším na sedmý pokus. Vyzkoušíme si to na příkladu:

Hráč zvolí kombinaci 56277 (místo barev používáme číslice 0 až 7).

Náš první odhad (v programu by byl modifikován náhodnou permutací a přeskupením, ale od toho lze pro tuto chvíli upustit) je 00123 (řádek #0). Za to dostaneme jeden bílý kolík, tedy pokračujeme řádkem #328.

Tipujeme 14566. Hráč nám dá dva bílé kolíky, čímž nás posune na řádek #469.

Dále tipujeme 16277; povšimněme si, že tento kod nemůže být řešením, protože v prvním tipu bychom dostali dva bílé kolíky a ve druhém jeden černý a jeden bílý. Hráč nám dá čtyři černé kolíky. Jdeme proto na řádek #713.

Tipujeme 40005 a dostáváme jeden bílý kolík. Proto tipujeme 56277 a jsme v cíli, hráč nám dá pět černých kolíků.

Jako tahák to funguje báječně, ale opět narážíme na problém nevýkonného hardwaru. I když se snažím sebevíc a zvažuji všemožné způsoby komprese, včetně různých variant Huffmanova kodu, nemohu tabulku směstnat do takové velikosti, aby se vešla do 52 KiB paměti, kterou nejvýš má PMD 85 k disposici.

Budu tedy muset vymyslet něco jiného. Představitelné je např. to, že se z tabulky do programu uloží pouze několik prvních kroků a zbytek se nechá péemdéčku dopočítat, ale zde jsme opět u problému časových nároků na prohledání stavového prostoru.

Nejhorší scenář, tedy že buď tuto hru neimplementuji vůbec, nebo v jednodušší variantě čtyř posic a šesti barev, jak odpovídá původnímu Mastermindu, si zatím nepřipouštím.

Aktualisováno.
Prozatím mám Plán. Nechal jsem si spočítat, kolik kombinací zbývá v jednotlivých uzlech stromu, a vyšlo mi toto:

Z toho vyplývá, že ponechám-li ve stromové struktuře pouze ty uzly, které mají více než (například) 64 zbývajících kodů, strom bude snadno směstnatelný do paměti.

Zbývá vytvořit algorithmus, kterým si PMD zbývající kody zjistí a nalezne vhodný další pokus.

První část je netriviální, protože si nemohu dovolit procházet všech 32768 možností a zkoumat, zda kod odpovídá všem dosavadním výsledkům. Napadlo mne, že bych mohl vzít dva první výsledky a rozdělit podle nich kody do osmi různých skupin, přibližně stejně početných. V paměti bych uchovával pro každý kod tříbitový údaj o skupině, což znamená (snesitelných) 12 KiB programu. Procházení by tak cca 7/8 kodů vyloučilo ihned, porovnáním čísla skupiny, a pokusy a jejich výsledky by se zkoumaly jen pro zbývající osminu případů. To by (snad) mohlo být časově únosné.

Netriviální je i druhá část, protože ani zde nemohu procházet všechny možné kombinace. Nejméně bolestnou variantou je omezit se na kody, které zbyly, a najít optimální volbu mezi nimi Knuthovým minimaxem. Nebude to tak elegantní, jako když počítač zvolí zdánlivě zcela nesmyslný kod a poté sestaví řešení, ale zatím mne nic lepšího nenapadlo, i když určitý nápad se mi v hlavě už rýsuje – uvidíme.

Komentovat články mohou pouze registrovaní uživatelé; prosím, zaregistrujte se (v pravém sloupci dole)