V priebehu posledných rokov sa ústrednou oblasťou výskumu a rozvoja informatiky stala už dnes takmer všadeprítomná umelá inteligencia, v použití ktorej spočíva úspech mnohých inovatívnych riešení. Často sú tieto projekty uskutočniteľné vďaka poznatkom nadobudnutým najmä v snahe zvýšiť autonómnosť umelej inteligencie pri rozhodovaní sa na základe logického úsudku. Práve toto úsilie súvisí s tvorbou rozličných agentov, ktorých úlohou je osvojiť si pravidlá vopred stanovanej hry a následne úspešne konfrontovať získané zručnosti s ľudským protihráčom. Kladnou stránkou spomenutej formy výskumu je aj skutočnosť, že na jej realizáciu je celkom postačujúci prístup k počítaču, a preto sme sa i my vydali cestou síce skôr aplikovaného, no rovnako zaujímavého bádania, kam až moderné informačno-komunikačné zariadenia dokážu zájsť.
Naším cieľom bolo konkrétne vyvinúť aplikáciu, ktorá by predstavovala nielen štandardnú implementáciu stolovej hry dáma umožňujúcej porovnať si svoje strategické zmýšľanie dvom reálnym protihráčom, ale ktorej súčasťou by bol aj program schopný do určitej miery vzdorovať človeku, ba dokonca poraziť začiatočníka. V tejto práci sa teda najprv budeme zaoberať návrhom riešenia daného problému, kedy podrobnejšie uvedieme a zdôvodníme zvolené postupy, potom určíme časový plán, v ktorom rozvrhneme implementáciu do niekoľkých fáz, a na záver zhodnotíme dosiahnuté výsledky. Jednou z príloh tohto dokumentu bude okrem samotnej spustiteľnej aplikácie i návod na jej obsluhu v podobe používateľskej príručky.
Špecifikácia a návrh
Celú aplikáciu sme sa aj s ohľadom na naše skúsenosti rozhodli vytvoriť v programovacom jazyku Python, ktorého výhodou je jednoduchá syntax a nemalý počet k nemu poskytovaných knižníc. Ďalej budeme túto kapitolu členiť na tri časti zodpovedajúce jednotlivým logickým celkom, z ktorých sa bude skladať vývoj konečného softvéru.
Riadenie priebehu hry
Zabezpečenie korektného riadenia priebehu hry je v procese návrhu tohto projektu azda jeho najdôležitejším komponentom, pretože od neho sa bude odvíjať aj následné prevedenie do používateľsky prívetivého prostredia. Po zvážení viacerých alternatív sme si na reprezentáciu hracej dosky zvolili dvojrozmerné pole, ktorého prvkami sú objekty obsahujúce informácie o obsadenosti, hodnote a susediacich políčkach. Využijeme teda kombináciu štandardného poľa a spájaných štruktúr, čoho dôvodom je aj väčší počet dát pre každé políčko spätý s vedomím, že tie budú neskôr potrebné pri realizácií agenta. Toto riešenie nám napokon uľahčí i spôsob, akým budeme prehľadávať celú plochu, čo bude nevyhnutné pri kontrole správnosti vykonaného ťahu, keďže jedno z pravidiel tejto hry dáva hráčovi za povinnosť urobiť krok, ktorým vie preskočiť najväčší počet nepriateľských figúrok. Prihliadajúc na náš konečný cieľ, budeme všetky, čiže aj potenciálne nevhodné, možnosti na začiatku každého ťahu vypočítavať a ponúkať používateľovi, pričom korekcia bude podľa zaužívanej zásady ponechaná na protihráča. Pomocou backtracking-u teda prehľadáme hraciu dosku, zapamätáme si optimálne cesty pre prípad opravy súperom a nakoniec všetky uložíme vo forme stromu za účelom zvýšenia efektivity sprístupňovania políčok hráčovi. Spojením týchto záverov dospievame k výslednej štruktúre priebehu celej hry, ktorá je znázornená na obr. 1.
Obr. 1: Priebeh hry
Používateľské rozhranie
Základnou požiadavkou pri prezentácii funkcionalít softvéru zväčša býva prehľadnosť, a preto sa aj my budeme snažiť docieliť intuitívnosť navigácie v aplikácii. V dôsledku pretrvávajúceho trendu internacionalizácie bude používateľ inštruovaný naprieč celým programom v anglickom jazyku. Na úvodnej obrazovke sa bude nachádzať menu so štyrmi možnosťami: Play, Settings, Ranking, Rules. Kliknutie na tlačidlo Play nás privedie ku konfigurácii špecifikujúcej nastavenia konkrétnej hry, ako napríklad mód (dvaja skutočný hráči alebo hráč proti počítaču), úroveň obťažnosti v prípade konfrontácie s počítačom, mená hráčov a ďalšie. Ponúknutá bude tiež možnosť načítať už rozohranú partiu a takisto zvoliť súbor, do ktorého sa má hra zaznamenávať. Následne uvedieme používateľa do herného režimu, ktorého správanie si bude vedieť sčasti prispôsobiť po prechode do sekcie Settings z menu na úvodnej obrazovke. V nej sa bude dať určiť spôsob posúvania figúrkami (klikaním, ťahaním, oboma), zapnúť pomoc v podobe zvýraznenia možností, zmeniť základnú veľkosť hracej dosky a začiatočného počtu figúrok, ovplyvniť rôzne grafické prvky a poskytnúť textový alebo CSV súbor s rebríčkom doterajších výsledkov, ktorý má program modifikovať. Prezeranie a zoraďovanie výsledkov v rebríčku podľa zvoleného kritéria používateľovi sprostredkuje tlačidlo Ranking v hlavnom menu. Kliknutím na Rules sa dostaneme k stručnému popisu pravidiel, ktoré uplatníme pri riadení priebehu samotnej hry.
Agent s inteligenciou protihráča
Keďže jednou z našich úloh bolo vyvinúť agenta, ktorého schopnosti by boli porovnateľné so zručnosťami začiatočníka, no zároveň sme nechceli pristúpiť k využitiu neurónových sietí vyžadujúcich komplexné vedomosti v tejto oblasti a značnú výpočtovú silu, rozhodli sme sa implementovať algoritmus minimax dosahujúci pozoruhodné výsledky. Podstata jeho fungovania je založená na prehľadávaní možných scenárov po vykonaní vopred stanoveného počtu krokov, v našom prípade tri, kedy sa stav hry vyhodnotí a podľa tohto meradla sa napokon určí spomedzi všetkých ten najvýhodnejší. Meno algoritmu je odvodené od spôsobu, akým sa tieto optimálne kroky vyberajú. V prechádzanom strome udalostí totiž každá úroveň predstavuje akcie jedného z dvoch hráčov pravidelne sa striedajúcich počas hry, a preto vieme heuristiku posudzujúcu stav vytvoriť tak, že napríklad čierny bude chcieť jej výstup maximalizovať a biely minimalizovať, pričom ak takéto rozhodovanie zopakujeme postupne od najnižšej úrovne, ktorá je spomínanou hranicou v budúcnosti, až po najvyššiu, tak výsledkom bude najlepší možný krok za predpokladu, že súper bude tiež v najbližšom čase hrať ideálne. Aby sme však nemuseli prehľadať celý strom, aplikujeme aj princíp zvaný alpha-beta pruning, čím badateľne urýchlime tento proces, pretože vďaka nemu dokážeme z výpočtu vynechať tie vetvy, ktoré kvôli už známym alternatívam nebudú v porovnaní s aktuálnym optimom výhodnejšie. Z uvedeného vyplýva, že bude nesmierne dôležité sústrediť sa na návrh ohodnocujúcej funkcie, berúc do úvahy teóriu nami zvolenej hry. Po dlhšom rozbore sme dospeli k záveru, že naša heuristika bude skúmať rozloženie figúrok z dvoch hľadísk, absolútneho (obr. 2) a relatívneho (čím menší rozptyl, tým lepšie).
Obr. 2: Rozvrstvenie hodnoty pozície pešiaka pri veľkosti hracej plochy 10x10 z pohľadu hráča začínajúceho hore
- biela farba predstavuje hodnotu 0, čierna približne 60% hodnoty kráľa
Časový plán
Október 2020
Implementácia základných prvkov hry
Program je schopný riadiť priebeh hry zatiaľ bez možnosti korekcie. Interaktivita je zabezpečená v textovej podobe a prebieha za pomoci terminálu.
Tvorba jednoduchého agenta
Algoritmus minimax s použitím alpha-beta pruning-u bol implementovaný a heuristika agenta je pripravená na vyššie popísanú optimalizáciu.
November 2020
Dizajn hracej dosky v tkinter
Doterajšia funkcionalita bola obohatená o schopnosť vizuálnej reprezentácie prostredníctvom základných elementov knižnice tkinter.
Boli pridané všetky spomenuté obrazovky okrem tej, ktorá bola určená na prezeranie rebríčka.
Export hry do textovej podoby a zápis do súboru s rebríčkom
Program umožňuje zaznamenávať hru v reálnom čase do textového súboru a po jej skončení výsledok zapísať do príslušného súboru s rebríčkom.
Dizajn vlastných figúrok a tvorba animácií
K vizuálu vyvinutého s pomocou štandardných prvkov knižnice tkinter pribudli vlastné figúrky a originálne animácie.
December 2020
Pridanie možnosti korekcie protihráčom
Požívateľ môže opraviť práve vykonaný ťah protihráča tak, že sám poskytne krok, ktorý mal byť spravený podľa platných pravidiel.
Prezeranie rebríčka
Obrazovka na prezeranie rebríčka bola vytvorená.
Optimalizácia pomocou modulu threading
Počas výpočtu najvhodnejšieho ťahu počítačom nebolo možné interagovať s programom, a tak sme túto záťaž preniesli na druhé vlákno.
Január 2021
Vylepšenie heuristiky
Agent je schopný voliť kroky na základe ohodnotenia vyplývajúceho z rozmiestnenia figúrok.
Výsledky práce a zhodnotenie
Úlohou tohto projektu bolo vytvoriť plnohodnotnú aplikáciu umožňujúcu používateľovi zahrať sa tradičnú hru dáma nielen so skutočným súperom, ale aj proti počítaču. Všetky ciele stanovené pri návrhu riešenia sa nám podarilo zrealizovať, pričom v mnohých prípadoch výsledky dokonca prevyšujú požadované nároky. Zaujímavou a určite prínosnou optimalizáciou bolo využitie modulu threading, ktoré síce proces rozhodovania agenta v konečnom dôsledku neurýchlilo, no dovoľuje to používateľovi interagovať s programom i počas tejto fázy. Schopnosti implementovanej umelej inteligencie sme dokázali dostať na očakávanú úroveň, a to aj napriek tomu, že pri konfigurácii nastavení hry sme ponechali k dispozícii iba najľahšiu obťažnosť. Zvyšné dve voľby sa napokon stali perspektívou ďalšej práce na tomto projekte potenciálne zahŕňajúcej štúdium neurónových sietí.
