8乘8板的完美散列函数？

我正在实现一个只有两种类型的棋盘，并且正在寻找一个从该棋盘映射到长整数（64位）的功能。我认为这不应该太难，因为一个长整数包含比8 * 8数组更多的可用信息（称为grid [x] [y]），每个点只包含3个可能的元素，包括空元素。我尝试了以下方法：
（1）Zobrist哈希与Longs而不是ints（只是为了测试 - 我实际上并没有期望它能够完美地工作）
（2）将网格转换为基本3的64个字符的字符串号码，然后把这个数字解析成一个长整数。我认为这应该起作用，但花了很长时间。
是否有一些更简单的方法来解决（2）涉及位移操作或类似的操作？
编辑：请不要给我实际的代码，因为这是一个类项目，这可能在我们的部门被认为是不道德的（或者至少不是在Java中）。编辑2：基本上，任何时候在棋盘上只有10个白人和10个黑人，其中任何两个相同颜色的棋子在水平，垂直或对角线方向上都不可能是邻居。另外，每种颜色只有12个空格，只有该颜色可以放置棋子。8乘8板的完美散列函数？

来源

2010-11-29 Rishi

完美的混编使用版本将短值映射到完成的输出。在你的情况下，似乎更像是你正在寻找一个编码方案来存储你的值。你有8 * 8个单元格，每个单元格有3个不同的值。对于没有压缩方案的64位而言太多了。然而，很难说如果不知道更多关于那里有多少件，或者它们如何在板上分布，那么好的算法会是什么。 – Cine 2010-11-29 07:28:41

很明显，您的编辑会对问题产生影响。但为什么坚持64位int？ – 2010-11-29 07:42:46

嗯，我想如果有必要，我不介意使用更大的对象。只希望尽可能小，以免发生内存不足错误。 – Rishi 2010-11-29 07:44:31

如果游戏中的每个瓦片可以在游戏中的任何点是任意3个状态的1，散列游戏板的每个可能的状态时，在任何给定所需的“完美散列”存储的，那么最小量瞬间将
=功率（3,8 * 8）个别散列
= log2(3^64)位
=约。 101.4位，所以你将需要至少102位来存储这个信息

在这一点上，你可能只是说，每个瓷砖有4个州，这将使您需要128 bits。

一旦你这样做了，就很容易为电路板制作一个快速的散列算法。

E.g.（writtin如C++，可能需要改变代码，如果平台不支持128张的数）

 
uint_128 CreateGameBoardHash(int (&game_board)[8][8]) 
{ 
    uint_128 board_hash = 0; 
    for(int i = 0; i < 8; ++i) 
    { 
     for(int j = 0; j < 8; ++j) 
     { 
      board_hash |= game_board[i][j] << ((i * 8 + j) *2); 
     } 
    } 
    return board_hash; 
}

此方法将仅在102位的最优解废物26个比特（略多于3个字节），但您将节省大量的处理时间，否则这些处理时间将花费在基础3数学上。

编辑这里是不需要128位，应该在任何16位（或更高）处理器工作

 
struct GameBoardHash 
{ 
    uint16 row[8]; 
}; 

GameBoardHash CreateGameBoardHash(int (&game_board)[8][8]) { GameBoardHash board_hash; for(int i = 0; i < 8; ++i) { board_hash.row[i] = 0; for(int j = 0; j < 8; ++j) { board_hash.row[i] |= game_board[j] << (j*2); } } return board_hash; }

当你有一个预定义的输入和需要

来源

2010-11-29 08:10:30