モンテカルロ木探索の性能の分析と改善

分析和改进蒙特卡罗树搜索的性能

• 批准号: 16J07455
• 负责人: 今川 孝久
• 金额: $ 0.83万
• 依托单位: The University of Tokyo
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2016
• 资助国家: 日本
• 起止时间: 2016-04-22 至 2018-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16J07455/
• 关键词: モンテカルロ木探索; 推定量; 探索アルゴリズム; 主観確率; 勝敗確定の情報

モンテカルロ木探索（MCTS）はゲームにおける代表的な探索の枠組みである．しかし，ゲームの性質とMCTSの性能の関係性については，まだ解明されていない点がある．本年度は，まず，多腕バンディット問題（MAB）における，期待値の最大値の推定量についての研究を行った．MABは確率的な報酬が得られるスロットマシーンが複数存在する時に，より多くの報酬を得られるプレイの仕方を求める問題である．MCTSの代表的なアルゴリズムであるUCTは，MABでの累積的な報酬の最大化を目指したアルゴリズムを木探索に応用したものであるように，MABはMCTSと密接な関わりがある．また，期待値の最大値の推定量は，最善手を判別するために重要である．判別のためには，以後も最善手を選び続けた（最も期待値が高くなるように手を選んだ）場合の報酬の期待値を比較する必要があるためである．本研究では，各確率変数に対し，その期待値が最大である確率の上限に基づき，重みを与え，その重み付き平均で期待値の最大値を推定する手法（SWE）を新たに提案した．理論的な解析を行い，推定値のバイアスが０に収束すること等を示した．加えて，実験を行い，提案手法の有効性を確かめた．様々なMABの設定の下で，提案手法は常に最良ではないものの，多くの設定で良い結果となった．次に，上記の手法SWEのMCTSへの応用を行った．既存手法UCTでは，子の価値の推定を子孫から行ったシミュレーション結果の平均で行う．まず，実験を行い，MABで，サンプルの平均による推定の代わりにSWEを使うことで推定値の精度を改善出来ることを確かめた．そして，UCTにおける，平均による推定の代わりに，SWEよる推定を行う手法を提案した．ゲームでの終盤に近いモデルと，序盤に近いモデルの２種類で，実験を行い，後者のモデルでの提案手法の有効性を示した．

The MCTS represents the group of explorers. The relationship between the properties of MCTS and the performance of MCTS is discussed. This year, we conducted research on the estimation of maximum expected values for the MAB problem. The MAB problem determines the rate of compensation for multiple employees. The MCTS problem is representative of UCT. MAB's cumulative compensation maximization refers to the use of MCTS to explore the relationship between MAB and MCTS. It is important to estimate the maximum value of expectation. To determine whether the best candidate is the best candidate in the future, compare the expected salary value in the case where the expected salary value is high. In this study, we propose a new method (SWE) for estimating the maximum expected value of each accuracy rate, the maximum expected value of each accuracy rate, and the maximum expected value of each accuracy rate. The theoretical analysis shows that there is no such thing as a theoretical analysis. Add MAB settings are often the best way to propose, and many settings are the best way to result. Second, note that SWE and MCTS can be used in different ways. Existing method UCT is used to estimate the value of children and children. MAB, MAB UCT, average, presumptive, SWE, presumptive, modus operandi. There are two kinds of proposals in the final stage of the game, and the two kinds of proposals in the final stage of the game are effective.

项目成果

モンテカルロ木探索における状態価値の推定方法の改善

蒙特卡罗树搜索中状态值估计方法的改进

• 发表时间: 2017
• 期刊: ゲームプログラミングワークショップ（GPW）2017論文集
• 作者: 山田亮太;松谷悠佑;木村尭朗;伊達広行;Takahisa Imagawa and Tomoyuki Kaneko;今川 孝久，金子知適
• 通讯作者: 今川 孝久，金子知適

Monte Carlo Tree Search with Robust Exploration

具有稳健探索的蒙特卡罗树搜索

• DOI: 10.1007/978-3-319-50935-8_4
• 发表时间: 2016
• 期刊: LNCS, Computers and Games
• 作者: 山田亮太;松谷悠佑;木村尭朗;伊達広行;Takahisa Imagawa and Tomoyuki Kaneko;今川 孝久，金子知適;T. Imagawa and T. Kaneko
• 通讯作者: T. Imagawa and T. Kaneko

Estimating the maximum expected value through upper confidence bound of likelihood

通过似然置信上限估计最大期望值

• 发表时间: 2018
• 期刊: 2017 Conference on Technologies and Applications of Artificial Intelligence (TAAI 2017)
• 作者: 山田亮太;松谷悠佑;木村尭朗;伊達広行;Takahisa Imagawa and Tomoyuki Kaneko
• 通讯作者: Takahisa Imagawa and Tomoyuki Kaneko

モンテカルロ木探索における子孫の勝敗確定時のプレイアウト結果の修正

修正了蒙特卡罗树搜索中后代获胜或失败时的比赛结果

• 发表时间: 2016
• 期刊: ゲームプログラミングワークショップ2016論文集
• 作者: 山田亮太;松谷悠佑;木村尭朗;伊達広行;Takahisa Imagawa and Tomoyuki Kaneko;今川 孝久，金子知適;T. Imagawa and T. Kaneko;今川孝久 金子知適
• 通讯作者: 今川孝久 金子知適