连接四个哈希函数：将闭合元素映射到闭合哈希键
我正在编写一个 Connect Four 游戏引擎。目前，我正在使用 Zobrist 哈希 为不同的 Connect Four 板位置生成哈希密钥（为了不做两次同样的事情，评估的棋盘位置存储在哈希表中）。评估的棋盘位置（极小极大树中的节点）始终彼此接近。不幸的是，接近的板位置被映射到均匀分布的散列键，导致大量 CPU 缓存未命中。
是否可以构建一个哈希函数，将接近的棋盘位置映射到闭合的哈希键？
一名玩家的棋盘位置由以下结构的位板表示：
. . . . . . . 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
我不知道这是否可能。 感谢您的帮助！
I'm writing a Connect Four game engine. Currently I'm using Zobrist hashing to generate hash keys for different Connect Four board positions (In order not to do the same thing twice, evaluated board positions are stored in a hash table). The board positions evaluated (nodes in a minimax tree), are always close to each other. Unfortunately close board positions are mapped to uniformly distributed hash-keys leading to a lot of cpu cache misses.
Is it possible to build a hash function which maps close board positions to close hash keys?
A board position for one player is represented by a bitboard of following structure:
. . . . . . . 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
I don't know if it is even possible.
Thanks for your help!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为这是不可能的。一个好的哈希密钥（如棋盘游戏的 zobrist 哈希）很可能具有伪随机属性，以实现换位表中密钥的均匀分布。在表中使“平仓”仓位的键彼此靠近与此相矛盾。
考虑一下：即使您将棋盘位置一对一映射到具有 (2^7-1)^7 个位置的表格，您也无法将“接近”棋盘位置映射到闭合内存位置：如果棋子位于低索引变化，位置会很接近，但棋子索引越高，位置差异每次都会加倍，而高索引会相距许多 TB ;-)
作为国际象棋引擎的作者，我知道这个问题。 AFAIK 还没人解决这个问题，每个人都使用 zobrist 哈希，也许需要一些小的修改。
不管怎样，祝你好运解决 Connect-4...我知道以前已经做过，但自己做更令人满意;-)
I don't think this is possible. A good hash key (like zobrist hashing is for board games) will most likely have pseudo random properties to achieve a uniform distribution of keys in the transposition table. Having the keys of "close" positions close to each other in table contradicts this.
Consider this: Even if you map your board positions one to one to a table with (2^7-1)^7 positions, you will not be able to map "close" board positions to close memory locations: If a piece at a low index changes, positions will be near, but the higher the piece index gets the position differences double each time, and the high ones will be many terabyte apart ;-)
As an author of a chess engine I know this problem. AFAIK nobody solved this problem yet, and everybody uses zobrist hashing, maybe with some minor modifications.
Anyway, good luck solving Connect-4... I know it has been done before, but it is more satisfactory to do it self ;-)
以下是如何修改您大概几乎一致的随机散列函数，以使其偏置，使得类似的棋盘位置在某种程度上可能出现在附近的散列处。
让 hash(gamestate) 成为您现有的函数。我们将创建一个 newhash(gamestate)，它使用哈希来实现随机行为，但对于密切相关的游戏状态，生成彼此接近的哈希的概率相当高。
让棋盘状态的“颜色”成为下一个移动的玩家。如果想找到白人玩家的哈希密钥，请使用 newhash(board) = hash(board)。如果你想找到黑色位置的散列，请根据你的顺序找到编号最大的黑色块，例如在位置 i 处。从游戏状态中删除棋子 i 并调用修改后的状态 probableparent 然后使用 newhash(board) = hash(probableparent) + i。如果您按可能的放置顺序对位置进行排序（较高的位置作为第一个顺序标准，也许中间位置较早作为第二个标准？我真的不知道 connect4 的好策略），那么有可能黑色转弯之前的白色转弯位于可能的父节点，因此很好地位于您的缓存中，因此 i 就在附近。此外，8 个可能的黑棋可能会共享相同的 prev_board 状态，因此具有附近的哈希位置。
您可以扩展此想法以一次回滚多个层。假设当前回合 % 3 == 2，删除棋盘位置 i 和 j 处的最大两次移动，然后使用 newhash(board) = hash(board-two-removals-ago) + i*48 + j。
Here is how to modify your presumably nearly uniformly random hash function to bias it in a way that similiar board positions are somewhat likely to occur at nearby hashes.
Let hash(gamestate) be your existing function. We'll create a newhash(gamestate) that uses hash for the random behavior, but has a reasonably high probability of generating hashes that are near each other for closely related game states.
Let the 'color' of a board state be the next player to move. If want to find the hash key for the white player, use newhash(board) = hash(board). If you want to find the hash for a black position, find the black piece with maximal number according to your order, say, at position i. Remove piece i from the game state and call the modified state probableparent Then use newhash(board) = hash(probableparent) + i. If you order the positions by likely order of placement (higher things come later as a first order criteria, maybe the middle locations come earlier as a second criteria? I don't really know good strategy for connect4), then it's somewhat likely that on the white turn before the black turn was at probableparent, and hence nicely in your cache and hence i is near by. Also, the 8 possible black moves will likely share the same prev_board state and hence have near by hash locations.
You can extend this idea to roll back more than one ply at a time. Say if current turn % 3 == 2, removing the maximal two moves at board positions i and j , and then use newhash(board) = hash(board-two-removals-ago) + i*48 + j.