αβ法とは

αβ法は、Mini-Max法の探索を速くするための工夫です。Mini-Max法は、先読みする手数が増えると、調べる局面の数が爆発的に増えます。αβ法は、調べても最終的な判断が変わらないと分かった枝を、途中で探索から外します。これを枝刈りと呼びます。

枝刈りの例

自分の手番で、候補手が2つあるとします。1つ目の手を調べたところ、相手がどう応じても評価値5は確保できると分かりました。次に2つ目の手を調べると、相手の最初の応手で評価値が2になりました。相手は自分にとって最も不利な手を選ぶので、2つ目の手の価値は2以下に決まります。この時点で、2つ目の手は1つ目の手より劣ることが確定します。そのため、2つ目の手に対する相手の残りの応手は、調べる必要がありません。

αとβ

探索中は2つの値を持ち歩きます。αは、自分の側がすでに確保できている評価値の下限です。βは、相手の側がそれ以上は許さない評価値の上限です。調べている局面でαがβ以上になったら、その先は結果に影響しないので打ち切ります。

結果は変わらない

αβ法が省くのは、結論に影響しないと確定した枝だけです。そのため、選ばれる手と評価値はMini-Max法とまったく同じです。精度を犠牲にして速くする近似とは違います。

どれだけ省けるかは、手を調べる順番で変わります。有望な手から先に調べると枝刈りが多く起こります。理想的な順番なら、同じ時間でおよそ2倍の深さまで読めます。1975年には、ドナルド・クヌースとロナルド・ムーアがこの性質を詳しく解析した論文を発表しました。

覚え方

「結果は同じで、手間だけ減る」がαβ法の要点です。