Razvoj računalnog igrača za igru Dama

završni rad

• Naslov (engleski): Development of Computer Player for Checkers Game
• Autor: Antun Magdić
• Mentor: Marko Čupić (mentor)
• Član povjerenstva: Marko Čupić (predsjednik povjerenstva)
• Član povjerenstva: Mladen Karan (član povjerenstva)
• Član povjerenstva: Hrvoje Nuić (č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: 2019-09-05, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: TEHNIČKE ZNANOSTI; Računarstvo

Sažetak

U radu su razmotreni algoritmi korišteni u razvoju računalnog igrača za igru damu. Opisan je postupak donošenja optimalnih odluka uz proizvoljnu količinu računalnih resursa. Opisan je algoritam minimax za odabir poteza. Opisan je algoritam alfa-beta koji donosi odluke na isti način kao i algoritam minimax, ali ima bolju srednju vremensku složenost. Razmotrene su različite heuristike koje je moguće koristiti za algoritme minimax i alfa-beta. Opisan je algoritam pretraživanja stabla metodom Monte Carlo. Predloženi su budući pravci razvoja računalnog igrača.

Sažetak (engleski)

The paper considers algorithms used in the development od the computer player for the game of checkers. It describes the process of optimal decision making with an arbitrary quantity of computing resources. It also describes the minimax algorithm for move selection. Furthermore, it describes the alpha-beta algorithm that makes decisions in the same manner as the minimax algorithm, but with a better time complexity. The paper considers various heuristics that can be used for the minimax and alpha-beta algorithms. It describes the Monte Carlo tree search algorithm. The paper suggests future directions in the development of the computer player.

• Ključne riječi: dama; minimax; alfa-beta; stablo igre; MCTS; Monte Carlo
• Ključne riječi (engleski): checkers; draughts; minimax; alpha-beta; game tree; MCTS; Monte Carlo
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:168:600033
• Studijski program: Naziv: Računarstvo; Vrsta studija: sveučilišni; Stupanj studija: preddiplomski; Akademski / stručni naziv: sveučilišni/a prvostupnik/ prvostupnica (baccalaureus/baccalaurea) inženjer/inženjerka računarstva (univ.bacc.ing.comp.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Zatvoreni pristup
• Datum i vrijeme pohrane: 2020-01-07 19:56:01