モンテカルロ木探索における差分ゲームを用いた最善手探索

• Item type: Symposium(1)
• 公開日: 2015-10-30
• タイトル: モンテカルロ木探索における差分ゲームを用いた最善手探索
• タイトル / 言語: en
• タイトル: Findng Optimal Variations using Difference Games in MCTS
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_5794
• 資源タイプ: conference paper
• 著者所属: 九州工業大学大学院情報工学研究院知能情報工学研究系
• 著者所属: 九州工業大学情報工学府
• 著者所属(英): en
• 著者所属(英): Department of Artificial Intelligence, Faculty of Computer Science and Systems Engineering, Kyushu Institute of Technology
• 著者所属(英): en
• 著者所属(英): Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology
• 著者名: 中村, 貞吾; 石田, 竹至
• 著者名(英): Teigo, Nakamura; Takeshi, Ishida
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: モンテカルロ木探索は囲碁などのゲームで高い効果を発揮しているが，形勢が一方に大きく傾いた状況では十分な性能を発揮することができない．そのような局面では，どの着手を選択してもプレイアウトの勝率に大きな変化がなくなるため，各着手に差異が生まれず有効な着手を発見できなくなることが原因だと考えられる．この問題を克服するためにDAKVやその改良手法が提案されてはいるが，十分な解決とはなっていない．本論文では，組合せゲーム理論で用いられる差分ゲームの考え方を用いて，この問題を解決する手法を提案し，ヨセにおける次の一手問題を用いた実験によりその有効性を検証する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Monte Carlo Tree Search (MCTS) has strong success in the game of Go and many other games. State-of-the-art computer Go program becomes stronger year by year. Although the strength of state-of-the-art computer Go program has reached the high dan level of amateurs, some weakness or defects still remain. One of such defects is a bad endgame in an almost winning situation. Balancing MCTS using Dynamically Adjusting Komi Value (DAKV) is one of the methods to resolve the weakness in such endgames. In this paper, we propose another method using Combinatorial Game Theory (CGT) to resolve this kind of problem. Our method uses difference games for playouts in MCTS. We can make even game situation for whatever board positions using difference games and MCTS might find an optimal move. We show some experimental results using endgame problems on a Go magazine modified to fit with our experiments. Our method found an optimal move for some problems that even strong Go programs such as Fuego and Pachi failed to find the optimal move.
• 書誌情報: ゲームプログラミングワークショップ2015論文集; 巻 2015, p. 12-19, 発行日 2015-10-30
• 出版者 / 言語: ja
• 出版者: 情報処理学会