Belief-state Monte Carlo tree search for phantom go

Jiao Wang*, Tan Zhu, Hongye Li, Chu Husan Hsueh, I. Chen Wu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

Phantom Go is a derivative of Go with imperfect information. It is challenging in AI field due to its great uncertainty of the hidden information and high game complexity inherited from Go. To deal with this imperfect information game with large game tree complexity, a general search framework named beliefstate Monte Carlo tree search (BS-MCTS) is put forward in this paper. BS-MCTS incorporates belief-states into Monte Carlo Tree Search, where belief-state is a notation derived from philosophy to represent the probability that speculation is in accordance with reality. In BS-MCTS, a belief-state tree, in which each node is a belief-state, is constructed and search proceeds in accordance with beliefs. Then, Opponent Guessing and Opponent Predicting are proposed to illuminate the learning mechanism of beliefs with heuristic information. The beliefs are learned by heuristic information during search by specific methods, and we propose Opponent Guessing and Opponent Predicting to illuminate the learningmechanism. Besides, some possible improvements of the framework are investigated, such as incremental updating and all moves as first (AMAF) heuristic. Technical details are demonstrated about applying BS-MCTS to Phantom Go, especially on inference strategy. We examine the playing strength of the BS-MCTS and AMAF-BSMCTS in Phantom Go by varying search parameters, also testify the proposed improvements. 2017 IEEE.

Original languageEnglish
Article number7997911
Pages (from-to)139-154
Number of pages16
JournalIEEE Transactions on Games
Volume10
Issue number2
DOIs
StatePublished - Jun 2018

Keywords

  • All moves as first (AMAF)
  • Belief-state
  • Imperfect information games
  • Monte Carlo methods
  • Phantom Go

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

Cite this