クラスタの手帖
一昨日のエントリは見ようによっては不思議なことが書いてあると思われる人もいるかもしれない
置換表のエントリの正当性と、並列探索（に関するNB0AMG法）における辞書の正当性とが別物の法則によって支配される、というくだりのことだる
その人はこう考えるに違いない：
置換表と並列探索の辞書の違いは窓がクリーンかダーティーかの違いだけ。一方、探索木とその葉における評価値を指定したらプレイヤーA,B双方の最適戦略の組み合わせとしての読み筋の集合と、その結果としての評価値が一意に定まる。つまり木と評価関数を指定するだけで求める情報（読み筋と評価値*1）は定まっており、置換表または辞書に載るべき正解のどこにもαβウィンドウが関与しないではないか！置換表と並列探索の辞書とで、扱いに違いなんて出ないんｼﾞｬﾈｰﾉ？GMA0BNはしょせん言うこと成すことGMA0BNクォリティーだな！
ところが、教科書的なαβ探索ルーチンではこれ（置換表と並列探索辞書の同一視）は成立しない
αβ探索のルーチンをよーく思い出してみよう：
int SearchOnAlphaSide(int depth, int alpha, int beta) { if (終局) { // 合法手無し return -INFINITE; } else if (depth >= depthMax) { return (局面評価値); } foreach (m in { 指し手 }) { 局面に手mを適用; int v = SearchOnBetaSide(depth + 1, alpha, beta); if (v > alpha) { alpha = v; if (alpha >= beta) break; } } return alpha; } int SearchOnBetaSide(int depth, int alpha, int beta) { ...(省略)... }
この書き方だと、SearchOnAlphaSide()は決してalpha未満の値を返さないし、SearchOnBetaSide()も決してbeta超の値を返さない。
これは、与えられる[alpha, beta)がクリーンな窓*2であれば、そういった範囲外の領域が探索済み故[alpha, beta)という窓が探索ルーチンに入力されたのであって、考慮する必要が無い保証があると言えるのだが、
与えられた[alpha, beta)がダーティーな窓の場合、alpha未満やbeta超の領域はきちんと探索されつくしてはいないかもしれない。
そこにいきなり探索ルーチンが区間[alpha, beta)内のみに答えを絞ってしまうと、探索に漏れが発生するのだ
どう対策するのが最も効率が良いかはノー☆コメント
対策する必要がある人が対策するってことでオール無問題、*3
