Primerjava in optimizacija preiskovalnih algoritmov na primeru abstraktne igre YinshBelej, Neža (Avtor) Oblak, Polona (Mentor) umetna inteligencapreiskovalni algoritmiprojekt GipfYinshMinimaxV 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.20172017-09-04 12:55:07Magistrsko delo/naloga94550sl