Let’s Catch the Train to Monte-Carlo1

While Monte-Carlo Tree Search (MCTS) has successfully been implemented in many games, its effectiveness appears to be greatest in the game of Go. In this thesis, Hendrik Baier even earmarks MCTS “the dominating paradigm in the challenging field of computer Go.” Having mentioned Go, there is no escaping linking another statement from this thesis to the recent astonishing accomplishment by DeepMind’s AlphaGo. It illustrates how fast computer game playing is currently improving – irrespective of whether you call that Artificial Intelligence or not. In Section 3.2.1, Baier writes: “the world’s best human Go players are still superior to the best computer programs, and writing a master strength Go program stands as a grand challenge of AI.” Four months after Hendrik Baier defended this PhD thesis, AlphaGo convincingly beat Lee Sedol 4-1. Lee is considered to be the best Go player in the world over the last decade.2 A magnificent achievement indeed, but let us not forget that it is the culmination of all the hard work over the past decades of a great many computer games researchers who have contributed to this monumental victory. One of the three pillars on which rests the success of AlphaGo is MCTS, the topic of this thesis. It would be interesting to know whether AlphaGo contains any of the MCTS enhancements that Hendrik Baier describes in this thesis or in any of his scientific papers. The oldest paper I could find (Baier and Drake, 2010), was published in the IEEE Transactions on Computational Intelligence in 2010, and describes an improvement to the Last-Good-Reply Policy in Monte Carlo Go.