置換表は反復深化と組み合わせると一層不安定化する…国家も同じだ
何ていうーか、一昨日のエントリは、反復深化の際、置換表を成長するままに放置すると置換表に矛盾が生じることがあるという最終結論には修正の必要は認められないものの、途中の論理が例によって怪しさ炸裂だったorz
1
まず、T'がβカットされないときtが置換表に積まれるとしたのは全くの誤りだる
tを含む部分木T'がβカットされる、という事象には、tがトラバースされる場合と、されない場合がある。
前者は、例えばT'の中で最初にトラバースされる葉ノードがtである場合等。とにかく部分木だろうがなんだろうが、葉ノードが探索木全体の葉ノードの部分集合である木なら、アルファベータ法でβカットされる前に少なくとも1つの葉がトラバースされる。tがそれにあたる可能性はままあり、これがtのように最終的な読み筋から遠く隔たった局面であっても置換表に積まれる真の原因だる
2
もう一つの間違いは、葉ノードであるtが置換表に積まれることがある、と書いたのだけど、例示したコードは葉ノードを決して置換表に積まないので話の辻褄が合わないという、、orz
これは話とコードのどちらが間違いかというと、話の方がまちがっちょる。反復深化前提だとして、深さN=nのときの葉ノードtは、N>nのとき、葉から1手以上内側の内部ノードt'にあたるわけだが、t'の評価値のlowerBoundとupperBound（以下l/bと略す）をtの評価値のl/bで置換したのでは、それはt'を通過する手筋について、深さNまでしか探索していないのと同じになる。このため、葉ノードを置換表に積んでも、より深い探索において葉ノードより上のノードの置換には使えないし、実際、そうした深さ関係のとき使わせないようにプログラムする。故に、置換が葉ノードを葉ノードで置換するパターンばかりになって、探索の実質的延長に全く寄与せず、かつ探索時間短縮の効果も小さいのだ。せいぜいときおり評価関数を計算せずに済む、ぐらいの有難味しか生じない
3（重要）
さらに極めけつの間違いは、置換表に矛盾が生じるのは、トラバース順序が変わるからではないということだる。置換表の矛盾は、今から述べるように、探索延長が主たる原因だった！*1
4
というわけで、一昨日のエントリの説明を書き直すと、次のようになる。
まず深さN=nの探索において、葉ノードtの1手以上内側のノードt_1が置換表に積まれたとし、探索終了時点でのt_1のl/bがそれぞれa,bだったとする。すわなち、閉区間[a, b]内に、深さnで探索したときのt_1の真のミニマックス値があるわけだ。
次に、N>nとして探索を反復することを考える。このとき、元t_1であったノードt_1'は、末端から2手以上内側に居るわけだが、上で述べた探索の実質的延長の観点から、l/bをt_1の[a, b]で置換して良い局面は、t_1'より先のノードに現れたt_1と同じ局面に限られる。
で、そういったノードt_1''が運よく見つかったとしよう。ただちに置換され、l/bは一気に[a, b]にまで縮小する？いやそうなるとは限らない。置換表の動作を思い出しておこう。有り得る場合を全部書くと、次の6通りとなる：
- a＜b＜alpha＜beta -- fail-low; bを返して終了
- a＜alpha≦b＜beta -- [alpha, beta)を[alpha, b)に片側縮小して探索続行
- alpha≦a＜b＜beta -- [alpha, beta)両側を[a, b)に縮小して探索続行
- a＜alpha＜beta≦b -- [alpha, beta)を変えずに探索続行
- alpha≦a＜beta≦b -- [alpha, beta)を[a, beta)に片側縮小して探索続行
- alpha＜beta≦a＜b -- fail-high; aを返して終了
右側にはそれぞれの場合毎の処理を書いた。
上記6通りのうち、1.と6.以外はt_1''の子ノードの列挙に進む。そこである子ノードuがβカットされたとする。これは普通に起きることであり、このとき当然、uから始まる読み筋の末端局面の評価値vはbeta以上だる*2。これは置換表の通常の更新規則によれば、fail-highということで、t_1''のl/bの片側aをa=vに修正すべきものである。ところが、このときbがv以上である保証は実は無い。なぜなら、t_1''の子ノードuの先で、置換表による実質的探索延長等の理由で探索延長が起きることも普通に生じることだが、すると、t_1''を根とする部分探索の読み筋の長さが、u以下を探索する直前の見込みと、u以下の探索した後の実態とで食い違ってしまうからだ。より具体的には、t_1''の子ノードを列挙し始めた時点では、その読み筋の長さ*3は、前世代の探索木（深さn）におけるt_1から末端までの手数と同じ想定であったものが、u以下の探索途中で探索延長されて実質は伸びてしまう。つまり、一昨日の例の式(2)の右辺の一意性は崩れる。
式(2)が、l/b縮小の行き着く先の一意性担保をやめたらあとは焼け野原であって、とりわけ特に2.や3.においては、beta== bとした上でt_1''の子ノード列挙を始めていることから、vがbetaを超えさえすれば、簡単にt_1''のl/bをa＞bという、矛盾したものにしてしまう*4。
つまり、この恐るべき事件は会議室ではなくて現場で実際に起き得るのだ
さらに、一見a≦bが保たれており明白な矛盾が見られないケースについても、ただちに信頼するというわけにはいかなくなる…
唐突だが以上
■結び
探索延長ってやつは諸悪の根源でありながらいつまでも付きまとってくるしー；
藻前はストーカー女か、
