Not Logged In

Analyzing the impact of knowledge and search in Monte Carlo Tree Search in Go

Domain-specific knowledge plays a significant role in the success of many Monte Carlo Tree Search (MCTS) programs. The details of how knowledge affects MCTS are still not well understood. In this thesis, we focus on identifying the effects of different types of knowledge on the behaviour of the Monte Carlo Tree Search algorithm, using the game of Go as a case study. We measure the performance of each type of knowledge, and of deeper search by using two main metrics: The move prediction rate on games played by professional players, and the playing strength of an implementation in our program Fuego. We compare the result of these two evaluation methods in detail, in order to understand how effective they are in fully understanding a program’s be- haviour. A feature-based approach refines our analysis tools, and addresses some of the shortcomings of these two evaluation methods. This approach allows us to interpret different components of knowledge and deeper search in different phases of a game, and helps us to obtain a deeper understanding of the role of knowledge and its relation with search in the MCTS algorithm.

Citation

F. Haqiqat, M. Müller. "Analyzing the impact of knowledge and search in Monte Carlo Tree Search in Go". Workshop on Computer Games (CGW), Springer, 1017, pp 127-146, July 2018.

Keywords: Monte Carlo Tree Search, Go, Search, Knowledge, Evaluation
Category: In Workshop
Web Links: Springer
  doi

BibTeX

@misc{Haqiqat+Müller:CGW18,
  author = {Farhad Haqiqat and Martin Müller},
  title = {Analyzing the impact of knowledge and search in Monte Carlo Tree
    Search in Go},
  Booktitle = {Communications in Computer and Information Science},
  Publisher = "Springer",
  Volume = "1017",
  Pages = {127-146},
  booktitle = {Workshop on Computer Games (CGW)},
  year = 2018,
}

Last Updated: June 30, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo