Some improvements in Monte Carlo tree search algorithms for sudden death games

Article type: Research Article

Authors: Chen, Chih-Hung^{; **} | Wu, Wei-Lin^{; **} | Chen, Yu-Heng^{; **} | Lin, Shun-Shii^{; **; *}

Affiliations: National Taiwan Normal University, Taiwan

Correspondence: [*] Corresponding author. E-mail: linss@csie.ntnu.edu.tw.

Note: [**] Department of Computer Science and Information Engineering, National Taiwan Normal University, Taipei, Taiwan, R.O.C.

Abstract: The average reward problem in the traditional Monte-Carlo tree search algorithms troubles the sudden death games for a long time, because of the average reward criterion will reduce the probability of a deterministic result. But this does not bother the non-sudden death games, such as Go, which can focus only on higher win rates rather than higher scores. In this work, we propose the miniMax-Monte-Carlo tree search with depth rewards to Outer-Open Gomoku (a variant of Gomoku) to discover a forced win/lose without any human knowledge, evaluation function, or pre-training. And it can solve not only the average reward problem but also the inaccurate win-rate problem in deep playout simulation in sudden death games. Finally, we propose a new integrated framework named BBQ (Big, Best, Quick win) MCTS for improving the performance of traditional MCTS.

Keywords: Monte-Carlo tree search, miniMax search, depth rewards, sudden death games, Outer-Open Gomoku, Tic-Tac-Toe

DOI: 10.3233/ICG-180065

Journal: ICGA Journal, vol. 40, no. 4, pp. 460-470, 2018