局面タブーリストを内包したモンテカルロ木探索の19路盤囲碁への応用

Abstract

"This paper proposes a modied Monte-Carlo tree search (abbreviated as MCTS) for playing 19×19 go. Diversifying playout causes the MCTS to have behavior just like a best- first search in a more uniformly- broadened tree without extending toward depth direction. The diversification of playout could be brought about by the process of excluding the same game states obtained from successive playouts. So as to achieve the diversity, each leaf node in the searching tree includes multiple tabu lists, whose element is a game state. Here, a game state is expressed as a value of Zobrist hash. The first game state, which has a hash value, to several ones from starting a playout are sequentially enqueued into the tabu lists. If a game state is labeled as ""tabu"", then the move to lead the same game state is treated as a prohibited move during a preset tabu tenure. Thereby, it is possible to select a good move which may be the best move, because the varieties of candidate move in the Monte-Carlo tree have been widening. Furthermore, we also propose two update methods about game state tabu lists. One is a sequential update method, and the other is a mass update one based on winning or losing of the playout."