Comparison and optimisation of search algorithms exemplified by abstract game Yinsh

V magistrskem delu se ukvarjamo s preiskovalnimi algoritmi, s katerimi je možno poiskati rešitve za abstraktne namizne igre. Izberemo si abstraktno igro Yinsh, ki je del znanega projekta Gipf. Cilj magistrskega dela je najti in implementirati pametnega igralca igre Yinsh, ki je zmožen premagati že obstoječe implementacije pametnih igralcev, hkrati pa je konkurenčen v igri proti izkušenemu človeškemu igralcu. Kot osnovno metodo si izberemo algoritem Minimax, za katerega sestavimo več evalvacijskih funkcij, pri čemer se te nadgrajujejo. Na tem mestu naredimo tudi analizo navzočih konstant v ocenjevalni funkciji in poiščemo optimalno kombinacijo le-teh. Osnoven Minimax zaradi velikega vejitvenega faktorja drevesa igre Yinsh ni zadovoljiva rešitev. Glede na naravo igre predlagamo več optimizacij metode Minimax, jih implementiramo, testiramo in evalviramo. Implementiramo tudi algoritem drevesnega preiskovanja Monte Carlo, katerega uspešnost primerjamo z algoritmom Minimax. Na podlagi raziskav in razvitih algoritmov sestavimo končno rešitev. Predlagamo tudi možne izboljšave in nadaljnje delo. Naša končna rešitev prinaša zelo dobre rezultate: prepričljivo premaga večino obstoječih implementacij, zmožna pa je premagati tudi zelo izkušenega človeškega igralca.In the thesis we analyse search algorithms that are able to find solutions for abstract board games. We choose the game Yinsh, one of the well known project Gipf games. The goal of the thesis is to find and implement a Yinsh-playing program that is able to defeat all the available computer programs and is strong against experienced human players. As a base method we choose Minimax, for which we implement various gradually upgrading evaluation functions. We analyse the constants in those functions and find the best combinations of them empirically. Because Yinsh has a large branching factor, basic Minimax is not an optimal solution. Based on the nature of the game Yinsh we propose multiple optimisations of the Minimax method, which we implement, test and evaluate. We also implement Monte-Carlo Tree Search method for the game Yinsh and compare its performance to the Minimax based algorithms. Based on the analysed approaches we compose the final solution. We also propose improvements and future work. Our final solution produces very good results. It defeats multiple computer programs and is also strong against experienced human players