Using evaluation functions in Monte-Carlo Tree Search

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].