TY - GEN
T1 - Belief-state Monte-Carlo tree search for Phantom games
AU - Wang, Jiao
AU - Zhu, Tan
AU - Li, Hongye
AU - Hsueh, Chu Hsuan
AU - Wu, I-Chen
PY - 2015/11/4
Y1 - 2015/11/4
N2 - Playing games with imperfect information is a very challenging issue in AI field due to its high complexity. Phantom game is a kind of such games, which usually has a large game-Tree complexity and has little research achievements until now. In Phantom games, rational human players commonly select actions according to their beliefs in the game, which can be represented as a concept of belie f-state. To the best of our knowledge, our paper is the first article to incorporate belief-states in the Monte-Carlo Tree Search, and the proposed algorithm is named BS-MCTS (Belief-state Monte-Carlo Tree Search). In BS-MCTS, a belief-state tree, in which each node is a belief-state, is constructed and the search procedure is in accordance with beliefs updated by heuristic search information. We also present two novel implementations in the belief learning, that are Opponent Guessing and Opponent Predicting, concerning the probability on the possible states and on future actions of the opponent respectively. To prove the effectiveness of our algorithm, BS-MCTS is applied to Phantom Tic-Tac-Toe and Phantom Go against other Monte-Carlo methods. The experimental results demonstrate that our method is outstanding and advanced. Moreover, based on BS-MCTS, our Phantom Go program had consecutively won three championships in Chinese National Tournaments.
AB - Playing games with imperfect information is a very challenging issue in AI field due to its high complexity. Phantom game is a kind of such games, which usually has a large game-Tree complexity and has little research achievements until now. In Phantom games, rational human players commonly select actions according to their beliefs in the game, which can be represented as a concept of belie f-state. To the best of our knowledge, our paper is the first article to incorporate belief-states in the Monte-Carlo Tree Search, and the proposed algorithm is named BS-MCTS (Belief-state Monte-Carlo Tree Search). In BS-MCTS, a belief-state tree, in which each node is a belief-state, is constructed and the search procedure is in accordance with beliefs updated by heuristic search information. We also present two novel implementations in the belief learning, that are Opponent Guessing and Opponent Predicting, concerning the probability on the possible states and on future actions of the opponent respectively. To prove the effectiveness of our algorithm, BS-MCTS is applied to Phantom Tic-Tac-Toe and Phantom Go against other Monte-Carlo methods. The experimental results demonstrate that our method is outstanding and advanced. Moreover, based on BS-MCTS, our Phantom Go program had consecutively won three championships in Chinese National Tournaments.
UR - http://www.scopus.com/inward/record.url?scp=84964434695&partnerID=8YFLogxK
U2 - 10.1109/CIG.2015.7317917
DO - 10.1109/CIG.2015.7317917
M3 - Conference contribution
AN - SCOPUS:84964434695
T3 - 2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings
SP - 267
EP - 274
BT - 2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 31 August 2015 through 2 September 2015
ER -