Monte Carlo Tree Search

Monte Carlo Tree Search (MCTS) is the basis of all state of the art Go programs, including Fuego. In our research, we also investigate Monte Carlo techniques in planning, and the close connections between Reinforcement learning and MCTS. Those publications are listed here.

Publications

D. Silver, R. Sutton and M. Müller. Temporal-Difference Search in Computer Go. To appear in Machine Learning, 2012.

J. Styles, H. Hoos and M. Müller. Automatically Configuring Algorithms for Scaling Performance. Accepted for Learning and Intelligent OptimizatioN Conference, LION 6, 2012.

H. Brausen, R. Hayward, M. Müller, A. Qadir and D. Spies. Blunder cost in Go and Hex. Accepted for Advances in Computer Games 13, 2011.

G. Van Eyck and M. Müller. Revisiting Move Groups in Monte Carlo Tree Search. Accepted for Advances in Computer Games 13, 2011.

D. Tom and M. Müller. Computational Experiments with the RAVE Heuristic. Lecture Notes in Computer Science 6515, pages 69-80, editors J. van den Herik, H. Iida and A. Plaat, Springer 2011. DOI link

M. Enzenberger, M. Müller, B. Arneson and R. Segal. Fuego - An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search. IEEE Transactions on Computational Intelligence and AI in Games, 2(4), 259-270. Special issue on Monte Carlo Techniques and Computer Go, 2010.

M. Müller. Fuego-GB Prototype at the Human machine competition in Barcelona 2010: a Tournament Report and Analysis. Technical Report TR 10-08, Dept. of Computing Science, University of Alberta, Edmonton, Alberta, Canada, 2010.

D. Tom. Investigating UCT and RAVE: steps towards a more robust method. MSc thesis, University of Alberta, 2010.

D. Silver. Reinforcement Learning and Simulation-Based Search in Computer Go. PhD thesis, University of Alberta, 2009.

D. Silver and G. Tesauro. Monte-Carlo simulation balancing. In Danyluk et al., ICML 2009.

M. Enzenberger and M. Müller. A lock-free multithreaded Monte-Carlo tree search algorithm, 2009. Advances in Computer Games 12, LNCS 6048, pages 14-20, Springer. http://dx.doi.org/10.1007/978-3-642-12993-3_2.

D. Tom and M. Müller. A study of UCT and its enhancements, 2009. Advances in Computer Games 12, LNCS 6048, pages 55-64, Springer. DOI link

M. Enzenberger and M. Müller. Fuego - an open-source framework for board games and Go engine based on Monte-Carlo tree search. Technical Report TR 09-08, Dept. of Computing Science. University of Alberta, Edmonton, Alberta, Canada, 2009.

M. Müller. Fuego at the Computer Olympiad in Pamplona 2009: a tournament report. Technical Report TR 09-09, Dept. of Computing Science. University of Alberta, Edmonton, Alberta, Canada, 2009.

S. Gelly and D. Silver. Achieving master level play in 9 x 9 computer go. In Dieter Fox and Carla P. Gomes, editors, AAAI, pages 1537-1540. AAAI Press, 2008.

D. Silver, R. Sutton, and M. Müller. Sample-based learning and search with permanent and transient memories. In W. Cohen, A. McCallum, and S. Roweis, editors, Machine Learning, Proceedings of the Twenty-Fifth International Conference (ICML 2008), volume 307 of ACM International Conference Proceeding Series, pages 968-975, Helsinki, Finland, 2008. ACM. Top tier. Acceptance rate: 158/583 = 27%.

L. Zhao and M. Müller. Using artificial boundaries in the game of Go. In J. van den Herik, X. Xu, Z. Ma, and M. Winands, editors, Computer and Games. 6th International Conference, volume 5131 of Lecture Notes in Computer Science, pages 81-91, Beijing, China, 2008. Springer. http://dx.doi.org/10.1007/978-3-540-87608-3_8. Acceptance rate: 24/40 = 60%.

S. Gelly and D. Silver. Combining online and offline knowledge in UCT. In Z. Ghahramani (ed.), ICML 2007, pages 273-280.

Created: Jan 20, 1998 Last modified: Feb 16, 2012

Martin Müller