MTD

scout探索アルゴリズムは確かに正しい結果を返しますね。うん。これは子ノードの評価値を場合分けして帰納的に証明できました。
さて、このscoutも効率のいいアルゴリズムだけどいまどきの実戦プログラムでは使われない。今使われてるったらやっぱりMTDですよ。Memory-enhanced Test Driveアルゴリズム。testってのは、前回書いた「幅0のα-β」のこと。memory-enhancedってことは、前回の実行結果を覚えておいて次回以降に生かすタイプのα-βであることです。
さて、この幅0探索をどう使って高速に探索するのか。使うのは2分探索みたいな技法です。目的はある局面の（先読みの結果の）評価値を求めることなんだけど、

1. まず、評価値の予想値fを決める
2. fを原点として幅0探索(test)
3. 実際の評価値がもっと大きければ探索結果はfより大きく、小さければ結果はfより小さい
4. つまり、探索結果はfよりも真の答えに近づいたので、それを新たなfにして2へ戻る

fが動かなくなったら探索終了。ここで、同じ局面に対して何度もα-βをかけることになるので、二度手間三度手間をなくすためにメモりに実行実績を残しておくのが有効になるのです。
では、実行結果の何をどう記憶するか。それはもう少し勉強しないと。transposition tableっていうんだけど。