標題: Belief-state Monte-Carlo Tree Search for Phantom Games
作者: Wang, Jiao
Zhu, Tan
Li, Hongye
Hsueh, Chu-Hsuan
Wu, I-Chen
資訊工程學系
Department of Computer Science
公開日期: 2015
摘要: 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.
URI: http://hdl.handle.net/11536/135524
ISBN: 978-1-4799-8622-4
ISSN: 2325-4270
期刊: 2015 IEEE CONFERENCE ON COMPUTATIONAL INTELLIGENCE AND GAMES (CIG)
起始頁: 267
結束頁: 274
Appears in Collections:Conferences Paper