MTD(f)実装中
実装中というか、水曜日辺りから着手してようやくエラーで落ちずに対局出来る所までは来ました訂正：アサーションを有効にすると落ちまくります。ただ、NPSが100k台から10k強にガタ落ちなんで、まだαβより遅いですが。
とりあえず、実装してみて分かった事をメモがてら書いてみます。
まず、recaptureで延長するのはよろしくないみたいです。
例えば、ルートノードから手順A→B→Cと手順C→B→Aで同じ局面xに到達する場合を考えます。この時、xで手Dを指すとAで動いた駒を取り返す（Cの駒は取り返さない）とします。そうすると、置換表に格納される局面xの評価値の上界・下界は延長する場合としない場合の値が混在します。で、結果的に下界が上界を上回るとかっていう異常な状態になり、探索結果がおかしくなります。
一応これの対策は考えてあって、局面のハッシュ値に直前の指し手の情報を含める*1と大丈夫だと思います。ただ、そうすると直前の指し手が異なる局面を別物扱いするので、探索ノード数は増えるはずです。結局、recaptureを延長するメリットと探索ノード数の増加っていうデメリットのどちらが大きいのか分からないので、私はrecapture延長は無しにしました。（本当はちゃんとデータとって決めるべきなんですが、実装が楽な方を取りました。）
それと、ハッシュムーブもあまりよろしくないらしいです。
理由は以前書いたHistory Heuristicと同じで、ハッシュに最善手として登録されているか否かによってLMRで探索短縮する・しないが変わってきて、結果的に探索値の矛盾が起きる様です。
と言う訳で、ハッシュムーブに関してはLMRで短縮しない、ルートから一定深さでだけ使用する事にしました。
…たった3日でこれだけ問題が出るんだから、MTD(f)がちゃんと動くのは何時になるんでしょうね。他にもやるべき事があるので、先行き心配です。次回選手権まで残り35週間、ヤバ気な感じ。
