Računalni agent za igranje igre na ploči

diplomski rad

• Naslov (engleski): Computer Agent for Board Game Playing
• Autor: Marino Voćanec
• Mentor: Tomislav Hrkać (mentor)
• Član povjerenstva: Tomislav Hrkać (predsjednik povjerenstva)
• Član povjerenstva: Zoran Kalafatić (član povjerenstva)
• Član povjerenstva: Jan Šnajder (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Fakultet elektrotehnike i računarstva; Zagreb
• Datum i država obrane: 2021-07-02, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U ovom radu proučeni su različiti pristupi oblikovanja računalnog agenta za automatsko igranje odabrane igre na ploči. Opisan je postupak efikasne implementacije igre kao i razvoj grafičkog korisničkog sučelja za evaluaciju agenta u igri protiv ljudskih igrača. Implementirani su algoritmi iz dvije različite familije: tradicionalni algoritmi koji se temelje na klasičnom minimaks pretraživanju stabla te noviji koji koriste Monte Carlo simulacije i duboko učenje. Razvijeni agenti su iterativno poboljšavani raznim optimizacijskim postupcima sve dok nije postignuta željena razina kvalitete igre. Posebno su naglašene mogućnosti, ograničenja i problemi pojedinih algoritama. Na koncu, nakon evaluacije svih razmotrenih algoritama, odabran je najbolji te je predložena njegova konačna natjecateljska implementacija.

Sažetak (engleski)

This paper considers different approaches of designing computer agents for automatic board game playing. It describes the process of efficient game engine implementation as well as graphical user interface for evaluating agent game play against human players. Algorithms from two different families were implemented: traditional algorithms which are based on classical minimax tree search and new ones which utilize Monte Carlo simulations and deep learning. Developed agents had been iteratively enhanced with various optimization techniques until satisfactory quality of game play was reached. Special focus was put on possibilities, limitations and problems of chosen algorithms. At last, after evaluation of all considered algorithms, the best one was chosen and its final competitive implementation was suggested.

• Ključne riječi: igra na ploči; agent; stablo igre; minimaks; alfa-beta; negamaks; transpozicijska tablica; MTD(f); genetski algoritam; Monte Carlo; MCTS; duboko učenje; konvolucijska neuronska mreža; rezidualni blok; predtreniranje; binarna ploča
• Ključne riječi (engleski): board game; agent; game tree; minimax; alfa-beta; negamax; transposition table; MTD(f); genetic algorithm; Monte Carlo; MCTS; deep learning; convolutional neural network; residual block; pre-training; bitboard
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:946857
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra inženjer/inženjerka računarstva (mag.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2023-01-13 14:11:56