Cílem je vytlačit šest soupeřových kuliček ze šachovnice. Protihráči střídavě přemisťují své kuličky podle následujících pravidel:
Kuličkou lze tlačit až dvě vlastní kuličky, které spolu bezprostředně sousedí v daném směru (tj. posun trojice v řadě):
.. []> []> []> .. .. .. [] [] [] .. .. .. .. .. .. .. .. .. .. .. .. .. Ukázka možných .. .. .. .. .. .. .. [] .. tahů v řadě .. .. .. .. .. .. []/ .. .. .. .. [] .. .. .. ../ .. .. .. [] .. .. .. .. .. .. .. .. .. .. .. ..
Vlastními kuličkami lze přetlačit i kuličky soupeřovy, pokud počet vlastních kuliček převyšuje počet soupeřových kuliček a za soupeřovými kuličkami je již volné místo. Nejvýše lze takto tlačit trojicí kuliček dvojici soupeřových kuliček, čtveřicí kuliček již tlačit nelze.
.. []> []> []> XX .. .. [] [] [] .. .. .. .. .. .. .. .. .. .. .. .. .. Ukázka možných .. .. .. .. .. .. .. [] .. tahů v řadě .. .. .. .. .. .. []/ .. .. .. .. [] .. .. .. XX/ .. .. .. [] .. .. .. ../ .. .. .. .. XX .. .. ..V ukázce byla jedna soupeřova kulička vytlačena mimo šachovnici, touto cestou se tedy naplňuje cíl hry.
Nelze tlačit, pokud za kuličkami soupeře následuje moje vlastní kulička nebo pokud kuličky nejsou v jedné řadě.
[]> []> XX> []> .. .. [] [] XX [] .. .. .. .. .. .. .. .. .. .. .. .. .. Ukázka .. .. .. .. .. .. .. [] .. zakázaných .. .. .. .. .. XX <[] .. .. tahů XX [] [] .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
.. [] [] [] .. .. .. .. .. .. ../ ../ ../ .. [] [] [] .. .. .. .. .. .. Ukázka možných .. .. .. .. .. .. .. []> .. tahů šikmo .. .. .. [] .. .. []> .. .. .. .. .. [] .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
V tazích šikmo není možné tlačit žádné kuličky a řádka vlastních kuliček nesmí být přerušená, kuličky spolu musejí bezprostředně sousedit.
.. [] [] [] .. .. .. [] .. .. ../ [] ../ .. [] [] [] .. .. .. .. .. .. Ukázka .. .. .. .. .. .. XX <[] .. zakázaných XX [] .. .. .. .. <[] .. .. tahů .. [] .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. .. ..
Vyhrává ten, který jako první vytlačí šestou soupeřovu kuličku ze šachovnice.
V programu je z pravidel vyřazen šikmý tah.
Uživatel hraje s kuličkami, které se na začátku hry objeví ve spodní části šachovnice, uživatel hru zahajuje.
Pro pohyb po šachovnici jsou určeny tyto klávesy:
Uvedené klávesy lze použít i pro zadání směru tahu (viz níže), pro pohyb kurzoru po šachonici lze navíc používat šipek a kláves 8 a 2, které kurzor přesouvají o dvě řádky nahoru a dolů.
- 7, U
- posun doleva nahoru
- 9, I
- posun doprava nahoru
- 6, K
- posun doprava
- 3, M
- posun doprava dolů
- 1, N
- posun doleva dolů
- 4, H
- posun doleva
Přímý tah se zadá takto:
- Kurzorem najeďte na kuličku, která bude realizovat tah. (V našich ukázkách výše je vyznačena červenou barvou.)
- Stiskněte return nebo enter, abyste vstoupili do režimu zadávání směru tahu.
- Stiskněte klávesu udávající směr posunu kuličky. Chcete-li táhnout jinou kuličkou, stiskněte esc a vraťte se k bodu 1.
- Pokud to bude možné, počítač sám provede jakákoli povolená přetlačování kuliček v daném směru. Pokud to možné nebude (chcete tlačit moc kuliček, vytlačit vlastní kuličku ze šachovnice ap.), tah se neuskuteční a budete vráceni do režimu volby kuličky, tj. pokračujete od bodu 1.
Po zadání platného tahu se kuličky přesunou, změní se indikátor aktivní strany v levém horním rohu obrazovky a po chvilce přemýšlení táhne i počítač. Pak je opět na tahu člověk.
Hra pokračuje tak dlouho, dokud jedna ze stran nevytlačí šest soupeřových kuliček ze šachovnice. Jakmile k tomu dojde, program se ukončí vyhlášením vítěze a výpisem dalších statistik. Předčasně lze program ukončit stiskem klávesy q, pokud právě neprobíhá výběr tahu počítače.
Program Abalone je kompilován ze tří zdrojových kódů:
abalone.pas
- je hlavní program, kromě těla celého programu obsahuje též definici a deklarace procedur spojených s tvorbou a analýzou herního stromu.
plocha.pas
- je knihovna s objektem
sachovnice
sloužícím k reprezentaci stavu šachovnice. Součástí knihovny jsou i obslužné metody a procedury sloužící k inicializaci šachovnice, kopírování šachovnice (vytvoření nového objektu s obsahem existujícího objektu), provádění tahů na šachovnici a zadávání tahu uživatelem.fronta.pas
- je pomocná knihovna obsahující implementaci fronty pomocí objektů. Frontu pak využívá hlavní program při výpočtu herního stromu ve vlně.
V dalším se budeme věnovat především hlavnímu programu a metodám tvorby a analýzy herního stromu.
Celý herní strom sestavený z objektů typu
hra
je uložen v globální proměnnémozek
(a samozřejmě dalších dynamicky odkazovaných objektech). Každý uzel stromu pak může obsahovat odkaz na vlastní šachovnici (objekt typusachovnice
), pokud uzel nemá vlastní šachovnici, může poprosit svého otce o poskytnutí šachovnice a na ni pak uplatní svůj tah. Kořen celého stromu,mozek
, obsahuje odkaz na hlavní šachovnici hry, která je též vykreslována na obrazovku. Další odkaz na tentýž objekt je pak i v globální proměnnés
. Šachovnice celého mozku tedy nesmí být nikdy smazána.
Ohodnocovací funkce hry Abalone je statická, tj. hodnotí stav šachovnice a nikoli její změny. Je proto umístěna přímo do metodyvaha
objektusachovnice
.Základem ohodnocení je počet vytlačených kuliček, pokud hráč vytlačí
i
soupeřových kuliček, získává100*i*i
bodů.Dalším faktorem pro ohodnocení je "koagulovanost" kuliček. Pro každou kuličku se prohlédne její nejbližší okolí (tj. šest sousedních míst) a je-li na sousední pozici kulička stejné barvy, získává hráč jeden bod, sousedí-li naopak kulička s okrajem šachovnice, strácí hráč jeden bod.
Samostatně jsou též hodnoceny "rizikové situace". Hráč ztrácí 50 bodů, pokud se jeho kulička nachází u kraje šachovnice a protihráč má v příslušném směru dostatek kuliček na to, aby mohl naši kuličku v příštím tahu vytlačit ze šachovnice.
Abalone využívá času, kdy přemýšlí uživatel, k tomu, aby konstruoval strom ve vlně do několika dalších pater. Omezující je zde volná paměť a čas, po který uživatel přemýšlí.V hlavním cyklu, kdy program čeká na podněty z klávesnice, je periodicky volána procedura
ohodnocuj
, která vezme další prvek z fronty (v globální proměnnéohodnot
) - nějaký uzel rostoucího stromu - a zavolá jeho metodumysli
."Myšlení" uzlu spočívá v pokusu vyrobit svého dalšího syna ze stávající šachovnice a ohodnotit jej. Pokud uzel nevyrobil posledního syna, přidá se znovu do fronty a v dalším cyklu bude stejně pokračovat. Jsou-li již všichni synové vyrobeni a jejich šachovnice ohodnoceny, uzel zavolá vlastní metodu
reeval
, která najde nejlepšího syna, správně nastaví své ohodnocení (proměnnouvaha
), zvýší indikátor hloubky propočtení stromu a o totéž rekurzivně poprosí otce. Tímto způsobem si tedy celý strom udržuje informace o své hloubce a o nejlepších tazích. Po probublání informace o zvětšené hloubce až ke kořeni stromu se uzel pokusí přidat do fronty nikoli sám sebe, ale své syny, aby začaly vyrábět nové patro stromu v dalších krocích. Uzel nepřidá své syny do fronty, pokud nemá právo generovat strom do větší hloubky - toto právo uděluje nenulová proměnnádohloubky
, v níž je pro každý uzel uloženo, jak hluboko může tvořit syny. O správu proměnnédohloubky
ve všech uzlech mozku se stará hlavní program - jakmile má mozek hloubku rovnou povolené hloubce (tj. celý se úspěšně propočetl do povolené hloubky a nedošla přitom např. paměť), zvýší hlavní program v celém stromu povolení do hloubky o jednu vrstvu. Je-li fronta prázdná, vybuduje se sama po vložení mozku, po několika iteracích již ve frontě budou odkazy na listy. Listy si "všimnou", že mohou generovat strom do větší hloubky a běžný cyklus se začne opakovat.Vedlejším efektem tohoto předvýpočtu na pozadí je pro uživatele možnost nechat mozek myslet za sebe. Jakmile se zvýší hloubka mozku, problikne na šachovnici současný nejlešpí známý tah. Je zřejmé, že se toto doporučení může s výpočtem dalších vrstev ještě měnit, je však přesto pro uživatele často dobrým tipem. Uživatel může nápovědu ovládat pomocí dvou kláves:
+ - na šachovnici problikne stávající nejlepší známý tah
* - stávající nejlepší známý tah je za uživatele proveden, tak jako kdyby jej uživatel opravdu táhl
Ořezávání málo nadějných uzlů během výpočtu ve vlně představuje určitou heuristiku v programu. Ořezávání vlny má dvě podoby a pomocí konstant v úvodu programu je možné jej vyladit na míru nejmenší škodlivosti.Jen n nejlepších synů
KonstantaSIRKAMYSLENI
dovoluje omezit počet nejlepších synů, kteří budou během výpočtu ve vlně uchování. Program samozřejmě postupně generuje všechny syny, po každém přidání a ohodnocení nového syna však prohlédne stávající syny a překročí-li jejich počet konstantu, toho nejhoršího z řetízku odstraní. Další rozvíjení stromu ve směru "špatných uzlů" tedy není možné.Ukazuje se, že je to ten nejnebezpečnější způsob heuristiky. Počítač často zahazuje i útočné tahy, protože se tím jeho kuličky dostanou na méně bezpečná políčka u kraje šachovnice a paradoxně může hodoncení takové šachovnice vypadat nevýhodně.
Prořezávání ve zpětné vlně
Další možnost ořezávání je implementováno v metoděreeval
, tedy ve chvíli, kdy uzel dostává zprávu o propočtení stromu pod ním do větší hloubky. KonstantaHLOUBKAREZUVLNY
ještě omezuje tento algoritmus zdola - pokud není strom pod uzlem propočten do této minimální hloubky, ořezávání se vůbec nespustí.Prořezávání se uskutečňuje již ve chvíli, kdy je znám nejlepší možný následník stávajícího uzlu (odkaz na něj je v proměnné
bestson
), a jeho úkolem je odstranit syny, kteří jsou ve svém hodnocení o horší než nejlepší syn o více než konstantaPRAHREZUVLNY
.
Procedura
mozektahne
realizuje tah počítače. Nejprve ověří, zda již náhodou není strom propočten do hloubky větší než jeHLOUBKAMYSLENI
, a podle potřeby spustí rekurzivní metodu stromudeepthought
a omezením rekurze naHLOUBKUMYSLENI
. Tato metoda jednak prohlíží stávající uzly stromu a nechává je prohledat do příslušné hloubky (zde jsou tedy mnohdy uzly předpočtené a předvýpočet vlnou šetří počítači čas), a rovněž zkouší generovat uzly další. Pro syny je opět vyvolána metodadeepthought
, omezení do hloubky je tentokrát sníženo.Pokud během výpočtu do hloubky dojde k nějaké chybě (nedostatek paměti pro vytvoření syna), ohodnotí se přímo šachovnice uzlu (a nikoli až jeho synů ve vytyčené hloubce) a do hierarchicky vyšší instance volání procedury
deepthought
se vrátí snížená hranice hloubky. Všechny další větve stromu se tedy od té chvíle propočítávají do menší hloubky, než bylo původně stanoveno.V metodě je užito alfa-beta redukce, k níž například dojde v případě, že uzel, který vybírá ze svých synů minimum najde hned prvního syna s tak malým ohodnocením, že by jej otec stávajícího uzlu již nemohl vybrat (volí maximum), neboť zná syna lepšího. Každý uzel dostává od svého otce v parametrech požadavky na minimální a maximální hodnotu přijatelného syna a pokud se vytvořený syn do tohoto intervalu nevejde a uzel se má snažit hledat syna ještě menšího nebo ještě většího, uzel se o generování dalších synů nepokouší.
Na rozdíl od přechodu od vlny k prohledávání do hloubky, kdy je strom uchován v paměti, je strom během hloubkového prohledávání postupně zahazován a po ukončení prohledávání ve stromu zbydou jen synové první úrovně.
Hloubka rekurze určená hodnotou proměnné
HLOUBKAMYSLENI
se v průběhu hry mění. Na počátku je dána hodnotou konstantyVYCHOZIHLOUBKAMYSLENI
a po každém tahu počítače se zvýší, pokud počítač stihl strom prohledat v čase menším než jeDOBAMYSLENI
. Pokud prohledávání naopak překročilo dobuMAXDOBAMYSLENI
, pro příště se povolená hloubka sníží. Může se poměrně snadno stát, že nižší hloubka je propočtena vždy ve velmi krátkém čase a větší hloubka naopak vždy překročí maximální povolenou dobu, počítač pak střídavě přemýšlí do hloubky větší a menší.
Po úvodní inicializaci programu Abalone, během níž je vytvořen kořen herního stromu, hlavní šachovnice a založena prázdná fronta pro prohledávání ve vlně, vstupuje program do hlavního cyklu. Periodicky kontroluje a zpracovává události na klávesnici funkcí
walkandwait
a volá proceduruohodnocuj
, která realizuje jeden krok výpočtu ve vlně.Zpracování podnětů z klávesnice provádí rovněž funkce
walkandwait
, stará se o posun kurzoru po šachovnici i o reakci na stisk klávesy return, tj. příjem tahu uživatele a následně spuštění výběru tahu počítače (tyto kroky jsou sdruženy do proceduryclovektahne
).Funkce
walkandwait
vracítrue
, pokud program nemá dosud končit. Tato návratová hodnota pro hlavní cyklus tedy představuje výzvu k výpočtu na pozadí.False
znamená pokyn k vypsání statistik o hře a ukončení programu. K tomu může dojít buď prohrou jednoho z hráčů (součástí závěrečných statistik je pak vyhlášení vítěze) nebo na požadavek uživatele o předčasné ukončení programu.
- Zdrojový text:
- Je určen pro Borland Pascal verze něco kolem 7.
- K dispozici v tomto balíku.
- Zkompilovaný spustitelný soubor:
- K dispozici zde.
26.5.1998