Belief-state Monte-Carlo tree search for Phantom games

Jiao Wang, Tan Zhu, Hongye Li, Chu Hsuan Hsueh, I-Chen Wu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

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.

Original languageEnglish
Title of host publication2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages267-274
Number of pages8
ISBN (Electronic)9781479986217
DOIs
StatePublished - 4 Nov 2015
Event2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Tainan, Taiwan
Duration: 31 Aug 20152 Sep 2015

Publication series

Name2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings

Conference

Conference2015 IEEE Conference on Computational Intelligence and Games, CIG 2015
CountryTaiwan
CityTainan
Period31/08/152/09/15

Fingerprint Dive into the research topics of 'Belief-state Monte-Carlo tree search for Phantom games'. Together they form a unique fingerprint.

  • Cite this

    Wang, J., Zhu, T., Li, H., Hsueh, C. H., & Wu, I-C. (2015). Belief-state Monte-Carlo tree search for Phantom games. In 2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings (pp. 267-274). [7317917] (2015 IEEE Conference on Computational Intelligence and Games, CIG 2015 - Proceedings). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CIG.2015.7317917