前回の記事「ミニマックス法とは何か? 1:コンピュータ将棋の基本戦略」では、ミニマックス法の戦略について解説しました。今回は、ミニマックス法における枝刈りについて解説します。
枝刈りには大きく分けて2つの種類があります。「前向き枝刈り」と「後ろ向き枝刈り」です。
「前向き枝刈り」とは、探索を行わずに何かしらの人為的な基準によって枝刈りを行うことです。探索に“先入観”を取り入れることになりますので、上手くいくかどうかはやり方に依ってきます。
「後ろ向き枝刈り」とは、探索時の情報を活用することでミニマックス法の結果ができるだけ変わらないように行われる枝刈りのことです。副題の「アルファベータ枝刈り」(アルファベータ法とも言う)が代表例であり、これはミニマックス法の結果を確実に再現することができます。後ろ向き枝刈りは基本的にはやった方が得になります。
今回の記事では、主として、後ろ向き枝刈りの最も基本的な手法であるアルファベータ法について解説します。この手法は、コンピュータ将棋の探索技術の基盤となるものです。
まずは、前回のミニマックス法の探索例を再掲します。
この例は、以下の図のように書き換え、「?」部分を任意の数字に置き換えても、初期局面の評価値や最善手の結果は変わりません。実際に色々と数字を入れて確認してみてください。ただし、探索途中の局面の評価値は変わりうるので、「+700↑」「+200↓」のように範囲で表現しています。ここで、数字末尾の「↑」は「以上」を、「↓」は「以下」を表しています。
このことは、言い換えると、「?」部分は実は探索する必要がなかったということを意味しています。必ずしも全局面を探索しなくても、正確な初期局面の評価値や最善手を得ることができるというわけです。
それでは、実際にどのように探索をすれば無駄を減らすことができるのでしょうか?
探索量を減らすという事は、その分だけ情報量を減らすということを意味していますので、上の例で途中の評価値を確定値から範囲値に変えたように、情報量削減の工夫が必要になってきます。
探索の際に下限と上限の範囲を決めることで情報量を減らし、探索の無駄を省く手法のことをアルファベータ法と言います。名前は、下限値をα、上限値をβと書いたことに由来しており、現在でも探索の下限値と上限値は慣習的にαとβで書き表されます。
実際にやってみましょう。
上の図でそれぞれの局面の左下に書いてあるのが探索範囲です。初期局面の探索範囲は負の無限から正の無限までの全ての範囲にしてあります(※図中の「INF」は無限の意味)。初期局面からスタートして、局面を展開し、上から下へと順番に探索していきます。探索範囲は、探索で得られた情報を用いて、随時更新されていきます。
まず、一番上に位置している4つの局面は、まだ何も情報がありませんので、初期局面の探索範囲のままです。右上の末端で「+500」という値が得られます。この分岐では最大値を探しているので、2番目の末端局面の探索範囲の下限が「+500」に更新されます。2番目の末端局面の値は「-200」であり、下限以下ですので、これは無視されて、最終更新値である「+500」が一つ前の局面の評価値として返されます。
一つ前の局面の分岐においては、最小値を探しているので、ここでは探索範囲の上限が更新されます。結果、探索の上限は「+500」となるのですが、3番目の末端局面の値は「+700」であるため、これで下限値を更新すると、それ以降の探索範囲は「+700」以上「+500」以下となって探索範囲が消失します。探索範囲が消失するということは、それ以降は探索しなくてもよいということです。
以下同様の操作で、無駄な探索を省いて正確な結果を得ることができます。この手順はプログラムで書くと簡単なのですが、人間が理解しようとすると中々に大変です。アルファベータ法の筆算方法の詳細については「アルファベータ法の筆算:これであなたもコンピュータ!?」の記事にまとめました。
さて、ここで注意しなければならないのは、上記の手法に際して、「上から下へ」という探索の順序を指定していたことです。前の記事で全局面を探索していた時には探索順序は関係ありませんでした。
実は、アルファベータ法の場合には探索順序が重要であり、探索順序によって省略できる探索量が変わってきます。例えば、上の例では末端の8局面の内の3局面の省略に成功していますが、記事冒頭の図に戻って、順序を「下から上へ」と逆にしてアルファベータ法をやってみると、ただの1局面も省略できないことが分かります。種を明かすと、上の例は「上から下へ」と探索した時に最も効率がよくなるような順序(各分岐で最善手を最初に探索)になっていたのです。
それでは、実際に探索順序によって探索量はどれくらい変わってくるのでしょうか?
分岐数を3に固定した時の探索局面数を以下に示します。横軸は探索の深さdです。青点が最善順序の時の結果(評価値は各分岐に対して等間隔)、赤点が最善順序の逆順の時の結果、黒点がランダムの時の結果(1000回の平均)になります。縦軸は常用対数ですので、10の何乗であるのかを表しています。
全局面を探索する場合には、3のd乗ですので、赤線になります。最善順序の逆順の場合の結果(赤点)は、これに近くなります。一方で、最善順序の場合の結果(青点)は、\[2 \times 3^{d / 2}\]の線(青線)によく一致しています。この式は、3を分岐数で置き換えると、固定分岐数におけるアルファベータ法の理想値として知られているものです。ランダムの場合の結果(黒点)は両者の中間くらいに位置しています。
つまり、アルファベータ法は、順序が最善ならば、探索量を平方根で減らすことができます。平方根の違いは意外と大きく、例えば、上図で20手のところを見てみると、最善順序なら10万局面程度の探索で済むところが、ランダムならその100倍以上の計算量が必要になり、全局面なら1万倍以上の計算量が必要になります。最善順序なら1秒で済む思考時間が、2分とか、3時間とかになってきてしまうわけです。局面数が増えると、違いはより顕著になります。
アルファベータ法が最もよく機能するのは、各分岐で最善手を最初に探索する場合であり、有望そうな手から順番に探索していくことが大切になります(指し手の順序付けの問題と言う)。一般には、浅い探索の結果を活用したり、別の枝(兄弟ノード)での突出した最善手(「killer move」と言う)を優先して探索したりというような工夫がなされています。
さて、上の例では、初期局面の探索範囲を負の無限から正の無限までの全範囲に設定していたわけですが、最初の段階から探索範囲に制限を加えてしまうことも可能です。ただし、その場合には、下限以下に正解がある場合には下限以下という情報しか得られませんし(「fail low」と言う)、逆に上限以上に正解がある場合には上限以上という情報しか得られません(「fail high」と言う)。設定範囲内に正解があるかどうかという賭けの要素が出てきます。
また、下限値(α)と上限値(β)を利用して、さらに枝刈りを行う手法もあります。例えば、「null move枝刈り」や「futility枝刈り」等が有名です。
「null move枝刈り」というのは、パス(null move)によって相手に手番を渡した時に、それでも上限値以上なら、その局面は上限値以上と決め付けるという手法のことです。将棋の場合には、パスより酷い手しかないという局面(チェス由来のドイツ語でツークツワンクと言う)は滅多にありませんから、非常に高確率で有効な手法です。
「futility枝刈り」というのは、末端まで残り1手の局面で評価値の簡易見積もりが下限値を大きく下回っている/上限値を大きく上回っているのならば、無駄(futility)になる可能性が高いので、その局面の探索を打ち切るという手法のことです。残り数手に拡張されることもあります。
これらの手法は、アルファベータ法とは異なり、確実な結果を保証するものではありませんが、コンピュータ将棋においては有効な運用が可能であることが知られています。
ちなみに、各々の枝刈り手法が「前向き」なのか、「後ろ向き」なのかについては文献によって記述に差があるようです。例えば、「futility枝刈り」は、評価値の簡易見積もりと人為的な基準によって探索を行わずに枝刈りをしているわけですから、厳密には「前向き」だと思われますが、一方で、アルファベータ法の近似手法の一つだと捉えると、「後ろ向き」であるとも解釈が可能です。「前向き」/「後ろ向き」の分類は、数学的な定義の問題というよりは、その手法をどういうものだと位置づけているかという解釈の問題なのかもしれません。
また、「全幅探索」という言葉についても様々に解釈の余地があるようです。本来は「その深さの全ての局面の探索」を意味する言葉ですが、それと同じ結果が得られるアルファベータ法も「全幅探索」に含めることがあります。また、「null move枝刈り」や「futility枝刈り」等も、近似的に同じ結果を得ていると考えて、「全幅探索」に含めることがあります(例えば、Bonanza等)。
この辺のことは定義に拘る人が見ると頭が痛くなるかもしれませんが、急速に発展する分野において言葉の整理が追いつかないというのは、とてもよくあることです。言葉を整理するのは、全てが終わった後に学問としてまとめる学者の仕事なのです。
最後に、ハードウエアに関することを少し補足しておきます。
上記の例では、1つのスレッド(一連の命令の流れ)で処理することが暗黙の前提になっていました。しかしながら、最近のCPUはマルチコアが基本になっています。例えば、第1期電王戦に使用されるIntel Core i7-6700Kであれば、4つの物理コアを有しており、一度に4つのスレッドを処理することが可能です。さらに、ハイパースレッディング(HT)技術を用いると、4つの物理コアを8つの仮想コア(論理コアとも言う)に分けて利用することもでき、同時に8つのスレッドを処理することも可能になります。ただし、その場合には、1スレッドの性能は0.65倍程度に落ちてしまうようです(参照:「30分でBonanzaの評価関数の要点を話します!」)。また、1台のPCに限らず、多数のPCをつなげてクラスタとして使用する場合には、もっと大量のスレッドを同時に処理することになります。
上述のアルファベータ法等の枝刈りは、探索時に得た情報を随時的に活用していました。これをマルチスレッドでどのように処理すればいいのかというのは技術的に簡単な話ではありません(並列化の問題と言う)。スレッド数が倍になっても自動的に探索速度が倍になるわけではないということです(※一説には、実効的な探索速度はスレッド数の平方根以上程度と言われています)。この問題については、ここではこれ以上は深入りしません。
以上、今回はミニマックス法における枝刈りについて解説しました。ここで記したのは、本当に基礎的な部分ですが、コンピュータがどのように“考えている”のかを知るための一つのきっかけとなってくれれば幸いです。
コメント