sakurapyon’s blog

sakurapyon’s blog

置換表難しい

今までわかったような気になってたことが、考え始めると全然わかってなかったことに気がついたり、気になったりする。GMA0BNさんの置換表シリーズも気になってることの一つ。

前にも書いたけど、私の思っている探索木はこれじゃなくて

こんな形をしている。

探索延長はあるし、各種のreductionがあるので、評価した局面の深さはきっとばらばらだ。置換表に登録されている値も、どれぐらい信用していいんだかイマイチわからない。でも、置換表に登録されている指し手は、試してみてダメなら捨てればいいし、かなりの割合で最善の指し手になるから使わない手はない。深さが浅かろうがなんだろうが手は使える。2手使えるかどうかは謎だ。私は1手だけ登録している(メモリも足りないし)。ということで指し手は局面さえ一致していれば使う。

問題は値だ。登録した時点よりも浅いのは捨てていいとして、深さが等しかったりより深いものは使っていいんだろうか? と、思って bona6 のソースをみたら、ずいぶん慎重に値を使っているようだ。そうだよなあ…

前回の手番で考えた指し手は使えるから、置換表自体を毎回クリアするのはもったいない。かといって値を不用意に信用するとたぶんはまる。

例えば王手延長になった先の局面があったとして、前回の探索では延長上限に達したために不詰みと判断したとする。今回は2手先に進んだので、前回同様に探索延長すれば詰みが見つかるとしよう。sakurapyonはあまり先が読めないので、こういう局面に遭遇することは多い (逆に詰みの値であればたぶん信用していい)←これもダメっぽい。

さて、そのときに置換表を見ると不詰みになった値があり、かつ深さは一見充分に見えたりするわけだ。ん...んん。れさぴょんには、 e.depth<=depth なる判断が入ってるけど、そのせいかな... (れさぴょん本は部屋のどこかに埋もれていて発掘できない)。

れさぴょんは置換表を消去していないから、置換表には前の手番のときの値が残っている。探索深さdeptMax=8として、そこでdepth=4で登録された情報はe.depth=4, e.remainDepth=
4 になると。次回手番がくると、depth=2 のときにこの表に遭遇する。すると e.depth<=depthが成立しないのでこの値は使われない（remainDepth>=depthであっても)。depth=2の探索が進んで値が得られると HashAdd にて上書き登録される。上書きするのはいいんだけど、値を使わないのはなぜだろうか?

逆にどんな場合なら値が使われるんだ? e.Tesu>=k.Tesu があるから、登録時点における手数が等しいか大きい。これは反復深化すれば容易に実現する。e.depth<=depth になるのが難しい。同じ手順で同じ局面になるなら e.depth>depth になっちゃうので、違う手数で同一局面になる場合だな、これは。ああ、そういうことか。要するに違う手順で同一局面に遭遇した場合にのみ使えて、かつ、今回のほうが探索残りも少ない場合か。これはよっぽどの場合じゃないと遭遇しない気がするがそうでもないんかな?　やっぱり良くわからない…

メモ：