| Abstrakt: | Hlavným cieľom tejto bakalárskej práce bolo preskúmať a analyzovať aplikáciu algoritmu Monte Carlo Tree Search (MCTS) na novú kartovú hru. Najprv sme uviedli komplexné definície kartových hier vo všeobecnosti a potom sme sa zamerali konkrétne na hru Faraón. Táto hra má zvyčajne malý počet dostupných ťahov, ale je ťažké heuristicky vyhodnotiť aktuálny stav (na rozdiel napr. od šachu). Hru Faraón sme potom implementovali spolu s algoritmom MCTS vrátane dvoch zaujímavých variantov odporúčaných existujúcim výskumom. Starostlivými manuálnymi úpravami sme doladili parametre algoritmu MCTS.
Na vyhodnotenie vplyvu našich úprav sme uskutočnili rozsiahly turnaj s použitím rôznych variantov MCTS a alternatívnych algoritmov. Výsledky sme zaznamenali a analyzovali s cieľom posúdiť výkonnosť týchto algoritmov. Zaznamenali sme výrazné zlepšenie výkonu pri rovnakom výpočtovom rozpočte, ale zároveň zavedenie Beam Search ako jedného z vylepšení neočakávane viedlo k poklesu výkonu.
Okrem toho bolo kľúčovým aspektom našej práce skúmanie evolučných zákonitostí stromovej štruktúry vytvorenej algoritmom MCTS. Zistilo sa, že strom vykazuje pozoruhodnú vyváženosť, čo naznačuje, že v hre Faraón neexistujú žiadne super výhodné ťahy. Zavedenie heuristiky orezávania ťahov, druhého z dvoch zlepšujúcich variantov, však spôsobilo jav, ktorý sme nazvali neočakávaná prehra, hoci celkový výkon sa zlepšil.
Naše výsledky naznačujú, že algoritmus MCTS má pozoruhodný potenciál na riešenie úloh hier, ako je napríklad hra Faraón, pričom neustále prekonáva ostatné algoritmy. Tento výskum poskytuje cenné poznatky o použití MCTS v kontexte hry Faraón a ponúka zaujímavé vyhliadky na budúci pokrok v tejto oblasti.
|
|---|