Browsing by Author "Wu, I. -Chen"

Now showing 1 - 2 of 2

Belief-State Monte Carlo Tree Search for Phantom Go
(2018-06-01)
Wang, Jiao
;
Zhu, Tan
;
Li, Hongye
;
Hsueh, Chu-Husan
;
Wu, I. -Chen
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 belief-state 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-BS-MCTS in Phantom Go by varying search parameters, also testify the proposed improvements.
Job-Level Proof Number Search
(2013-03-01)
Wu, I. -Chen
;
Lin, Hung-Hsuan
;
Sun, Der-Johng
;
Kao, Kuo-Yuan
;
Lin, Ping-Hung
This paper introduces an approach, called generic job-level search, to leverage the game-playing programs which are already written and encapsulated as jobs. Such an approach is well suited to a distributed computing environment, since these jobs are allowed to be run by remote processors independently. In this paper, we present and focus on a job-level proof number search (JL-PNS), a kind of generic job-level search for solving computer game search problems, and apply JL-PNS to solving automatically several Connect6 positions, including some difficult openings. This paper also proposes a method of postponed sibling generation to generate nodes smoothly, and some policies, such as virtual win, virtual loss, virtual equivalence, flagging, or hybrids of the above, to expand the nodes. Our experiment compared these policies, and the results showed that the virtual-equivalence policy, together with flagging, performed the best against other policies. In addition, the results also showed that the speedups for solving these positions are 8.58 on average on 16 cores.