Visualization of alpha-beta game tree search : magistrsko delo

Taseva, Emilija

| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

First page > Show document

Show document

Title:	Visualization of alpha-beta game tree search : magistrsko delo
Authors:	ID Taseva, Emilija (Author) ID Strnad, Damjan (Mentor) More about this mentor... ID Kohek, Štefan (Comentor)
Files:	UN_Taseva_Emilija_2019.pdf (1,52 MB) MD5: 9A01626B9DDED4EE4CD23D54F3075DA5 PID: 20.500.12556/dkum/e2560cd5-41cc-423f-8268-140ad7552d59
Language:	English
Work type:	Bachelor thesis/paper
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
Place of publishing:	Maribor
Place of performance:	Maribor
Publisher:	[E. Taseva]
Year of publishing:	2019
Number of pages:	VI, 36 str.
PID:	20.500.12556/DKUM-75186
UDC:	004.388.4(043.2)
COBISS.SI-ID:	22829846
NUK URN:	URN:SI:UM:DK:VNEKQMAJ
Publication date in DKUM:	08.11.2019
Views:	1262
Downloads:	79
Metadata:
Categories:	KTFMB - FERI
:	TASEVA, Emilija, 2019, Visualization of alpha-beta game tree search : magistrsko delo [online]. Bachelor’s thesis. Maribor : E. Taseva. [Accessed 3 April 2025]. Retrieved from: https://dk.um.si/IzpisGradiva.php?lang=eng&id=75186 Copy citation

Average score:	0.5 1 1.5 2 2.5 3 3.5 4 4.5 5 (0 votes)
Your score:	Voting is allowed only for logged in users.
Share:

Similar works from our repository:

Similar works from other repositories:

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

Licences

License:	CC BY-SA 4.0, Creative Commons Attribution-ShareAlike 4.0 International

Link:	http://creativecommons.org/licenses/by-sa/4.0/
Description:	This Creative Commons license is very similar to the regular Attribution license, but requires the release of all derivative works under this same license.
Licensing start date:	26.09.2019

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 must log in to leave a comment.

Comments (0)

0 - 0 / 0

There are no comments!

Back