Two-Stage Monte Carlo Tree Search for Connect6
Authors:
- 5 April 2011
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computational Intelligence and AI in Games
- Vol. 3 (2) , 100-118
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.Keywords
This publication has 18 references indexed in Scilit:
- NCTU6 Wins Man-Machine Connect6 Championship 2009ICGA Journal: The Journal of the Computer Games Community, 2009
- MONTE CARLO GO CAPTURING TACTIC SEARCHNew Mathematics and Natural Computation, 2008
- PROGRESSIVE STRATEGIES FOR MONTE-CARLO TREE SEARCHNew Mathematics and Natural Computation, 2008
- Amazons Discover Monte-Carlo2008
- Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search2007
- Monte-Carlo Go Reinforcement Learning Experiments2006
- Bandit Based Monte-Carlo Planning2006
- Algebraic connectivity of directed graphsLinear and Multilinear Algebra, 2005
- Games solved: Now and in the futureArtificial Intelligence, 2002
- GO‐MOKU SOLVED BY NEW SEARCH TECHNIQUESComputational Intelligence, 1996