| Item type |
Symposium(1) |
| 公開日 |
2014-10-31 |
| タイトル |
|
|
タイトル |
多腕バンディットアルゴリズムのMCTSへの応用と性能の分析 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Applying Multi Armed Bandit Algorithms to MCTS and Those Analysis |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_5794 |
|
資源タイプ |
conference paper |
| 著者所属 |
|
|
|
東京大学大学院総合文化研究科 |
| 著者所属 |
|
|
|
東京大学大学院総合文化研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Arts and Sciences, The University of Tokyo |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Arts and Sciences, The University of Tokyo |
| 著者名 |
今川, 孝久
金子, 知適
|
| 著者名(英) |
Takahisa, Imagawa
Tomoyuki, Kaneko
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
UCT は囲碁やGeneral Game Playing などの応用で効果を発揮している探索手法で，多腕バンディット問題のアルゴリズムであるUCB1 をモンテカルロ木探索(MCTS) に応用したものである．多腕バンディット問題には，KL-UCB, Thompson Sampling, UCB1-Tuned などUCB1 より優れるとされる様々なアルゴリズムが提案されてきている. そこで本研究では、UCB1 に変えてそれらのアルゴリズムをMCTS に用いることを提案し，実際の性能についてP-game と呼ばれる仮想的なゲーム木を用いて分析した. 実験の結果，UCB1 よりもKL-UCB, Thompson Sampling, UCB1-Tuned がMCTS においても優れることが，期待通りに確認された．ただし，各アルゴリズムの差よりも各仮想的なゲーム木の性質に因る性能の違いの方が大きいことも同時に確認されている．本稿で用いたP-game は，広く探索アルゴリズムの性能の評価で用いられているが，MCTS の評価に用いる場合は，木の作り方に注意を払う必要がある可能性がある． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
UCT is a search method which is effective in such as Go and General Game Playing, and it is a application of UCB1, an algorithm of multi-armed bandit proplem to Monte-Carlo tree search (MCTS). In multi-armed bandit problem, various algorithms better than UCB1 have been proposed, such as KL-UCB, Thompson Sampling, UCB1-Tuned. In our research, the other algorithms instead of UCB1 are applied to MCTS and, it's effectiveness are analized by P-game, a virtual game. The result of the experiments show that KL-UCB, Thompson Sampling and UCB1-Tuned are better than UCB1 as it is expected, but also difference of effectiveness caused by properties of P-game trees is larger than difference between the algorithms. P-game is widely used for evaluating effectiveness of search algorithms, but we may need to take care of creating P-game tree when evaluating MCTS. |
| 書誌情報 |
ゲームプログラミングワークショップ2014論文集
巻 2014,
p. 145-150,
発行日 2014-10-31
|
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-GPWS2014023.pdf (1.1 MB)
