Two-Stage Monte Carlo Tree Search for Connect6

Abstract

Recently, Monte Carlo tree search (MCTS) has become a well-known game search method, and has been successfully applied to many games. This method performs well in solving search trees with numerous branches, such as Go, Havannah, etc. Connect6 is a game involving a search tree with numerous branches, and it is also one of the sudden-death games. This paper thus proposes a new MCTS variant related to Connect6, called two-stage MCTS. The first stage focuses on threat space search (TSS), which is designed to solve the sudden-death problem. For the double-threat TSS in Connect6, this study proposes an algorithm called iterative threat space search (ITSS) which combines normal TSS with conservative threat space search (CTSS). The second stage uses MCTS to estimate the game-theoretic value of the initial position. This stage aims at finding the most promising move. The experimental result shows that two-stage MCTS is considerably more efficient than traditional MCTS on those positions with TSS solution in Connect6. Furthermore, according to Connect6 heuristic knowledge, this paper uses relevance-zone search to accelerate identifying winning and losing moves.