αβ 法

αβ 法とは何か

αβ 法は、将棋やチェスのように2人が交互に手を指すゲームで、先の局面を読んで最善手を決めるときの探索の手順です。αβ 枝刈り(alpha-beta pruning)とも呼ばれます。求める答えは Mini-Max 法と同じで、違うのは調べる局面の数です。答えに影響しないと確定した枝を途中で調べるのをやめることで、同じ答えにより少ない計算でたどり着きます。

ドナルド・E・クヌース(Donald E. Knuth)とロナルド・W・ムーア(Ronald W. Moore)は、1975年の論文「An Analysis of Alpha-Beta Pruning」(Artificial Intelligence 第6巻)でこの手順を分析しました。この論文は、すべての局面を調べる手続き、片側だけで枝を切る手続き、両側で枝を切る手続きの3つを順に示し、同じ木で調べる局面の数を比べています。以下の説明と数値例は、この論文の内容に沿っています。

前提になるミニマックスの考え方

先読みの様子は、今の局面を根に置き、指し手ごとに枝分かれさせた木で表します。これ以上読まない終端の局面を終端と呼び、終端には自分から見た有利さを表す数値である評価値を付けます。

ミニマックスの考え方では、相手も最善を尽くすと仮定して、終端から根へ向かって値を決めていきます。自分の手番の局面では、子の局面の値のうち最も大きいものを採ります。相手の手番の局面では、相手は自分の点を下げたいので、子の局面の値のうち最も小さいものを採ります。局面 p の値を F(p)、p から指せる手で進んだ局面を p1 から pd とすると、次のように書けます。

p が終端のとき F(p) = 評価値

自分の手番のとき F(p) = max( F(p1), F(p2), ..., F(pd) )

相手の手番のとき F(p) = min( F(p1), F(p2), ..., F(pd) )

この式をそのまま計算する手続きは、すべての終端の評価値を調べます。候補手が d 個ずつで n 手先まで読むと、終端は d^n 個になり、読む深さを1手増やすたびに d 倍に増えます。

αとβの2つの境界値で枝を切る仕組み

αβ 法は、探索の途中で2つの境界値を持ち歩きます。αは、自分つまり値を大きくしたい側が、ここまでの探索ですでに確保できると分かった値の下限です。自分はαより低い値にしかならない手を選ぶ必要がありません。βは、相手つまり値を小さくしたい側が、ここまでの探索ですでに確保できると分かった値の上限です。相手はβより高い値になる手を許しません。

具体的な場面で考えます。自分の手番で、最初の手Aを調べ終え、相手が最善を尽くしても5点は取れると分かったとします。このときαは5です。次に手Bを調べ始め、相手の1つ目の応手で自分が3点になると分かりました。相手は自分の点が低くなる手を選べるので、手Bの値は3点以下です。手Aの5点を上回ることはないと確定したので、手Bに対する相手の残りの応手は調べなくても答えは変わりません。ここで打ち切るのが枝刈りです。相手の手番で同じことを逆向きに行うのがβによる枝刈りです。

クヌースとムーアの論文は、この考え方を2段階で示しています。F1 は、すでに分かっている値より良くなり得ない手を調べない手続きで、片側の境界だけを使います。論文はこれを分枝限定法(branch-and-bound)の技術として説明しています。F2 は、αとβの2つの境界値を引数として受け取り、F2(p, α, β) の形で呼び出す手続きです。両側の境界で枝を切るこの F2 が、完全なαβ 法にあたります。

81通りの終端局面で見る計算例

論文は、どの局面でも候補手が3つあり、4手先まで読む木を例に使っています。終端の数は 3 × 3 × 3 × 3 = 3^4 = 81 個です。同じ木の同じ評価値に3つの手続きを当てると、調べる終端の数は次のように変わります。

すべての局面を調べる手続き F では、81個の終端をすべて評価します。

片側の境界だけで枝を切る F1 では、81個のうち36個の終端を評価すれば済みます。省けたのは 81 - 36 = 45 個で、評価する数は 36 ÷ 81 ≒ 0.44、つまり全部を調べる場合の約44%です。

αとβの両方で枝を切る F2 では、F1 よりさらに少ない終端しか評価しません。

3つの手続きが根の局面に付ける値は同じです。枝刈りは答えを変えず、答えを出すまでに評価する終端の数だけを減らします。なお、36個という数はこの木とこの評価値の組み合わせで数えたものです。評価値の並びが違う木では、省ける数も変わります。

調べる順番で省ける量が変わる

枝刈りが起きるのは、すでに確保した値と比べて、調べている手が及ばないと分かったときです。そのため、良い手を先に調べてαやβが早い段階で厳しい値になるほど、後から調べる手の多くを途中で打ち切れます。反対に、悪い手から順に調べると、新しく調べる手のたびに確保した値が更新されるので打ち切りが起きにくくなり、最悪の場合は Mini-Max 法と同じ数の終端を評価します。

また、αβ 法が減らすのは計算量だけです。選ぶ手の良し悪しは、Mini-Max 法と同じく、評価値の付け方と読む深さで決まります。αβ 法で浮いた計算時間はより深く読むことに回せるので、同じ時間でより先の局面まで読めます。