ゲーム木検索

美添　一樹（情報理工学系研究科コンピュータ科学専攻　助教）

人間と同様にゲームをプレイする機械を作るということは，人類のひとつの夢であるだけでなく，コンピュータの進歩の観点からも興味深い題材であり，多くの研究者の興味を引きつけてきた。

1997年にIBMのDeepBlueがチェスの世界チャンピオンを破った例が最も有名である。 また，昨年情報処理学会50周年記念イベントとして行われた清水市代女流王将対コンピュータ将棋「あから2010」の対局では，コンピュータが勝利を収め，コンピュータ囲碁も近年急速に棋力を伸ばしている。

ゲーム木とはゲームの可能な手順を木によって表現したものである。 将棋や囲碁のゲーム木のサイズは巨大であり，すべてをしらみつぶしに探索することは半永久的に不可能である。 しかしゲームをプレイする場合には，制限時間以内に着手を選択する必要がある。 ゲーム木探索は，広大な探索空間に対してある程度のリアルタイム性を要求する，難しい問題である。

ゲームをプレイする場合には先読みと形勢判断が必要である。 相手よりも深く先読みができて，正確に形勢判断ができれば負けることはない。

将棋ではalpha-beta探索を用いた先読みにより，通常の計算機でも1秒間で数十万から百万局面以上の先読みを行う。 これに評価関数を用いた形勢判断を組み合わせることによって，現在ではトッププロに迫る棋力を獲得している。 評価関数とは局面の形勢を数値化するものである。 近年は機械学習の理論に基づいて自動的に評価関数を作成する手法が主流になっており，開発者自身は将棋が強くなくとも，強い将棋プログラムを作成することが可能となった。

囲碁は評価関数の作成が困難なゲームであるために，コンピュータにとって非常に難しいゲームとして知られていたが， 2006年にモンテカルロ木探索が発明されたことによって急速に棋力が向上し，現在ではアマ五段近くに到達している。 現在の筆者の研究テーマはモンテカルロ木探索の並列化である。 alpha-beta探索は並列化が難しくスパコンの利用が難しいが，モンテカルロ木探索はスパコンを活用することにより大幅な性能向上が期待できる。 コンピュータ囲碁がプロ棋士に迫るという予測も現実味を帯びてきた。

ゲーム木探索の進歩は，ハードウェアの進歩とそれを活用するアルゴリズムの進歩を象徴的に示す成果である。