izpis_h1_title_alt

Primerjava in optimizacija preiskovalnih algoritmov na primeru abstraktne igre Yinsh
ID Belej, Neža (Author), ID Oblak, Polona (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (1,20 MB)
MD5: 3935EAAB907E8682E277E817BACB4D58
PID: 20.500.12556/rul/9a718c65-8def-4221-a499-7a46708c8ada

Abstract
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.

Language:Slovenian
Keywords:umetna inteligenca, preiskovalni algoritmi, projekt Gipf, Yinsh, Minimax
Work type:Master's thesis/paper
Organization:FRI - Faculty of Computer and Information Science
Year:2017
PID:20.500.12556/RUL-94550 This link opens in a new window
Publication date in RUL:04.09.2017
Views:2567
Downloads:604
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Comparison and optimisation of search algorithms exemplified by abstract game Yinsh
Abstract:
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.

Keywords:artificial intelligence, search algorithms, project Gipf, Yinsh, Minimax

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back