| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Show document

Title:Visualization of alpha-beta game tree search
Authors:Taseva, Emilija (Author)
Strnad, Damjan (Mentor) More about this mentor... New window
Kohek, Štefan (Co-mentor)
Files:.pdf UN_Taseva_Emilija_2019.pdf (1,52 MB)
 
Language:English
Work type:Bachelor thesis/paper (mb11)
Typology:2.11 - Undergraduate Thesis
Organization:FERI - Faculty of Electrical Engineering and Computer Science
Abstract:Algorithms make up a crucial part of computer science studies. Learning and understanding new algorithms can be quite interesting, but also hard and complex, especially for students. Visualization can significantly help with the understanding of the dynamic behaviour of algorithms by visually displaying each step of the algorithm, its purpose and how it changes the data. Besides faster and more efficient learning, the better understanding can also lead to potential algorithm improvements in the future. The goal of this thesis is visualization of the alpha-beta tree search algorithm for determining the next optimal move in a two-player, zero-sum, complete information game. The algorithm is visualized using two games, Tic-Tac-Toe and Othello. The algorithm operation can also be demonstrated using a custom tree with parameters chosen by the user.
Keywords:algorithm visualization, minimax algorithm, alpha-beta pruning, adversarial search
Year of publishing:2019
Source:Maribor
NUK URN:URN:SI:UM:DK:VNEKQMAJ
License:CC BY-SA 4.0
This work is available under this license: Creative Commons Attribution Share Alike 4.0 International
Views:45
Downloads:10
Metadata:XML RDF-CHPDL DC-XML DC-RDF
Categories:KTFMB - FERI
:
  
Average score:(0 votes)
Your score:Voting is allowed only for logged in users.
Share:AddThis
AddThis uses cookies that require your consent. Edit consent...

Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Secondary language

Language:Slovenian
Title:Vizualizacija alfa-beta preiskovanja drevesa igre
Abstract:Algoritmi predstavljajo ključni del študija računalništva. Učenje in razumevanje novih algoritmov je lahko zelo zanimivo, ampak tudi naporno in zapleteno, zlasti za študente. Vizualizacija lahko bistveno pripomore k razumevanju dinamičnega delovanja algoritma tako, da grafično prikaže vsak njegov korak, namen in način spreminjanja podatkov, kar lahko v prihodnosti pripomore k potencialnim izboljšavam algoritma. Cilj diplomske naloge je vizualizacija alfa-beta preiskovanja drevesa igre, s katerim določimo naslednjo optimalno potezo v igri z dvema igralcema, ničelno vsoto in popolno informacijo. Alfa-beta algoritem je optimizacija algoritma minimax, ki išče najboljšo rešitev skozi drevo igre, tako da odreže veje, ko je že našel boljši korak. To znatno skrajša čas računanja in omogoča, da veliko hitreje iščemo po drevesu iger. Upoštevati je treba tudi, da je stopnja izboljšanja, ki jo doseže algoritem alfa-beta, močno odvisna od vrstnega reda raziskovanja vozlišč. Prej ko se odkrije boljše stanje, prej lahko druge veje s slabšim stanjem zavržemo. Pri vizualizaciji algoritma iskanja dreves, zlasti za bolj zapletene igre, je treba določiti nekatere omejitve. V večini primerov ni mogoče poiskati celotnega drevesa, saj bi dobili obsežno drevo z ogromnim vejitvenim faktorjem in globino, ki ga ni mogoče pregledati v smiselnem času. Zaradi tega bi morali določiti nekatere omejitve, kot je omejitvi globina iskanja. Za vizualizacijo postopka odločanja algoritmov in predstavitev prednosti alfa-beta obrezovanja smo izdelali spletno aplikacijo z uporabo JavaScript in D3.js knjižnice za ustvarjanje močnih in interaktivnih vizualizacij v brskalniku. Vizualizacija delovanja algoritmov minimax in alfa-beta je izvedena na primeru dveh iger, križci-krožci in Othello. Delovanje algoritma je možno ponazoriti tudi na po meri ustvarjenem drevesu, katerega parametre izbere uporabnik. Spletna aplikacija tako služi kot uporabno učno orodje. Za postopek vizualizacije smo implementirali splošen programski vmesnik, ki ga je mogoče uporabiti za katero koli igro z dvema igralcema, ničelno vsoto in popolno informacijo. Uporabi se lahko tudi za kateri koli drug algoritem preiskovanja drevesa igre. Čeprav je vmesnik za vizualizacijski program uporaben za druge algoritme, je še vedno zelo odvisen od domene. Z nadaljnjimi izboljšavami se lahko njegove funkcionalnosti razširijo, da bi lahko ponudili še bolj specifične rezultate.
Keywords:vizualizacija algoritmov, algoritem minimax, alpha-beta rezanje, konfliktno iskanje


Comments

Leave comment

You have to log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica