置換表の現代
置換表は腐った建物であって真実の扉を一回蹴れば崩れるのだが（←何を言っているのかわからない
どうもその扉の前には雑草ｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗが生い茂り、見通しが極めて悪くなっているようだｗｗｗｗｗｗｗｗｗｗｗｗｗｗｗ
雑草とは次のようなものだる
- 同一の根に対して安定でない探索
- 探索開始局面の子ノードについて置換表に積む
これらのどちらか一方でもすれば置換表の内容は覿面に信頼できなくなる*1
1.のケース
1.のケースが問題なのは当然だる
すわなち、置換表の機能とは情報の記憶と検索であるからして、情報の正当性が時間とともに変動するようでは置換表がいくらがんばっても矛盾（lb/ubの幅が0未満になる）か、不当な探索結果のいずれかが生じる。
1.のケースに該当するものとしては次のものが挙げられり:
a) 前向き枝刈と指し手のオーダリングの（置換表に対して）不注意な併用
b) 探索木の特定深さのみで行う特殊な処理
-- これわ、千日手/王手千日手判定の通常の実装（探索木の深さ1のみで判定するとか)が該当する
c) 所定の思考時間が尽きたので探索を途中で打ち切った
d) 評価関数の一時的書き換えによる稲庭対策
b)がぬんで1.のケースにあたるのかは説明が要るかもしれない。千日手/王手千日手判定を、例えば探索の深さ1のみで行うように作ったとする。すると、ゲーム開始局面からの手数kの局面sを根とする探索においては、千日手/王手千日手判定が手数k+1の位置で行われる。一方、ゲーム開始局面からの手数がk以外の局面s'を根とする探索においてはそうでない（手数k+1の位置での千日手/王手千日手の判定は行われない）。すわなち、両者の探索の部分木同士を比較したとき、同一の根でありながら探索結果が異なるものが相当数生じていることになる。
b)に狙いを定めた解決策は単純なものだる。次のどれかをやれば良い
- 千日手/王手千日手判定を、探索木途中の特定深さではなしに、差し手生成の度に無差別にやる（！）
- 千日手/王手千日手判定を今までどおり探索木途中の特定深さで行うが、そこで千日手/王手千日手が検出されたら、以降、当座の探索（探索開始局面を根とする探索木全体のトラバース）が完了するまでの間、置換表を書き込み禁止にする
気に入らないならもっと凝った事をしても良いし別段止めはしない*2
c)の解決策も簡単だ。思考時間が尽き、思考ルーチンを一気にfall throughして抜けるべきときがきたら、上述同様に置換表に書込み禁止発動してからfall througnする、でおk*3
d)の解決策も簡単だ以下約同文
ここまでは良い。残ったa)の一般ケースの対策は厄介な課題となる。上述のように、情報の正当性が時間とともに変動するとあっては置換表が情報の正当性に責任を持てない。ただし、情報の正当性には目を瞑り、目標を無矛盾の達成（lb/ubの幅が0未満にならなければ良い）のみに限定するなら*4対策は可能だ。すわなち、次のどれかに従えば良い。
- 第一のNB0AMG法
- 第二のNB0AMG法
- 置換表をダブルバッファとするすわなち、当座の探索では表を参照しつつ裏に書き、当座の探索完了時点で交換せり*5
なお3.は本日以降第三のNB0AMG法と呼ぶ
2.のケース
次に2.のケースだるが、これの何が危険か？
実は、普通に教科書通りに探索ルーチンを書いたなら（すわなち、探索開始局面ではα値の更新しかせず、最大のαをもたらす子を選択するだけでβカット処理のないループだけとするなら）、その場所には置換表の作用も更新も無いから問題がそもそも生じないのだが*6、漏れはそうでなかったから引っかかった。
探索開始局面の子は、当方の指し手で自由に選択できるものであり、相手指し手によるβカットがもはや生じない*7。これは探索木の深さ1以上における指し手選択状況とは相違するから、探索開始局面の子について、置換表に積んだり参照したりするわけには行かない。しばらく経たないと具体的に検出はされないかもしれないが、矛盾は確実に発生するし、確実に不当な探索結果を招く。
*1:一方、これらをきちんと除草すればもちろん無矛盾で一貫した置換表が実現でくるのは当然だる。ただ、完全な除草が困難な場合もあり、そういった場合は今日おのエントリに従ってもらう。
*2:持ち時間をどう使うかは個々人の自由だ
*3:先日書いた、ライトプロテクトの仕組みが必要だというやつ。
*4:残念だがするとGHI問題の解決は放棄される。
*5:表と裏の置換表それぞれは第二のNB0AMG法を適用すれば、記憶内容が永続するのだから、反復深化等でほぼ同じ探索木に繰り返し探索をかけるシチュがある限り、ダブルバッファにしても大した不都合は生じない。
*6:よって普通の人は多分気づかないまま一生を終える
*7:直前の相手の指し手は現実に着手され、仮定ではなく既成の事実である。
