izpis_h1_title_alt

Primerjava in optimizacija preiskovalnih algoritmov na primeru abstraktne igre Yinsh
Belej, Neža (Avtor), Oblak, Polona (Mentor) Več o mentorju... Povezava se odpre v novem oknu

.pdfPDF - Predstavitvena datoteka, prenos (1,20 MB)

Izvleček
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.

Jezik:Slovenski jezik
Ključne besede:umetna inteligenca, preiskovalni algoritmi, projekt Gipf, Yinsh, Minimax
Vrsta gradiva:Magistrsko delo/naloga (mb22)
Organizacija:FRI - Fakulteta za računalništvo in informatiko
Leto izida:2017
Število ogledov:352
Število prenosov:408
Metapodatki:XML RDF-CHPDL DC-XML DC-RDF
 
Skupna ocena:(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
:
Objavi na:AddThis
AddThis uporablja piškotke, za katere potrebujemo vaše privoljenje.
Uredi privoljenje...

Sekundarni jezik

Jezik:Angleški jezik
Naslov:Comparison and optimisation of search algorithms exemplified by abstract game Yinsh
Izvleček:
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.

Ključne besede:artificial intelligence, search algorithms, project Gipf, Yinsh, Minimax

Podobna dela

Podobna dela v RUL:
Podobna dela v drugih slovenskih zbirkah:

Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj