[Machine Learning] アルファ・ベーター法 （alpha-beta method）

前回の投稿（min-max法）に続いて，アルファ・ベーター法 （αβ method）に関する投稿です．

前回の投稿のmin-max法では，木を全て探索し，末端局面の評価値を求めた上で指手を決定しました．αβ法を用いると木の枝刈りをすることで計算量を減らすことができます．前回の投稿で示した木は以下のようなものでした．

まず，枝刈りができるのはJの評価値を求めるところです．今，Cの評価値が3に決定したとします．Cが決まった後にはDを求めるので，Iの評価値を求めます．その結果は4となりました．この時点でJの評価値の計算は不要になり，枝刈りができます．

枝刈りのできる理由を以下に示します．
Bは後手が指手を選ぶ場面なので，小さな評価値の法を選びます．Cの評価値は3に決まったので，ここで選択される手の評価値が3より大きくなった場合は，Dは選択されません（Cが選択されます）．
ところが，Iの評価値が4になった時点でDの評価値として先手は4以下の評価値を選びません（IとJのどちらかを選ぶのは先手なので，より大きな評価値の指手を選ぶ）．従って，Jが3より小さい値になったとしても，Dの評価値は4になります．また，Jの評価値がIより大きくなった場合はDの評価値として選ばれますが，Cの評価値3よりも大きな値なので，結局Aの評価値としては選ばれず，Cの評価値が選ばれます．よって，Rの評価値を決めるためには，Jの評価値を求める必要が無くなります．

このようなタイプの枝かりをベータ・カット（β cut）と言い，基準となる値をβ値といいます．

上記のベータ・カット（β cut）について再度まとめます．

1. Cの評価値が3（= β）なので，Aの評価値は3以下になる．
2. Iの評価値が4になったので，Dの評価値は4以上になる．
3. 4 > 3（= β）なので，Dは選択されない．
4. Jを枝刈りする．

次にBの評価値を求める場合を見てみます．

今，Rは先手局面なので，AとBの大きな評価値の方を選びます．Aの評価値は3なので，Bが選ばれるには，3より大きな値にならなければなりません．

Bの評価値を求めるためには，まず，Eの評価値を求めます．Eは先手局面なので，KとLの評価値の大きい方を選択します．よって，K = 2 > L = 1なので，Eの評価値としては2（K）が選ばれます．

Eの評価値が2に決まると，Fの評価値の計算は不要になり，枝刈りができます．

枝刈りのできる理由を以下に示します．

EとFは，後手局面なので，評価値の小さな指手を選び，その値がBの評価値になります．従って，局面Bの評価値は2より小さい値にしかなりません．AとBのどちらを選択するかは，先手なので，より大きな評価値の指手を選びます．Aの評価値は3で，Bの評価値は2以下の値にしかならないので，Fの評価値を調べる必要が無くなります．

このようなタイプの枝かりをアルファ・カット（α cut）といい，基準となる値をα値といいます．

上記のアルファ・カット（α cut）について再度まとめます．

1. Aの評価値が3（= α）なので，Rの値は3以上になる．
2. Eの評価値が2なので，Bの評価値は3以下になる．
3. 2 < 3 (= α) なので，Bは選択されない．
4. Fは選択されないので枝刈りをする．

関連する投稿
ミニマックス法（min-max method），アルファベータ法（alpha-beta method），