20.500.12556/RUL-94550 Primerjava in optimizacija preiskovalnih algoritmov na primeru abstraktne igre Yinsh 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. umetna inteligenca preiskovalni algoritmi projekt Gipf Yinsh Minimax artificial intelligence search algorithms project Gipf Yinsh Minimax true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2017-09-04 12:55:07 2017-09-04 12:55:12 2022-08-10 01:48:48 0000-00-00 00:00:00 2017 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 19343 Belej_Neza_-_Primerjava_in_optimizacija_preiskovalnih_algoritmov_na_primeru_abstraktne_igre_Yins.pdf Belej_Neza_-_Primerjava_in_optimizacija_preiskovalnih_algoritmov_na_primeru_abstraktne_igre_Yins.pdf 1 3935EAAB907E8682E277E817BACB4D58 849e7aca512661b06e4bf3f1284555e0d49cf0f31e99b67c0359c0a4087948b9 8d43b2f2-a1b3-11eb-a523-00155dcfd717 20.500.12556/rul/9a718c65-8def-4221-a499-7a46708c8ada https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=102834 Fakulteta za računalništvo in informatiko 0 0 0