Thesis or Dissertation モンテカルロ木探索における予測読みに関する研究

荒井, 光  ,  アライ, ヒカル

pp.1 - 42 , 2015-03-25 , The University of Electro-Communications
Description
本研究は,モンテカルロ木探索アルゴリズムの探索木の成長に大きく関わるパラメタを変更することにより,コンピュータ囲碁における予測読みの強化を試みた.予測読みとは,相手が探索しているときにこちらも探索を行い,その探索結果を次の自身の着手を決定する探索に使用する技術のことである.予測読みの情報を次の手番時に活かすためには実際の相手の着手を深く探索することが一番良い.しかし,これには2つの相反する要素を持つ.つまり,相手の着手を当てるためには手を広く読む必要があるのに対し,一方で深く探索する方が良いという2つの要素である.よって,予測読みは良い着手を探索することよりも,実際の相手の着手を深く探索することが要求される.このことから,手番時と同じ探索を行うのではなく,他の探索手法を行うことを検討する余地があると考えられる. モンテカルロ木探索には,木の成長に大きく関わるパラメタが2つある.1つめはUCB1値の勝率とバイアスのバランスを決定するパラメタである.このパラメタ値が大きいとバイアスの値が大きくなり,選択回数が少ない着手が多く読まれやすくなる.よって,より広く手を探索するようになる.2つめはProgressive Wideningの閾値を決定するパラメタである.このパラメタ値を大きくすると,候補手に設定される各閾値が大きくなり,結果として探索の候補手を減らす.この2つのパラメタ値を変更することにより,手番時と異なった探索を実現する. 本研究では,まず村松研究室の学生により開発されている囲碁プログラムstormに基本的な予測読みを実装しどの程度棋力が向上するかオープンソース囲碁プログラムGNU Goとの対局実験により検証した.そして,探索時にパラメタ値を変更することにより,生成された探索木の変化を示した.また,予測読み時にパラメタ値の変更を行う手法をstormに実装し,13路盤では適切なパラメタ値を設定することで,GNU Goとの対戦において棋力が向上すること示した.そして,コンピュータ囲碁専用の対局サーバCGOSに提案手法を実装したstormを接続し,複数の異なるプログラムと対戦させた場合に,適切なパラメタ値を設定することで,予測読みを行わない場合と比較して,Eloレーティングが100以上向上することも示した.

Number of accesses :  

Other information