Using evaluation functions in Monte-Carlo Tree Search

作者：Lorentz Richard^*

来源：Theoretical Computer Science, 2016, 644: 106-113.

DOI：10.1016/j.tcs.2016.06.026

• MCTS
• MCTS-EPT
• Breakthrough
• Havannah
• Amazons

For decades the game playing algorithms of choice have been based on the mini-max algorithm and have had considerable success in many games, e.g., chess and checkers. Recently a new algorithmic paradigm called Monte-Carlo Tree Search (MCTS) has been discovered and has proven to perform well in games where mini-max has failed, most notably in the game of Go. Many view mini-max and MCTS based searches as competing and incompatible approaches. However, a hybrid technique using features of both mini-max and MCTS is possible. We call this algorithm MCTS-EPT (MCTS with early playout termination) and study it from the context of three different games: Amazons, Breakthrough, and Havannah. This paper expands and elaborates on work presented in [1] and [2].

• 出版日期2016-9-6