ベイズ統計を用いたゲーム木探索

ゲーム 統計学

将棋、チェス、オセロといったゲームの「コンピュータ思考エンジン」を作るための「ゲーム木探索アルゴリズム」の分野では、「先読みする手をいかに絞り込むか」がメインテーマの一つとなっている。読む手をうまく絞れれば時間をかけずに答えを出せるが、読み落としのリスクも増えるので、工夫が必要になる。

将棋の思考エンジンの場合、「激指」で開発された「実現確率探索」という方法が有名である。これは、アルゴリズム的に抽出した「手の属性」（自然言語処理でいうところの素性）に応じて「読む深さ」を変えるというもので、例えば通常は「１手」とカウントするところを、特定の属性（例えば「直前に動いた駒をタダで取る」という属性）を持つ手だけは「０．５手」カウントなどとすることによって、同じ「N手先まで読むサブルーチン」でも手の属性によって読む深さを変える事ができる（カウント数の少ない手ほど、より深く読む）というわけだ。その「手の属性」を色々用意しておいて、各属性の「手のカウント数」を棋譜データから統計処理を行って決めることで、より人間に近い読みをアルゴリズム化できるというのがこの手法の特長でもある。ちなみに「実現確率」というのはパラダイムを示唆するネーミングであり、実際にゲーム木の上で確率測度を構成するわけではない。

さて、ゲーム木探索ではそれぞれの手について「先を読む前」と「先を読んでみた後」で手の価値（評価値）が変わってくる。すなわち、前者は「その手を指した直後の局面の有利不利（評価関数）」で決まり、後者は「ミニマックス法」という再帰的な計算アルゴリズムで決まる。これは決定論的なモデルであり、手の価値はどの時点でも「値は分布ではなく一点」になる。ここで、「価値の確率分布*1」を考えることによってベイズ統計の枠組みを応用できないだろうか。「先読み前」の手の価値は「事前分布」に相当し、「先読み後」の価値は「事後分布」に相当するので、先読みを行うたびにベイズ更新していくようなアルゴリズムが作れそうな予感が湧いてくる。

とりあえず探索が終わった後の意思決定について先に考えてしまっておこう。もしそれぞれの手の価値について「真の分布」が得られたとすると、意思決定フェーズとしてどの手を選ぶのが合理的だろうか。２つの分布が連続的でお互いに重なっていなければ、合理的な選択は自明で、より高い価値に分布しているほうの手を選べばよい。しかし分布に重なりがある場合、何らかの効用関数を比較するのが合理的だろう。効用関数をうまく使えば、例えば「劣勢のときは勝負手を放つ」といった意思決定も行えそうである。

では続いて、手を読む順序について検討してみる。まず最初にそれぞれの手について事前分布を求める必要があるが、どのようにしたらよいだろう。これにはそもそも「局面の有利不利（評価関数）」が一点ではなく分布になっている必要がある。そうなっていれば、手の価値の事前分布は上述と同様に「その手を指した直後の局面の有利不利」とすればよいだろう。では事後分布、すなわち先読みによるミニマックス法の計算に相当する部分についてはどのようにしたらよいだろう。これは一般の分布を相手にしているととても大変なので、やはりベイズ更新の定石どおり「共役分布のあるやつを使ってパラメータだけをベイズ更新」するのがよいだろう。ここでふさわしい分布はベータ分布だと思われる。手の価値を「その手をさしたらA勝B敗」という風に表現するならそれはA,Bをパラメータとするベータ分布がピッタリである。ではベータ分布のベイズ更新を使って「ミニマックス法に相当する計算」を行うにはどうすればよいだろうか。もっときちんと問題を定式化すると、「それぞれの手の価値がベータ分布として与えられているときに、価値の最大値の分布はどうなるか」というものだ。これは純粋に数学的な問題なので、じっくりと検討して後日また記事を書くことにしよう。解析的に導出できるのか、もしくはサンプリング法を使うことになるのか、楽しみである。

また、ここでもう一つ大きな検討課題がある。通常の決定論的なミニマックス法では、アルファベータ枝刈りという劇的に計算量を減らせる（元の計算量の√になる）「計算のショートカット」があって、ほぼ全ての思考ルーチンでこのアルファベータ枝刈りが使われているのだが、ベイズ統計的なゲーム木探索ではこのアルファベータ枝刈りがそのままでは使えない。なので、ベイズ統計的なゲーム木探索において、アルファベータ枝刈りに相当する「計算のショートカット」を見出しておかないと、決定論的なアルゴリズムに全く伍し得ない可能性がある。これについても、同時に検討を進めることにしようと思う。

さて、以上、本記事ではベイズ統計を用いたゲーム木探索について検討し、ベータ分布の集合に関する数学的な問題に帰着するところまで議論を進めた。さらに検討を進め、近いうちにまた続きを書きたいと思う。

*1:「その手を指す確率」を厳密な確率測度として構成するのは難しいが、「手の価値についての確率分布」は確率そのものなので、より深い理論展開が期待できる。