ボナンザ hash/ehashの問題点

前々回の記事はちょっと記述はしょりすぎでしたね。オープン戦の片手間に書いてたのがまずかったか…もうちょいちゃんと説明します。

>Pentium 以降の ia32 は 64bit アラインされた quadword が atomic のようです。

それはたしかにそうなんですけれども、C言語でたとえば

uint64_t a,b;
  :
a = b;

のような代入文があったとして、これを普通に32bitでコンパイルするとマシン語レベルでは32bit load 命令２つになります。ia32の一般命令には64bit loadの命令が存在しないですから。Intel マニュアルの記述はマシン語レベルの話なので、２マシン命令になれば当然ながらatomicityは保証されません（間に別のストアが入り得る）。

ia32でatomicにするには、SSEなりMMXなりの64 bit loadを指定する必要がありますが、これにはソースをいじる必要があります。64bit modeならば普通のコンパイルで64 bit loadになりますので問題ありません。

この原因によりハッシュが壊れるのは、確率的には非常に小さいでしょう。本家ボナンザでは影響は微々たるものなんだと思います。実際、以前に並列ボナのRを測ったときも32bitでやりましたが、劣化には気づきませんでした。ただ、影響が確率的に小さいというだけで、バグとしては確実に存在するはずです。

hashの方はword1,word2どちらかでも壊れるとSignKeyのためhitしないかもしれませんね。だからアサートにひっかからないのかもしれません。その意味では、hashの方はバグではないとも言えるかも。ですがehashの方は時々壊れた値を使ってると思います。ただαβ探索では１ノードで評価値間違っても全体の結果に影響与えることはまずないので、なかなか顕在化しないのでしょう。

bonasseではevaluateを差分計算しています。１コアではこの効果はかなりあったのですが、これを32bitで並列にするとぼろぼろに弱くなりました。１コアよりも弱いくらいに。この原因はと考えるにおそらく、ehashである局面で破壊が起きると、差分のためそれより下の局面全部で間違うので、本家ボナよりはるかに大きく影響が出たのではないかと推測しています。実際、まったく同じソースで64bitにするとちゃんと強くなったので、この仮説は正しいのだろうと思っています。