Abalone

(nekámen, zápočtový program pro letní semestr prvního ročníku MFF UK)

Cíl a pravidla stolní verze hry

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:
  1. V žádném tahu nelze žádnou kuličkou "přeskočit" nějaké políčko na šachovnici. Kuličky se přemisťují vždy na sousední políčko.
  2. Jsou možné dva druhy tahu:
    A. v řadě
    Hráč přesune svoji kuličku na libovolné sousední políčko (tím určuje jeden ze šesti možných směrů tahu). Je-li cílové políčko obsazeno, může dojít k "přetlačování" kuliček nebo může být tah zakázán (nelze-li přetlačovat).

    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  []  []  ..  ..
      ..  ..  ..  ..                       ..  ..  ..  ..
    ..  ..  ..  ..  ..                   ..  ..  ..  ..  ..
    
    B. šikmo
    Až trojice vlastních kuliček sousedících v jedné řadě se přesouvá šikmo, na volná políčka.
    ..  []  []  []  ..                   ..  ..  ..  ..  ..
      ../ ../ ../ ..                       []  []  []  ..
    ..  ..  ..  ..  ..   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ů       ..  []  ..  ..  ..
      ..  ..  ..  ..                       ..  ..  ..  ..
    ..  ..  ..  ..  ..                   ..  ..  ..  ..  ..
    
  3. Uskutečněný tah nelze vrátit.
Vyhrává ten, který jako první vytlačí šestou soupeřovu kuličku ze šachovnice.

Omezení a ovládání programu Abalone

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:

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
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ů.

Přímý tah se zadá takto:

  1. Kurzorem najeďte na kuličku, která bude realizovat tah. (V našich ukázkách výše je vyznačena červenou barvou.)
  2. Stiskněte return nebo enter, abyste vstoupili do režimu zadávání směru tahu.
  3. 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.
  4. 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.


Abalone pod kapotou

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 typu sachovnice), 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

Ohodnocovací funkce hry Abalone je statická, tj. hodnotí stav šachovnice a nikoli její změny. Je proto umístěna přímo do metody vaha objektu sachovnice.

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.

Předvýpočet stromu na pozadí

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 metodu mysli.

"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ěnnou vaha), 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

Návrhy ořezávání výpočtu ve vlně

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ů

Konstanta SIRKAMYSLENI 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. Konstanta HLOUBKAREZUVLNY 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ž konstanta PRAHREZUVLNY.

Prohledávání stromu do hloubky s ořezáváním

Procedura mozektahne realizuje tah počítače. Nejprve ověří, zda již náhodou není strom propočten do hloubky větší než je HLOUBKAMYSLENI, a podle potřeby spustí rekurzivní metodu stromu deepthought a omezením rekurze na HLOUBKUMYSLENI. 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 metoda deepthought, 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 konstanty VYCHOZIHLOUBKAMYSLENI a po každém tahu počítače se zvýší, pokud počítač stihl strom prohledat v čase menším než je DOBAMYSLENI. Pokud prohledávání naopak překročilo dobu MAXDOBAMYSLENI, 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ší.

Hlavní cyklus programu

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á proceduru ohodnocuj, 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 procedury clovektahne).

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 programu a spustitelný program

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.

Ondřej Bojar, obo@cuni.cz
Informace: http://www.cuni.cz/~obo/files/abalone/

26.5.1998

NAVRCHOLU.cz