20.500.12556/DKUM-72471 Drevesno preiskovanje Monte Carlo v igri Havannah Monte Carlo tree search in game Havannah V diplomskem delu predstavimo namizno igro Havannah in algoritem drevesnega preiskovanja Monte Carlo. Slednji je v zadnjih letih pripomogel k občutno boljši zmogljivosti računalniških igralcev v kompleksnih namiznih igrah s popolno informacijo, med katere spada tudi Havannah. Implementiramo tri računalniške igralce igre Havannah: prvi uporablja osnovno različico drevesnega preiskovanja Monte Carlo, drugi uporablja algoritem hitrega ocenjevanja vrednosti akcij, tretji pa kombinacijo drevesnega preiskovanja Monte Carlo s hitrim ocenjevanjem vrednosti akcij. Na koncu primerjamo vse tri igralce v medsebojnih igrah in v igrah proti človeškemu nasprotniku. In this thesis, we describe the board game Havannah and the Monte Carlo Tree Search algorithm. The latter has recently contributed to significant improvement of computer play in complex board games with perfect information, such as Havannah. We implement three computer players for Havannah: the first one using basic Monte Carlo Tree Search, the second one using Rapid Action Value Estimation algorithm and the third one using a combination of the two, called Monte Carlo Rapid Action Value Estimation. In the end, we compare the players' performances in matches against each other, as well as against a human player. igra na deski Havannah drevesno preiskovanje Monte Carlo hitro ocenjevanje vrednosti akcij igre s popolno informacijo board game Havannah Monte Carlo tree search Rapid Action Value Estimation games with perfect information true true false V. Krajnc Slovenski jezik Angleški jezik Diplomsko delo/naloga 2018-09-26 22:43:15 2018-11-14 08:59:33 2022-08-01 22:46:07 2019-07-11 19:20:04 2018 0 [Maribor 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 004.832.2(043.2) 21891350 URN:SI:UM:DK:ZKXMDMEM UN_Krajnc_Vanesa_2018.pdf UN_Krajnc_Vanesa_2018.pdf 1 E5D128CA42A327445A0B390BDBA0B392 1c32ecbb9d5ce21fb5b85035b24f3e857586799326f40d8b29f15d985b123fdd 67c69734-7c10-11eb-bb7a-00155d0001ca 20.500.12556/dkum/d202f530-55ac-4d5c-bf77-0df2dfda00c0 https://dk.um.si/Dokument.php?lang=slv&id=130366 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0