前回の続き。新しくなった置換表を確保するコードの128GB制限を取っ払うことを考えます。

Stockfishのコミュニティでは、この乗算部分を64bit×64bitの掛け算にする(結果の上位64bitを取り出す)ことが提案されている。

128 GB TT size limitation : https://github.com/official-stockfish/Stockfish/issues/1349

そのへんを踏まえて、やねうら王では次のように書いた。

TTEntry* first_entry(const Key key) const {
#if defined (IS_64BIT) && defined(USE_SSE2)
uint64_t highProduct;
_umul128(key, clusterCount, &highProduct);
return &table[(highProduct & ~1) | (key & 1)].entry[0];
#else
return &table[(((uint32_t(key >> 1) * uint64_t(clusterCount)) >> 32) & ~1) | (key & 1)].entry[0];
#endif
}

ところが、これがすこぶる弱い。前のバージョンに100戦やって1勝も勝てない。目眩がした。

_umul128()で64bit×64bitの掛け算の結果のうちの上位64bitをhighProductに取り出しているわけであるが、このコードを次のように修正するとうまく動く。

_umul128(key << 32, clusterCount, &highProduct);

この理由がややこしいのだが、Stockfishのコミュニティで提案されているコードのまずい点はいくつかある。

まず、上のコードの動作について考えておこう。

置換表サイズは1MB単位で指定するので
clusterCount = 1024*1024 * mbSize / sizeof(Cluster)
である。

mbSizeは、Hashオプションで指定した値、sizeof(Cluster) == 32である。
例えば、Hashオプションで64(64MB)を指定すると、clusterCount = 1024 * 1024 = 2^20である。

このとき、highProduct = key * 2^20 / 2^64 == key / 2^44 == key >> 44 である。つまりkeyの上位20bitを取り出しているに過ぎない。

この実装が駄目な理由
1) この上位20bitというのが曲者で、TTEntry::key16はHashKeyの上位16bitを見ているので、もろに被っている。同じところを見るとハッシュの衝突確率が上がると思う。
2) singular extensionのときに1つの手(excludedMove)を除外して探索しないといけないので、そのときに
key = pos.key() ^ Key(excludedMove << 16);
としてあるのだが、excludedMoveはbit0..15に指し手が格納されているので(やねうら王の場合、移動させる駒もbit16..に格納されてはいるが、細かい話になるので割愛)、16回シフトするとbit16..31に来る。これをxorするのでkeyのbit16..31は改変される。ところが、さきほどのケースだとkeyの上位20bitしか見ないのだ。

つまり、2)が致命的にまずく、singular extensionのときに必ずhash衝突が起きるのである。おそらくStockfishのさきほどのスレの人たちは置換表サイズをもう少し大きくとっていて、このことに気づいていないのだと思う。

3) 2)以外にもどこか同じような原因の箇所がある。(特定できていない) 例えば、_umul128(key << 32 , … )のように変更すると解決する。(誰かお気づきの方は、コメント欄でコメントお願いします。)

とりあえず、簡単な修正案としては、泥臭いコードだが、

_umul128(key + (key << 32) , clusterCount, &highProduct);

のようにbit16..31が、上位bit付近に反映されるように何らか手を加えてやることである。

とりあえず3)が解決したら、Stockfishの当該スレに書いてこようかと思っているが…。