连接四个哈希函数：映射关闭元素以关闭哈希键

Question

我正在编写一个Connect Four游戏引擎。目前，我使用Zobrist hashing为不同的Connect Four板位置生成散列键（为了不再做同样的事情，评估板位置存储在散列表中）。评估板位置（最小最大树中的节点）总是彼此接近。不幸的是，关闭的棋盘位置被映射到统一分布的散列键，导致大量的cpu缓存未命中。

是否有可能建立一个散列函数来映射关闭板位置以关闭散列键？

一个玩家A板位置由以下结构的棋盘表示：

. . . . . . . TOP 
5 12 19 26 33 40 47 
4 11 18 25 32 39 46 
3 10 17 24 31 38 45 
2 9 16 23 30 37 44 
1 8 15 22 29 36 43 
0 7 14 21 28 35 42 

我不知道，如果它甚至有可能。 感谢您的帮助！

Answer 1

我不认为这是可能的。一个好的散列键（如zobrist散列用于棋盘游戏）很可能具有伪随机属性，以实现转置表中键的均匀分布。在表中，“关闭”位置的键彼此接近，这与此相矛盾。考虑到这一点：即使您将棋盘位置一对一地映射到（2^7-1）^ 7位置的表格，您也无法将“关闭”棋盘位置映射到关闭存储位置：如果一个低指数的产品会发生变化，仓位将会接近，但是每个指数获得的仓位差距会增加一倍，而高仓位将会有很多TB的差距;-)

作为国际象棋引擎我知道这个问题。 AFAIK没有人解决这个问题，每个人都使用zobrist哈希，也许稍做修改。

无论如何，祝你好运解决连接-4 ......我知道这之前已经完成，但它是更理想的做自我;-)

Answer 2

下面是如何修改想必几乎均匀随机哈希功能可以以类似的电路板位置有可能在附近的哈希中发生的方式对其进行偏置。

让hash（gamestate）成为你现有的函数。我们将创建一个newhash（gamestate），该hash用于随机行为使用散列，但对于密切相关的游戏状态而言，产生彼此靠近的散列的概率相当高。

让棋盘状态的'颜色'成为下一个要移动的玩家。如果想找到白色播放器的散列键，使用newhash（board）= hash（board）。如果您想查找黑色位置的散列，请根据您的订单查找最大数量的黑色碎片，比如在位置i。从游戏状态中移除我，并调用修改状态probableparent然后使用newhash（board）= hash（probableparent）+ i。如果您按照可能的安排顺序排列职位（更高的事情会晚一些作为第一顺序标准，也许中间位置会更早地作为第二条标准？我真的不知道connect4的好策略），那么有点可能在黑色转弯之前的白色转弯处于可能的状态，因此在你的缓存中很好，因此我就在附近。此外，8种可能的黑色移动可能会共享相同的prev_board状态，因此在哈希位置附近。

您可以扩展此想法，一次回滚多个层。说如果当前转向％3 == 2，在板位置i和j上移除最大的两个移动，然后使用newhash（board）= hash（board-two-removals-ago）+ i * 48 + j。