Monte Carlo Tree Search with Bayesian Model Averaging for the Game of Go
John Jeong You · 2012
Computer Go is the next grand challenge for AI games research and in recent years, Monte Carlo tree search (MCTS) algorithms have been used in the top-performing computer Go systems. MCTS is a sampling method for sequential processes that incrementally builds a tree to guide the sampling process. This thesis presents three novel contributions for MCTS in computer Go. In the computer Go literature, there has been little effort to learn from local similarities between search tree nodes (i.e., Go boards) thus leading to potential sampling inefficiency. In this thesis, we first contribute locally weighted regression (LWR) as an update method in MCTS to address this problem. LWR uses similarity kernels to perform a weighted average of sampled outcomes from similar sequences of play. We evaluate a variety of kernels in LWR for MCTS and as our second major contribution, we show that the top-performing RAVE variant of MCTS can be interpreted as LWR with a novel data-dependent kernel that does not require a priori knowledge of Go. As our third contribution, we note that MCTS algorithms have derived great benefit from combining or mixing multiple models; i.e., multiple models are proposed to predict the outcome of play from a given Go board and these models are averaged together to provide a more accurate and lower-variance prediction. In this thesis we propose Bayesian model averaging (BMA) as a theoretically well-founded alternative mixing model for MCTS. BMA shows reasonable performance compared to other previously proposed mixing methods but crucially has a clear semantics for its tuning parameter that can be interpreted as a model prior. Furthermore, compared to similarly principled mixing methods such as minimum mean square error (MSE), BMA has more expressive power concerning the classes of mixture models it can support. Hence we claim that BMA is an attractive alternative to existing mixing models for MCTS. Finally, we note that while this thesis presents novel algorithms, theoretical justifications, and insights for MCTS in computer Go, we conjecture these ideas may be useful in the wider context of goal-oriented search, planning, and learning that is pervasive throughout AI.