やねうら王 classic 2.15 新旧置換表の調査（未完成）

　明らかなバグは１つ直したが、要因が１つじゃ無さそうなので忘れないようにまとめる。


■前条件

・仕様ソフト
　やねうら王 classic 2.15 NEW_TT（ありなし）

commit c967423d23fe07a695f1de1bf2b4385165d67976
Author: yaneurao 
Date:   Mon Mar 7 11:31:40 2016 +0900

    古い置換表のメモリ確保のバグ修正。

　48bit時に異常に遅くなっていたのが直ったが、確かに直る理由がわからない。（要確認）
　この現象は本当に謎。


■致命的なバグ

・局面ハッシュキーの最下位ビットを消している
　NEW_TTなし（以下OLD_TT）では、１６バイト＊４つのエントリを１クラスタとして管理している。そのため、クラスタの先頭エントリを返すfirst_entry()では、局面のハッシュキーにhashMaskというビットマスクによって下位２ビットを消して４の倍数にしている。

　ところが、局面ハッシュキーの最下位ビットは手番を表現しているため、このマスクによって手番が消されてしまい、後手番が先手番のハッシュ値を書き換えることが起こりうる。これによって後手が８九歩を打つというようなことが発生してしまっていた。

　試しにbenchコマンドでこのような場合が発生するか確認したところ、３局面程度発生した。また、ハッシュキーのビット数があまり関係なく、置換表の大きさが関係していることがわかった。（小さいほど保持されるキーの種類が少ないので発生しづらい）

　置換表のクラスタがどちらかの手番であることが保証されたことにより、position.cppのpseudoLegalあたりで違法手のチェックを省くことができる。また、ハッシュ衝突によって上書きされてしまうことによる精度の低下の影響が少なくなるように思える。

・解決方法
　一番容易な解決方法は、first_entryのkeyを２ビット左にシフトすることである。

 inline TTEntry* TranspositionTable::first_entry(const Key key) const {

   //:  return table + ((uint32_t)key & hashMask);
+  static_assert(ClusterSize == 4,"ClusterSize must be 4");
+  return table + ((uint64_t)(key<<2) & hashMask);

　この修正を入れることで、OLD_TTとNEW_TTの勝率はほぼ５割になることが期待されるのだが、実際は少し負け越している。綺麗に１：２の割合なのでレーティングでいうと１００差ちょい。置換表以外は全く同じなのでこれほど差がでるのは旧置換表がおかしいとしか言いようが無い。

以下気になるところ

・メモリ効率

　クラスタサイズが片や６４バイト、片や３２バイトなのでクラスタインデックスだとNEW_TTのほうが２倍の空間があることになる。だからメモリを倍にしてレーティングが同等になるのではないかという予測も立つ。
＞メモリを倍にしたらレーティングが同等になるか

・置換条件
　上記の修正を入れた場合の差を見てみると、probe時に再配置する場所を決定するかどうかという以外に、store条件がある
　→あまり関係がない。今の探索速度だと置換表サイズが8G/16Gとかあって初めて意味があると思われる。上書き回数などを調べたところ、上書きは１％にも満たない程度の数なので、勝敗にはあまり関係ない

・トン死がひどい
　結構な割合で１０００を超えている状態から頓死する
　これはどっちかの現象ではなく、両方にあるので基本的な部分で何か不具合がありそう。
　これがやねうら王２０１５と対局して全く勝てない理由の可能性はある。
　→当たり。自玉に王手がかかっている場合でも、相手玉に王手が掛けられる場合はそちらを優先してしまうようになっている。探索中の一手詰め判定は王手がかかっていない場合に限定することで、かなりトン死確率が下がり、勝率があがった。（暫定スコア１：０：２ -> ４：１：５）
　新置換表にこれを入れれば相当ではないか。

＜追記＞

・メモリ探索速度
　はるか昔BonanzaのNPSはキャッシュ込み、GPSFISHはキャッシュ無し（do moveのみ）みたいなので、NPSをどう定義したらええんや、みたいなことを書いていたのはLS3600氏だった気がするが、これを直接確認する指標がないので、プログラムにカウンタつけて調べてみた。（ローテク）
　すると、メモリ探索速度が１７％ほどNEW_TTのほうが多かった。しかし、探索時間はほとんど変わらない。この結果が有効かどうかは正直よくわからないが、速度的に速い分有利なのではないかという気はしている。ただ、置換表上は１７％多く読んでるはずなのに探索深さなどが変化がないこと。１秒でDepth20とかかいくので影響がないのかもしれないが、調べてみた方はよい。