Drevesno preiskovanje Monte Carlo v igri Havannah

diplomsko delo

Vanesa Krajnc (Author), Damjan Strnad (Mentor), Štefan Kohek (Co-mentor)

Abstract

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.

Keywords

igra Havannah;dreveno preiskovanje Monte Carlo;hitro ocenjevanje vrednosti akcij;diplomske naloge;

Data

Language:	Slovenian
Year of publishing:	2018
Typology:	2.11 - Undergraduate Thesis
Organization:	UM FERI - Faculty of Electrical Engineering and Computer Science
Publisher:	V. Krajnc
UDC:	004.832.2(043.2)
COBISS:	21891350
Views:	885
Downloads:	130
Average score:	0 (0 votes)
Metadata:

Other data

Secondary language:	English
Secondary title:	Monte Carlo tree search in game Havannah
Secondary abstract:	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.
Secondary keywords:	board game Havannah;monte Carlo tree search;rapid action value estimation;games with perfect information;
URN:	URN:SI:UM:
Type (COBISS):	Bachelor thesis/paper
Thesis comment:	Univ. v Mariboru, Fak. za elektrotehniko, računalništvo in informatiko, Računalništvo in informacijske tehnologije
Pages:	VI, 29 f.
ID:	10961952