Računalni agent za igranje igre na ploči

master's thesis

• Title (english): Computer Agent for Board Game Playing
• Author: Marino Voćanec
• Mentor: Tomislav Hrkać (mentor)
• Committee member: Tomislav Hrkać (predsjednik povjerenstva)
• Committee member: Zoran Kalafatić (član povjerenstva)
• Committee member: Jan Šnajder (član povjerenstva)
• Granter: University of Zagreb; Faculty of Electrical Engineering and Computing; Zagreb
• Defense date and country: 2021-07-02, Croatia
• Scientific / art field, discipline and subdiscipline: TECHNICAL SCIENCES; Computing

Abstract

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.

Abstract (english)

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.

• Keywords: 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
• Keywords (english): 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
• Language: croatian
• URN:NBN: urn:nbn:hr:168:946857
• Study programme: Title: Computing; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra inženjer/inženjerka računarstva (magistar/magistra inženjer/inženjerka računarstva)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Closed access
• Created on: 2023-01-13 14:11:56