Browsing by Author "Wang, Jiao"

Now showing 1 - 3 of 3

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.
Belief-state Monte-Carlo Tree Search for Phantom Games
(2015)
Wang, Jiao
;
Zhu, Tan
;
Li, Hongye
;
Hsueh, Chu-Hsuan
;
Wu, I-Chen
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.
Only-One-Victor Pattern Learning in Computer Go
(2017-03-01)
Wang, Jiao
;
Xiao, Chenjun
;
Zhu, Tan
;
Hsueh, Chu-Husan
;
Tseng, Wen-Jie
Automatically acquiring domain knowledge from professional game records, a kind of pattern learning, is an attractive and challenging issue in computer Go. This paper proposes a supervised learning method, by introducing a new generalized Bradley-Terry model, named Only-One-Victor, to learn patterns from game records. Basically, our algorithm applies the same idea with Elo rating algorithm, which considers each move in game records as a group of move patterns, and the selected move as the winner of a kind of competition among all groups on current board. However, being different from the generalized Bradley-Terry model for group competition used in Elo rating algorithm, Only-One-Victor model in our work simulates the process of making selection from a set of possible candidates by considering such process as a group of independent pairwise comparisons. We use a graph theory model to prove the correctness of Only-One-Victor model. In addition, we also apply the Minorization-Maximization (MM) to solve the optimization task. Therefore, our algorithm still enjoys many computational advantages of Elo rating algorithm, such as the scalability with high dimensional feature space. With the training set containing 115,832 moves and the same feature setting, the results of our experiments show that Only-One-Victor outperforms Elo rating, a well-known best supervised pattern learning method.