はじめに
kaggleコンペ「FIDE & Google Efficient Chess AI Challenge」(通称:チェスコンペ)に参加しているときに勉強したことをまとめるという意味も兼ねてこの記事を書くことにしました。
チェスソフトStockfishのコードとchess programmingという解説サイトで勉強した事であることはご了承ください。
出来るだけ一般論を話そうとしているので、恐らく別のボードゲームなどでも参考にできることが多いのではないかとは思います。
この記事では、αβ探索で用いられる「α値」と「β値」を直観的に理解し、αβ探索で用いられる枝刈り(αカットやβカット)だけでなく、α値やβ値を用いた大胆な枝刈りについても直観的に理解することを目的とします。
チェスソフトにおける探索を全て解説することが目的ではないことに注意です。この記事では解説しない様々な工夫が存在します。
また、実装上はミニマックス法ではなくてネガマックス法の方が簡単ですが、ネガマックス法による考え方は紹介しません。
ミニマックス探索とは
2人の人が交互に手を指すようなボードゲームにおいて良い指し手を探索するためにはどのようにしたら良いのでしょうか？？
全ての手を列挙することができれば当然可能ですが、現時点のコンピューターの計算能力では現実的な時間ですべての手を列挙することは不可能です。
そこで、ある程度の深さまでは探索をしますが、ある深さまで探索をしたらその局面で探索を打ち切り、探索を打ち切ることに決めた局面が「先手にとって」どれぐらい良いのかを表す値、評価値を求めることで妥協することにしましょう。
評価値の値が大きければ大きいほど先手が有利で小さければ小さいほど後手が有利です。
このような状況で、どのようにすれば手番の人にとって最善手を指すことができるでしょうか？？
分かりやすさのために現在の局面の手番が先手にある場合を考えてみます。(手番が後手にある場合も同じように考えられます。)
先手にとって最善手を探す場合に、後手が忖度してくれると思って最善手を探索するべきではありません。
先手と後手がともに最善手を目指すという状況を考えましょう。
先手は出来るだけ評価値が高い局面を目指し、後手は出来るだけ評価値が低い局面を目指すという戦略を取ります。
先手と後手がともに最善手を指した場合にたどり着く局面の評価値を、深さが深いノードから順に再帰的に割り当てていくということをします。ノード$i$におけるこの値を$v_i$とします。
一番深いノードにおける$v_{\cdot}$は分かっているので良いです。(一番深いノードでは探索を行わずに評価値を求めるだけだから)
深さ$d+1$における$v_{\cdot}$は分かっているが、深さ$d$における$v_{\cdot}$は分かっていない状況を考えましょう。
とりあえず、$d=2k$($k$は非負整数)の場合を考えましょう。
このときは、深さ$d$のノードから深さ$d+1$のノードへ移る時に先手が出来るだけ評価値が高い局面に行くように手を指します。
つまり、深さ$d$のノード$i$の子ノードを$j_1, \cdots, j_m$としたとき、
v_i=\max(v_{j_1}, \cdots, v_{j_m})
と定めればよいです。
$d=2k+1$($k$は非負整数)の場合を考えましょう。
このときは、深さ$d$のノードから深さ$d+1$のノードへ移る時に後手が出来るだけ評価値が低い局面に行くように手を指します。
つまり、深さ$d$のノード$i$の子ノードを$j_1, \cdots, j_m$としたとき、
v_i=\min(v_{j_1}, \cdots, v_{j_m})
と定めればよいです。
つまり、下図のように再帰的にmaxやminを取ることによって、先手と後手がともに最善手を指した場合にたどり着く局面の評価値を求めることができます。このように、minとmaxを交互に用いることから、ミニマックス探索という名前が付いています。
次に、深さ$0$のノードにおける指し手をどうやって決めるかを説明します。
深さ$0$のノードの子ノードを$j_1, \cdots, j_m$としたときに、$v_{j_1}, \cdots, v_{j_m}$の最大値を達成するような$j_i$に対して、ノード$j_i$へ移るための指し手を指せばよいです。
なぜなら、先手と後手がともに最善手を指した場合にはこの手が一番評価値の高い局面へ行くことができるからです。
ミニマックス探索は再帰関数を用いて実装することができ、深さ優先探索によって$v_{\cdot}$は求められます。
αβ探索とは
αβ探索とは、ミニマックス法にαカット、βカットと呼ばれる枝刈りを入れることによって高速化を行った探索アルゴリズムです。
αカットとβカットはやっても絶対に損をしない枝刈りであり、これによってミニマックス法から計算量を落としつつも全く精度を落とさないことが可能です。
恐らく最初に直観的な話をしても伝わらないと思うので、まずは数式を使った説明をします。
分かりやすさのために、現在の局面が先手番の場合を考えます。(後手番の場合は同じように考えられます。)
とりあえず、深さ優先探索で深さ$d=2k$($k$は非負整数)のノード$i$に対して$v_i$を求めている途中だとしましょう。
より細かい状況設定をします。
ノード$i$の兄弟ノードで既に$v_{\cdot}$を求められているノードをノード$j_1, \cdots, j_m$とします。
また、ノード$i$の子ノードで既に$v_{\cdot}$を求められているノードを$k_1, \cdots, k_n$とします。
このとき、$\alpha$値を
\alpha = \max(v_{k_1}, \cdots, v_{k_n})
によって定めます。もし$n=0$であれば$\alpha=-\infty$とします。
また、$\beta$値を
\beta = \min(v_{j_1}, \cdots, v_{j_m})
によって定めます。もし$m=0$であれば$\beta=\infty$とします。
(深さ$d=2k+1$($k$は非負整数)の場合でもmaxを取る方がα値でminを取る方がβ値であることに注意してください。深さ$d=2k+1$($k$は非負整数)の場合はノード$i$の子ノードに対してminを取っているのがβ値です。)
このとき、もし$\alpha\ge \beta$ならこれ以上ノード$i$を探索する必要は無く枝刈りを行うことができます。(これをαカットと呼びます。)
それは次の理由によって分かります。
$v_i$はノード$i$のすべての子ノードの$v_{\cdot}$の最大値を取ったものなので、$v_i\ge \alpha$であり、$\alpha \ge \beta$でもあるので$v_i \ge \beta$となります。
一方、ノード$i$の親ノードにおける$v_{\cdot}$の値はその子ノードにおける$v_{\cdot}$の最小値を取ったものであるから、既に$\beta$以下となることが分かっており、$v_i\ge \beta$なので$v_i$はノード$i$の親ノードにおける$v_{\cdot}$の値を更新することはありません。
$d=2k$($k$は非負整数)の場合には$\alpha$カットが生じますが、$d=2k+1$($k$は非負整数)の場合にも$\alpha \ge \beta$となったら同様に枝刈りを行うことができます。(これをβカットと呼びます。)
この2つの枝刈り、αカットとβカットをミニマックス探索に取り入れたのがαβ探索です。
α値とβ値を直観的に理解する
α値とβ値を先程定義し、数式的に考えると$\alpha\ge \beta$が起きた際には枝刈りを行うことができるということが分かりました。
それでは、α値とβ値を直観的に考えるとどのように考えられるのでしょうか？
先程と同様に、現在の局面が先手番とします。
とりあえず、現在の探索中のノードの深さを$d=2k$($k$は非負整数)としましょう。
探索しているノードの深さを固定して考えると、α値は探索を進めていくにつれて単調増加していきます。(α値はmaxをとるため)
そして、子ノードで$v_{\cdot}$が大きいノードを見つけることができれば、α値の大きさは大きくなります。
次に、現在の探索中のノードの深さを$d=2k+1$($k$は非負整数)としましょう。
探索しているノードの深さを固定して考えると、β値は探索を進めていくにつれて単調減少していきます。(β値はminをとるため)
そして、子ノードで$v_{\cdot}$が小さいノードを見つけることができれば、β値の大きさは小さくなります。
以上の観察から、α値はどれぐらい先手が良い手を見つけることができたのかを表し、β値はどれぐらい後手が良い手を見つけることができたのかを表しているという直観を得ることができます。
α値が大きければ大きいほど先手が良い手を見つけることができていますし、β値が小さければ小さいほど後手が良い手を見つけることができています。
それでは、αカットが生じているのはどのような状況でしょうか？
αカットが生じているのは、先手が良い手を見つけてしまったため、後手が前に指していた手が悪手であることが判明し、後手は違う手を考えた方が良いということが分かった場合です。
同じように考えると、βカットが生じるのは後手が良い手を見つけてしまったため、先手が前に指していた手が悪手であることが判明し、先手が違う手を考えた方が良いという事が分かった場合です。
このようにして、αカットとβカットを直観的に捉えることができました。
α値とβ値に対するこのような直観は非常に重要で、より大胆な他の枝刈りを理解するうえでも非常に役に立ちます。
α値やβ値を用いた他の枝刈りの例
せっかくα値とβ値の直観的な意味合いについて説明をしたので、他のα値とβ値を用いた枝刈りを少しだけ例に挙げてみたいと思います。
aspiration window
先程はα値の初期値は$-\infty$、β値の初期値は$\infty$と説明していましたが、aspiration windowではβ-αの値が小さい状態からスタートして、何度も探索を行って徐々に値を大きくしていきます。
これによって最初はたくさん枝刈りをされて探索されますが、徐々に枝刈りを減らしていくことになります。
β-αの値が小さい状態からスタートすることは、先手も後手もある程度良い手を見つけるだろうという発想だと直感的に理解できます。
また、手番が先手の局面でaspiration windowを適用して探索した結果得られた$v_{\cdot}$の値が$\alpha$の値を下回ってしまうとlow fail、$\beta$を上回ってしまったらhigh failと呼びます。(手番が後手の場合も似たように定義できます)
low failの場合は先手と後手がともにある程度良い手(良い局面にできる手)を指せると想定して探索したけど、結局先手はそこまで良い手を指せなかったということで、$\alpha$や$\beta$の値を設定し直して探索をし直すことになります。
high failの場合も、後手がそこまで良い手を指せなかったということで$\alpha$や$\beta$の値を設定し直して探索をし直すことになります。
move picker
ちょっと枝刈りの話ではないですが、move pickerというものがあります。
move pickerとは、子ノードの探索順を決めるものです。
move pickerによってより有望な子ノードを探索する事ができればその手が先手の手であればα値が上がりやすく、後手の手であればβ値が下がりやすくなります。
このようにして、αカットやβカットが引き起こされやすくなります。
これは分かりやすい話なのではないでしょうか。
ちなみに、move pickerの方式として、historyを使ったものというのが結構使われることが多いです。
例えば、相手がOOを指した後は自分がOOという手を指すと良い手になりやすい、という統計情報を用います。
αカットやβカットを生じさせた手は良い手だったとしてその手にボーナス点を付けたりします。
相手に相手の手が悪手だったと分からせる手がαカットやβカットなので、自分の手は相手の悪手をとがめるような良い手だったと考えられるわけですね。
null move pruning
null move pruningを適用する条件をきちんと説明しようとしたらこの記事ではまだ説明していない条件を色々説明する必要があります。
なので、大雑把にエッセンスだけを伝えることにします。現在探索中のノードから先手が指す場合について説明します。
null move pruningとは、自分が一手パスをして探索を行った結果$v_{\cdot}$が$\beta$以上だったら枝刈りができるというものです。
多くの局面において一手パスよりも悪い手は無いだろうという仮説から、一手パスでさえ$\beta$以上になったのだから一手パスよりもマシな手を指した場合も$\beta$以上になるであろうと考える大胆な枝刈りです。
futility pruning
futility pruningに関しても適用する条件をきちんと説明しようとしたらこの記事ではまだ説明していない条件を色々説明する必要があるので、エッセンスだけを伝えることにします。
現在探索中のノードから先手が指す場合について説明します。
futility pruningとは、現在の局面の評価値(ここも厳密な話をしようとするとtransposition tableの話をしないといけないので大雑把です)が$\beta$よりも十分大きいのであれば、数手を指すぐらいではそこまで変わらないだろうから、探索した結果も$\beta$以上だろうという大胆な枝刈りです。
まとめ
ミニマックス探索、αβ探索について説明し、さらにαβ探索に更に枝刈りを入れるような話の例を挙げました。
Stockfishの探索部の話をするのであれば本当は反復深化の事やPVノード探索とNonPVノード探索の話などもするべきだったかもしれません…
ですが、Stockfishの探索部のコードを読むうえで最初に一番難しいのはα値とβ値に対する感覚だと思い、この記事を作成しました。
もし参考になる方がいらっしゃれば幸いです。
(現在の局面がどのような局面なのかをどうやって分類しているのかもかなり勉強になりました。興味があればコードを参照してみると良いかもしれません。コードで残りどれぐらいの深さ探索する必要があるかがdepth、今までにどれぐらいの深さ探索したのかがplyと呼ばれるようです…plyに関しては最初はちょっと戸惑ったので一応注意しておきます…)