αβ法
概念とその効果
この探索法は、Minimax法において絶対に採用されることの無い手を見つけ出し、 そのことが分かったらそこから先読みしないようにするアルゴリズムです。
たとえば自分の手番で、ある手Aを指したときの評価値がαだったとします。
そしてそれとは別の手Bを指したときの評価値がαより小さかった場合、
Minimax法の動きから、自分としてはAを選択するはずです。
したがって、Bの評価値がどんなに良くてもαより大きくならないことが分かった時点で、
Bの探索を終了します。
また逆に相手の手番で、ある手Cを指したときの評価値がβだったとします。
そしてそれとは別の手Dを指したときの評価値がβより大きかった場合、
Minimax法の動きから、相手としてはCを選択するはずです。
したがって、Dの評価値がどんなに良くてもβより小さくならないことが分かった時点で、
Dの探索を終了します。
これをまとめると、「自分の手番のときは、 ある指し手の評価がαを上回らないと分かった時点でその指し手の探索を終了する。 相手の手番のときは、 ある指し手の評価がβを下回らないと分かった時点でその指し手の探索を終了する。」 となります。これはつまり、 指し手の評価nがα<n<βの範囲から外れたら探索を終了するということを意味し、 そこからαβ法という名前がつけられています。
αβ法はMinimax法を改良したアルゴリズムで、 得られる評価値はMinimax法と全く同じになることが保障されており、 Minimax法よりもずっと早く探索が終わります。 αβ法はMinimax法のコードを少し変更するだけなので、 Minimax法を使う位ならαβ法を使うべきです。
動きの例
Minimax法で使用した例を使って説明します。 ルートの評価値が-2に決まったところまではMinimax法と同じです。 この時点で、ルートの評価値は-2を下回ることはなくなりました。 そのためα=-2とし、以後の手を探索していきます。
| 自分の手番(α=-2) | -2 | ||||||||||||||||
 |
 |
 |
|||||||||||||||
| 相手の手番 | -2 | ？ | ？ | ||||||||||||||
|
|
|
|||||||||||||||
| 自分の手番 | 5 | -2 | -1 | ||||||||||||||
さて、葉の局面で評価値が-5となって、その一手前の評価値が-5となったところまで飛ばします(笑)。 この局面のさらに一手前においてα=-2でしたので、この局面もα=-2となります。
| 自分の手番(α=-2) | -2 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番(α=-2) | -2 | -5 | ？ | ||||||||||||||
|
|
|
|
|
|
||||||||||||
| 自分の手番 | 5 | -2 | -1 | 1 | -5 | ？ | |||||||||||
すると、この局面の評価は既に-5より良くなることは無いので、 この局面はこれ以上探索する必要が無いことが分かります。 なので、探索を止めて一手戻します。
| 自分の手番(α=-2) | -2 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | -5 | ？ | ||||||||||||||
|
|
|
|
|
|
||||||||||||
| 自分の手番 | 5 | -2 | -1 | 1 | -5 | ？ | |||||||||||
残りの着手も探索した結果はこのようになります。
| 自分の手番(α=4) | 4 | ||||||||||||||||
|
|
|
|||||||||||||||
| 相手の手番 | -2 | -5 | 4 | ||||||||||||||
|
|
|
|
|
|
|
|
|
|||||||||
| 自分の手番 | 5 | -2 | -1 | 1 | -5 | ？ | 5 | 8 | 4 | ||||||||
この例では結局１つしか枝刈りされませんでしたが、 探索の順番によってはもっと枝刈りが発生します。 また、この例ではα刈りしか行われませんでしたが、 深く探索するとβ刈りも発生します。
