Lock-Free Hash Table

[Nyanyan]

HyattらのLock-Freeハッシュテーブルを試してみたい

keyとして

• player ^ value
• opponent ^ best_move1 ^ (best_move2 << 8)

あたりを登録すれば良さそう

参考メモ: https://scrapbox.io/nyanyan/Lock-Free_%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86%E3%83%BC%E3%83%96%E3%83%AB

[Nyanyan]

keyは

• player ^ lower
• opponent ^ upper

としよう

[Nyanyan]

なんかwrong score / wrong policyのバグがある。

ノードの探索深さとmpcレベルも含めて、keyを

• player ^ lower ^ (depth << 8)
• opponent ^ upper ^ (mpc_level << 8)

とするか。最善手情報についてはミスっていても致命的な問題にはならないので一旦保留で良いが、

• player ^ lower ^ (depth << 8) ^ (moves[0] << 16)
• opponent ^ upper ^ (mpc_level << 8) ^ (moves[1] << 16)

も検討しよう。

[Nyanyan]

いや、本来であればplayerとopponentの各キーに対して全ての(間違えると致命的な)情報をxorしておくべきでは？？

• player ^ lower ^ (upper << 8) ^ (depth << 16) ^ (mpc_level << 24)
• opponent ^ lower ^ (upper << 8) ^ (depth << 16) ^ (mpc_level << 24)

をキーとしなければいけないはず。

[Nyanyan]

よく考えたらkeyのビットとvalueのビットの双方同じところが反転したデータに対してはバグる可能性があるので、lock-freeなハッシュテーブルは良くないような気がする。元の実装(を若干リファクタリングしたもの)に戻す。