连接四个散列函数:将关闭元素映射到关闭散列键
我正在写一个Connect Four游戏引擎。目前，我正在使用Zobrist hashing为不同的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我甚至不知道这是否可能。谢谢你的帮忙!
回答 2
Stack Overflow用户
发布于 2011-05-06 05:48:35
我认为这是不可能的。一个好的散列密钥(就像zobrist散列是用于棋盘游戏的)最有可能具有伪随机属性，以实现密钥在转置表中的均匀分布。表中“关闭”位置的键彼此靠近，这与此相矛盾。
考虑一下这一点:即使您将电路板位置一对一地映射到具有(2^7-1)^7个位置的表中，您也无法将“关闭”电路板位置映射到关闭的内存位置:如果低索引的块发生变化，位置将接近，但块索引越高，位置差异每次都会翻一番，高的将是几to的间隔;-)
作为一个国际象棋引擎的作者，我知道这个问题。AFAIK还没有人解决这个问题，每个人都使用zobrist散列，可能只做了一些小的修改。
无论如何，祝你好运解决Connect-4...我知道以前有人做过，但自己做会更令人满意;-)
Stack Overflow用户
发布于 2011-05-06 06:52:20
这里是如何修改你的几乎一致的随机哈希函数，使其偏向于在附近的哈希处可能出现类似的棋盘位置。
让hash(gamestate)作为您现有的函数。我们将创建一个newhash(游戏状态)，它将散列用于随机行为，但对于紧密相关的游戏状态，生成彼此接近的散列的概率相当高。
让棋盘状态的“颜色”成为下一个移动的玩家。如果想要找到白色播放器的散列键，可以使用newhash(board) = hash(board)。如果你想找到黑色位置的散列，根据你的顺序找到具有最大数量的黑色棋子，例如，在位置i。从游戏状态中删除棋子i，并调用修改后的状态probableparent，然后使用newhash(board) = hash (概率父母)+i。如果你按可能的放置顺序对位置进行排序(更高的东西作为第一顺序标准出现得更晚，也许中间位置出现得更早作为第二个标准？我真的不知道connect4的好策略)，那么很可能在黑色转弯之前的白色转弯可能是在父级，因此很好地在你的缓存中，因此我就在附近。此外，8个可能的黑色移动可能共享相同的prev_board状态，因此具有邻近的散列位置。
您可以将此想法扩展为一次回滚多个层。假设当前轮%3移除2，移除棋盘位置i和j处的最大两个移动，然后使用newhash( == )=hash(棋盘-2-移除-前)+ i*48 +j。
https://stackoverflow.com/questions/5904402
复制相似问题
腾讯云开发者
