効率的で正しいゲーム木探索アルゴリズムの研究

点击翻译按钮获取中文摘要

探索アルゴリズムはコンピュータサイエンスにおける基本的な手法であり、重要な応用分野の一つとしてゲームがある。ゲームの利用者の観点からは、探索アルゴリズム(ゲーム木探索アルゴリズム)が高速にかつ正しく問題を解けることが要求される。ところが、これまでのゲーム木探索アルゴリズムは、探索効率を落としたくないために正当性を保証しないアルゴリズムを利用するか、または解の正当性を保証したいために何千倍も遅い非効率なアルゴリズムを用いるかというどちらかの妥協を行ってきた。本研究では、このような探索効率と正当性の問題を解決するのが目標である。平成18年度の研究では、探索アルゴリズムの正当性を理論的に証明でき、効率的であることが分かったので、平成19年度は、研究目標にある通り、探索アルゴリズムのさらなる効率化を行った。囲碁とチェッカーを探索の題材に選び、コンピュータ上に開発したアルゴリズムを実装し、実験的に効率の良いアルゴリズムであることを示した。本研究の大きな成果として、チェッカーが引き分けであることを証明し、Science誌に掲載され、2007年度の科学的進歩の第10位にランクされた。また、最新の関連研究を調査し、本研究との比較を行い、開発した手法が優れていることが分かった。さらに、囲碁を題材にして、ランダム・サンプリングを用いた方法と効率に関する研究を開始した。ランダム・サンプリングを行う対象としては、囲碁を用いた。ランダム・サンプリングと木探索を組み合わせると非常に有効であることが、実験的に分かった。