MTD(f)にリトライしてみようかな
ABC探索は難しいんで、以前やった事のあるMTD(f)にも一度手を出そうかと考えています。
んで、とりあえず論文（http://people.csail.mit.edu/plaat/mtdf.html）読みつつ実装案を検討中。
MTD(f)は*1は結構デリケートな感じなんで、色々注意しないと危険ですね。
前にハマったのは、置換表の評価値を流用する際に、「現在の残り深さ＜前回探索時の（置換表の）残り深さ」になっているとおかしな事になる*2ってケースがありました。どうも、置換表の値を流用する場合は「仮に現在の状態で探索を続行した場合と、置換表の値を流用する場合で、厳密に結果が同じにならないといけない」って制約があるみたいです。
後、GA将!!!!!!ではムーブオーダリングはハッシュの手＋History Heuristicで、探索の短縮にLMRを使ってるんですが、これもこのままだとまずいかもしれません。
多分ですが、
- n回目のnull-window searchとn+1回目のnull-window searchでムーブオーダリングの順序が入れ替わる。
- その影響で、短縮される（あるいはされない）手が変化する。
- 短縮の変化の影響で手の評価値が変化する。
- 最終的に、Fail-HighするはずがFail-Lowする（あるいはその逆の）ケースが出てくる。
って事になるんじゃないかと。
まぁ、これは対策を考えてあって、ムーブオーダリングに使うテーブル（T1）と手のスコアを保存するテーブル（T2）の2つを用意しておいて、反復深化終了時にT2からT1に手のスコアをコピーしてやれば大丈夫かと考えています。これなら、null-window searchを繰り返している間は常に同じ順序でムーブオーダリングされるので、多分大丈夫、多分…
ちょっとでも探索が速くなってくれればその分学習も速く進む訳で、それなりの出来になるのを期待しています。
…まぁ、実装するのは今週末になるでしょうけど。
