近年、PCの搭載メモリは格段に増えて、将棋AIの大会で使うマシンに搭載されているメモリは256GB以上が普通になってきている。(例えば、DL系の将棋ソフトがよく使っているAWSのp4d.24xlargeは、1152GiB搭載)

このような巨大メモリを持っている場合、将棋ソフトの置換表(一度調べた局面の情報を格納しておく表)用のメモリを確保できるのかという問題がある。やねうら王ではいつぞやの改良によって、USI_Hash(置換表サイズを指定するエンジンオプション。単位は[MB])で、これが64bitで指定できるようになったので、1000GBでも1000TBでも1000PB(ペタバイト)でも指定できるようになっている。上限は64bitアドレス空間の16EB(エクサバイト)で、そこ近くまで置換表のために使い切れるようになっている。

置換表に情報を格納する時に、局面に対応する64bitの値(これをhash keyと呼ぶ)を計算し、それによって置換表のどこに格納するかを決める。

ところが、TTEntry(置換表の1つのrecord)に格納するhash keyは16bitしかないため、わりと高い確率で(1/2^16の確率で)他の局面の情報を持ってきてしまう。この(照合する時の)hash keyのbit数が足りないため、他の局面のhash keyと間違えてしまう現象のことをhash衝突と呼ぶ。

// 本筋でないことを書き出すとキリがないため、大雑把に話をしている。

hash衝突がこんな高い確率で起きて大丈夫なのかと言われるかも知れないが、実際問題として大丈夫ではない。有名なものとしては、mateだと錯覚するというバグがある。俗に言うmateバグである。

http://wdoor.c.u-tokyo.ac.jp/shogi/view/2022/04/09/wdoor+floodgate-300-10F+Kurara-test+Suisho6test2_TR3990X+20220409110004.csa/102

実際、mateバグは、hash衝突によって起きることが実証されている。格納するhash keyのサイズを増やせば、この問題は基本的には起きないのだ。

そこで格納するhash keyを64bitに増やすとする。そうするとTTEntryのサイズが増えてしまい、置換表効率が少し悪くなるが、まあそこはメモリがふんだんにあるなら、置換表効率より、mateバグのほうが致命的な問題であるから目を瞑ることにする。

しかし、そうしても、今度はメモリが1000GBや1000TBほどあると別の問題が起きる。TTEntryの場所は以下のようにして求めている。

TTEntry* tte = & Cluster[ClusterSize * hash_key / 2**64]

置換表全体はClusterという配列に入っているとする。ClusterSizeはこのClusterという配列の要素数である。hash_keyはその局面のhash key(64bit)。つまりは、64bit同士の掛け算をして2の64乗で割り算をしている。この結果は、0から(ClusterSize – 1)の間の整数となり、うまくバラけると言う仕組みである。

// 説明のために簡単化している。

ところがこの掛け算はhash_keyの上位bitが色濃く反映される。つまりは、TTEntryのアドレスを求めるのにhash_keyの上位bitを使ってしまっているのである。TTEntryに格納されているhash keyがいくら合致しようと、それが同一局面の情報である保証がない。例えば、ClusterSize = 2**64である場合、十分長い時間探索すると、それぞれのClusterの要素には何らかの局面の情報が格納されているはずであるが、この時、どのTTEntryにアクセスしても格納されているhash_keyとは合致してしまう。(100%の確率でhash衝突が生じるわけである)

// 説明が雑でわかりにくいかも知れない。わかる人だけわかって欲しい。

なんにせよ、TTEntryのアドレスを求めるためのhash keyと、TTEntryに格納するhash keyの64bitとは異なるhash keyのbitを割り当てないといけないのである。そこで、やねうら王 128-bit Editionでは、hash keyを128-bitで計算し、保持し、そのうちの下位64bitをTTEntryのアドレスを求めるのに用いて、上位64bitをTTEntryに格納するのに用いるということにした。これによりhash衝突が起きる確率は1/2**64になるし、また、置換表のサイズが16EB(エクサバイト)になろうとも、上の問題は起きないわけである。

この改造により、我々のPCのメモリが年々2倍に増えたところであと30年近くは問題なく動作するわけである。

これがやねうら王128-bit Editionである。メモリが256GB以上の環境で動かすなら、hash衝突の確率が天文学的な低さになっていることから、従来のやねうら王より強い…かも知れない。(計測してないのでわからない)

とりあえず、30年後も使えるやねうら王ということで、128-bit Editionをリリースしておく次第である。

やねうら王 V7.10 128-bit Edition ダウンロード先https://github.com/yaneurao/YaneuraOu/releases/tag/v7.10

補足1) hash keyの計算を128bitで行うようにしたが、これはAVX2の命令で計算するので計算によってNPS(探索速度)の低下はほぼ無い。
補足2) TTEntryのbyte数は10から16に増えた。改造前TTEntryは3つ束ねて30byteであった。そこに2byte paddingをして32byteであったが、改造後はTTEntryが16byteに増え、それを2つ束ねて32byteとした。32byteというのはCPUのcache lineのサイズで(注 : 最近のx86は64byteらしい)、alignされたメモリに配置されている限り、この読み込みに要する時間は変わらない。なのでこれによるNPSの低下は見られない。
補足3) TTEntryのサイズ増加によって、置換表のメモリ効率は悪くなるが、メモリがふんだんにある状況なら、それによる探索効率の低下は見られない。むしろ、hash衝突しなくなった分だけメモリがふんだんにある環境でなら強くなっている感じもある。

ともかく、メモリがたんさんある人にとっては、デメリット0の特別バージョンである。