MinmaxとAlphaBetaの探索ノード数

実際のreversiで、Minmaxに対してAlphaBetaはどの程度、調べるnode数を削減しているのかを調べた。

ルールを守る範囲で無作為に手を打つplayerを相手に、各plyごとに調べた端末node数をプロットしたものが次の図である。

縦軸はnode数で対数軸となっている。ばらつきがかなりあるが、平均をとったものが次の図となる。
＃偶数手の方が奇数手より調べるnode数が少なくなる傾向があるのはどうしてだろう？

plyごとのnode数の変化に関する傾向はMinmaxとAlphaBetaで違いがみられないので、単純に1試合あたりのnode数の平均を調べると次のようになる。

depth      MinMax   AlphaBeta
    2    1569.445     734.205
    3   13429.935    3182.210
    4  116136.220   11957.795
    5 1225244.320   42139.270
    6          NA  182336.385

大雑把にMinmax手法では探索の深さが１増すごとに9倍程度のnodeを調べていることが分かる。それに対して、AlphaBetaでは探索の深さが１増すごとにおよそ4倍程度のnode数の増加となっている。その結果、探索の深さが深くなるにつれてAlphaBetaの探索node数はMinmaxに比べると劇的に小さなものとなる。

各depthにおける探索時間(ms)は次の通り。

depth    MinMax AlphaBeta
    2   123.035    95.960
    3   910.690   311.085
    4  7931.905  1559.270
    5 73328.305  4320.155
    6        NA 22964.395