Autorem blogu je 
Vývoj mého javového emulátoru PMD 85 dospěl do fase funkčního testování, tedy je na místě pustit se do vývoje softwaru. Při jeho ladění nejlépe odhalíme, co už uspokojivě funguje a kde ještě bota tlačí
.
Začít jsem se rozhodl aplikací v assembleru, a poté si naprogramovat něco složitějšího v C. Pro prvně jmenovaný jazyk jsem zvolil deskovou hru Reversi, známou též jako Othello. I když jsou její pravidla značně jednodušší než např. u šachu, nejde o hru triviální, o čemž svědčí, že se Reversi v Japonsku hraje profesionálně a pořádají se v něm mistrovství světa.
Reversi byla také první netriviální hrou, ve které počítače začaly pravidelně porážet člověka; k tomu budiž podotknuto, že u soupeření počítačových a lidských hráčů se udávají dva milníky: datum, kdy poprvé počítač porazil v regulerní partii úřadujícího mistra světa, a datum, kdy naposledy mistr světa – případně jiný hráč – porazil v regulerní partii aktuálně nejsilnější počítačový program. V mezidobí je člověk pro počítač ještě důstojným soupeřem, arci netrvá to dlouho: u šachu vyhrávají počítače nad mistry světa od r. 1997, a poslední partie, kdy ještě zvítězil člověk nad šachovým programem, slaví právě dnes desáté výročí: stalo se tak 21. listopadu 2005. Přirozeně, že v dnešní době již počítače s lidmi vážně šach nehrají: nemělo by to smysl, jestliže mezi ELO ratingem nejlepších počítačových programů a špičkových šachistů-velmistrů je už propastný rozdíl několika set bodů. Go se zatím drží, ale dlouho to nepotrvá a člověk podlehne stroji i v něm.
V případě Reversi jsou počítače silnější než člověk už od počátku 80. let, je to tedy vhodný kandidát na implementaci pomocí z dnešního pohledu mimořádně nevýkonného hardwaru, jakým je PMD 85.
Upřímně řečeno, při programování aplikace jsem si nesčetněkrát zalál a zalitoval, že jsem se do něčeho takového vůbec pustil: procesor Intel 8080A nemá ani jeden indexový registr, což činí jeho programování krajně neefektivním a komplikovaným. Když chci například přistupovat k parametrům a dynamickým proměnným uloženým na zásobníku, nemohu prostě nastavit IX/IY na SP a přímo parametry a proměnné adresovat, ale pro každý jednotlivý přístup musím nejprve uložit index do HL, pak přičíst SP a až výslednou hodnotu využít pro práci s parametrem. Registrů je zoufale málo a pro časově kritické algorithmy se jich nedostává, pročež programátor musí třikrát rozmýšlet, kam tu-kterou hodnotu uloží, aby byl výsledek pokud možno co nejrychlejší/nejméně pomalý.
Mým cílem nebylo naprogramovat Reversi tak, aby bylo z dnešního hlediska silné: to by ani nešlo, protože moderní programy pro PC vyhodnocují za sekundu desetitisíce posic, zatímco u PMD se dostanu v nejlepším případě na desítky posic za sekundu. Stačilo by mi, kdyby Reversi bylo slabé, ale nikoli vyloženě trapně slabé.
Pustil jsem se tedy do práce bez velkých ambic a očekávání.
Základem algorithmu pro nalezení protitahu ve většině deskových her je tzv. minimax, fakultativně doplněný alfa-beta prořezáváním (alpha-beta pruning), a tento algorithmus jsem implementoval i pro PMD 85.
Jeho součástí je dynamická heuristická vyhodnocovací funkce, umožňující nalézt v čase O(1) přibližné číselné ohodnocení posice. Těchto funkcí existuje pro Reversi celá řada, přičemž se liší víceméně jen složkami a použitými koeficienty; zvolil jsem bez dalšího vymýšlení hotové řešení, přičemž nevylučuji, že v další versi funkci vyměním, zejména s ohledem na to, že koeficienty by měly variovat v závislosti na fasi hry a ne zůstávat konstantní.
Důležitou otázkou je, jak representovat posici. Podobně jako u šachu se u programů na Reversi používají tzv. bitboardy. V daném případě posici representují dvě pole po 64 bitech, jedno pro černé, druhé pro bílé kameny.
Základní a časově nejnáročnější operací je nalezení všech možných tahů v dané posici, přičemž jádrem je posunutí bitboardu o jedno pole v některém z osmi směrů. Má-li procesor 64bitové registry, jako většina dnešních CPU, je tato operace – pro jednu barvu – otázkou jednoho shiftu o pevný počet bitů a následného vymaskování bitů, které ve výsledku nemají být. U i8080 a jeho 8bitových registrů je to podstatně složitější (game.s, rutina dir_pat) a časové náročnější.
I když se často využívá duální representace posic, v bitboardové a maticové formě, v mém programu matice nepoužívám, vše dělám v bitboardech.
Další otázkou bylo, zda – a jakou – databasi zahájení zvolit. Program je omezený z hlediska velikosti, proto jsem se rozhodl převzít část database používané v programu Sirius, který jsem našel ve své linuxové distribuci. V cca devíti kilobytech ukládám CRC-24 posice a následující tah pro prvních šest plies (polotahů
).
Posici na desce nejprve nechám projít sedmi rotacemi a jednou inversí, tak abych získal osm ekvivalentních symetrických posic, z nichž spočítám osm CRC a podle nich najdu tah. Ten podrobím reversní transformaci a dostanu tah, který počítač provede.
Lze namítnout, že 24 bitů je plýtvání místem, že by stačilo šestnáct bitů, ale tam bych musel řešit kolise, tedy situaci, kdy dvě různé posice mají stejné CRC (narozeninový paradox). Protože při výpočtu mám volnost 16 bitů při volbě inicialisačního vektoru (XOR-in) a 14 bitů pro výběr generačního polynomu, nevylučuji, že by se podařilo nalézt takové CRC, kde by ke kolisím nedocházelo buď vůbec, nebo tahy, které by vygenerovaly kolisní posice, by nebyly validní, ale to si nechám do příští verse: s ohledem na to, že celková délka programu je cca 17 KiB, nejsou dva kilobyty rozdílu klíčové.
Vedle samotného algorithmu jsem musel naprogramovat i uživatelské rozhraní. Samotná grafika hrací desky je strohá a kromě animace na ní není co řešit, avšak měl jsem za nutné vylepšit fonty poskytované PMD. V prvním modelu byla k disposici jen velká písmena, u PMD 85-2 přibyla malá a až u PMD 85-3 je implementována česká a slovenská diakritika, ovšem v původní matici 6-krát-8 pixelů, tedy způsobem ne právě pohledným.
Vyšel jsem ze znakového generátoru PMD 85-3, ale výšku znaků jsem zvýšil o dvě šestice a některé znaky jsem upravil, především velká písmena s diakritikou a dále např. G, u, & a @. Až budu mít víc času, předělám všechny versálky, příliš se mi nelíbí, že je např. v širší než u.
Nic dalšího nebylo třeba, řídicí logika, která části spojila dohromady, je triviální.
Docela pěkně jsem si zaprogramoval a vytvořil funkční, plně použitelný program, který s ohledem na absolutní museálnost hardwaru, pro který je určen, může být ihned po dokončení deponován v museu (případně vymazán).
Jakmile program odladím, vystavím ho jako PTP, ve všech třech jazykových versích (anglické, české a slovenské), a nabídnu laskavým čtenářům k beta-testování.
Aktualisováno.
reversi-1.0-2.ptp Anglická verse MGLD 00, česká MGLD 01, slovenská MGLD 02, startuje se ve všech případech JUMP 0000.
Komentáře
V slovenskej verzii je záverečnom texte slovo "vyhrál". Správne má byť "vyhral".
Aj keď je vypnutý zvuk, tak je po stlačení klávesu počuť pípnutie.
To jsem přehlédl; díky, opraveno.
Aj keď je vypnutý zvuk, tak je po stlačení klávesu počuť pípnutie.
To je v pořádku, tak jsem to chtěl; spíš se programu dalo vytknout, že vypíná i pípnutí při chybě, což jsem nyní opravil.
Vypnutím zvuku se míní, že se vypíná akustická signalisace tahu počítače, která je u vyšších úrovní užitečná, ale u nižších může rušit.
Možná by se mohl dát odkaz na oldcomp.cz, aby i ti co nesledují vaše stránky mohli otestovat reversi....
Všechny tři emulátory jsou ve fasi alfaverse, zápasím hlavně s věcmi, které nejsou v Javě dobře udělané (zvuk, přepínání focusu apod.).
RSS kanál komentářů k tomuto článku