難しさが手番で異なる局面でのモンテカルロ木探索の性能の改善

IPSJ

Bibliographic Information

Other Title
  • Improvement of Performance of Monte Carlo Tree Search in Positions Where Difficulty Differs by Turns

Abstract

モンテカルロ木探索 (MCTS) は広い応用を持つ探索手法であり,特に囲碁で効果的であることが知られている.一方,置き碁や攻め合いなど苦手とする局面があるように，MCTSが有効に働く条件はまだはっきりと分かっていない．本研究では「最善手を互いに選び続ければ引き分けになるが,次善手を選んだ場合の不利益の度合いが手番によって異なる」という状況を詳しく分析した．まず，この性質を持つゲームではMCTS が最善手を逃しやすいことが，仮想ゲームを利用した分析を通じて分かった．そして改善する鍵が，終局時のスコアを利得に変換する調整にあることを示し，プレイアウト終了時のスコアの頻度が最大の位置に勝ち負けの評価の境界を定める手法を提案した．実際に対局実験を行ったところ，提案手法をMCTSに用いることで，通常のMCTSや別の調整法であるdynamic komiを用いる場合よりも高い勝率が得られた．

Monte-Carlo tree search (MCTS) is famous for its success in Go, while it is widely applied in many search problems. However, it is not clear that what kind of game conditions should be satisfied so that MCTS works effectively. For example, it is known that MCTS programs often play awkward moves in positions involving semeai and ones in handicapped games. This paper analyzes and discusses a property in even positions where two players have different penalties when they missed the best move. Analyses based on virtual games show that MCTS often fails to identify the best move in this situation and that the problem will be mitigated by adjusting a function that converts game scores gained by playouts into rewards (win, draw and loss). We presented to use a score of the maximum frequency as a threshold in the function. Experiments show that MCTS with the presented method works better than plain MCTS and MCTS with dynamic komi.

Journal

Related Projects

See more

Details 詳細情報について

  • CRID
    1050855522090920320
  • NII Article ID
    170000078726
  • Web Site
    http://id.nii.ac.jp/1001/00095809/
  • Text Lang
    ja
  • Article Type
    conference paper
  • Data Source
    • IRDB
    • CiNii Articles
    • KAKEN

Report a problem

Back to top