magistrsko delo
Emilija Taseva (Author), Damjan Strnad (Mentor), Štefan Kohek (Co-mentor)

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;

Data

Language: English
Year of publishing:
Typology: 2.11 - Undergraduate Thesis
Organization: UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher: [E. Taseva]
UDC: 004.388.4(043.2)
COBISS: 22829846 Link will open in a new window
Views: 678
Downloads: 56
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: Slovenian
Secondary title: Vizualizacija alfa-beta preiskovanja drevesa igre
Secondary 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.
Secondary keywords: vizualizacija algoritmov;algoritem minimax;alpha-beta rezanje;konfliktno iskanje;magistrske naloge;
Type (COBISS): Bachelor thesis/paper
Thesis comment: Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages: VI, 36 str.
ID: 11233221