以下では、プログラマー向けに説明を書きます。
その昔、CPUの演算で、掛け算が異様に遅い時代があった。割り算はいまでも足し算なんかに比べるとずいぶん遅いけども、掛け算はいまや足し算の数倍程度の時間しかかからない。
置換表は、次のようにして置換表のエントリー(TTEntry)を決定する。
・Keyは局面を表す64bitのhash keyである。
・clusterCountは、確保されたTTEntryの要素の数であるとして、2のべき乗である。
疑似コードで示すと次のようになる。
TTEntry* first_entry(Key key)
{
return &table[key & (clusterCount – 1)];
}
(2のべき乗 – 1)は、2進数的に見ると01111111bのように1が並ぶ形なのでbitwise andを取ると下位のN-bitが取得できるという仕組みである。
このようにTTEntryの決定にbitwise andを用いていた。なので、clusterCountは2のべき乗でならねばならなかった。
実際には、やねうら王ではsizeof(TTEntry)==10で、それを3つ束ねて30バイトにして、2バイトpaddingして32バイトのClusterを作り(CPUのcache lineに合わせるため)、それをclusterCount分だけ用意してある。
細かい話はともかく、clusterCountが2のべき乗で、かつ、tableの全体サイズも2のべき乗バイトでなければならないという制約があった。
このため、やねうら王では将棋所/ShogiGUIでHashサイズ(置換表のためのメモリ量)として2のべき乗しか指定できなかった。2のべき乗以外を指定しても、2のべき乗分しか確保していなかった。
ところがこれだと128GB搭載しているPCでも64GBしか置換表のためにメモリが使えない。OSと思考エンジンが置換表以外に使うメモリを合わせても4GBほどしかないはずで、残りの60GBは丸ごと遊んでしまう。すごく無駄である。
そこで、現代風に掛け算を用いてTTEntryを決定することにより、この制約を取り除こうというアイデアがある。
Allow for general transposition table sizes. (#1341) : https://github.com/official-stockfish/Stockfish/commit/2198cd0524574f0d9df8c0ec9aaf14ad8c94402b
疑似コードで示すと次のようになる。
TTEntry* first_entry(Key key)
{
return &table[(uint32_t(key) * clusterCount) >> 32];
}
32bitのhash key × clusterCount / 2^32 をしているので結果は 0 から (clusterCount – 1)の値になるはずである。hash keyが一様分布であれば、この結果もまた一様分布だと考えられる。
冒頭にも少し書いたが、掛け算は足し算やビット演算に比べてたかだか数倍の時間がかかるだけなのでおおよそ無視できる。
やねうら王もさきほどこのアイデアを借用し、次のように改造してみた。
TTEntry* first_entry(const Key key) const {
return &table[(((uint32_t(key >> 1) * uint64_t(clusterCount)) >> 32) & ~1) | (key & 1)].entry[0];
}
keyのbit0はその局面の先手/後手を表すフラグなので、このbit0はそのままtableのindexのbit0に反映されて欲しい。(先手用の局面の情報を、後手用の局面を保存しているentryに保存した場合、hash衝突したときに、指し手が非合法手になるのを避けるため)
そこでkeyのbit0は、(key & 1)として取り出してある。また、ここでkeyのbit0を用いるので、前半のところでkeyのbit0を用いると、前半の計算に31bitしか使っていないことになる(?)ので、(key >> 1)としてある。わりと細かいことだが、大切なことである。
このようにしたところ、1スレッド1秒でHash = 3を指定して前のバージョンと対局させた場合、R70〜100ぐらい違う。前のバージョンでは置換表が2MBしか確保しないのに対して、このバージョンでは置換表を3MB確保できる。その差が現れる。
そんなわけで長い持ち時間で対局させ、置換表の使用率が50%以上の状況とかだと顕著に効果があるのかも知れない。
ところで気になるのは上の計算式ではclusterCountが32bit符号なし整数で表現できる範囲(2^32-1)を超えるとまずい。(使っていないことになる)
やねうら王の場合、TTEntryを3つ束ねて1つのClusterとしていて、これがsizeof(Cluster) == 32なので、32バイト×2^32(4GB) = 128GBまでしか有効に活用できない。いまどきAWSなどで上位スペックのPCを借りると256GB以上搭載されているというのに…。
この解決策については別の記事で書く。