如何为散列矩阵（黑白棋盘）制作自定义散列函数到数字

Question

我必须做一个项目，我需要为散列矩阵自定义函数。项目是关于 Othello (Reversi) 游戏，这意味着我需要散列固定的 8x8 矩阵。

这是初始化矩阵的样子：

board = [['.' for x in range(8)] for y in range(8)]

这是一个棋盘外观示例：

[
['.', '.', '.', '.', '.', '.', '.', '.'], 
['.', '2', '1', '.', '.', '.', '.', '.'], 
['.', '.', '2', '.', '.', '.', '.', '.'], 
['.', '.', '1', '2', '1', '.', '.', '.'], 
['.', '.', '.', '1', '2', '.', '.', '.'], 
['.', '.', '.', '.', '.', '.', '.', '.'], 
['.', '.', '.', '.', '.', '.', '.', '.'], 
['.', '.', '.', '.', '.', '.', '.', '.']
]

如您所见，一个玩家是 1（始终是我），第二个玩家是 2（始终是计算机），. 是空棋盘位置。

我制作了某种散列函数。它看起来像这样：

def hash(self, board):
        string = ''
        for y in range(8):
            for x in range(8):
                string += board[y][x]
        broj = 0
        for index, znak in enumerate(string):
            broj += (index + 1) * ord(znak)
        return broj

函数接受棋盘（矩阵）并首先生成包含所有棋盘字段的字符串，其顺序和状态与棋盘中的一样。之后，我使用 for 循环中的公式对该字符串进行哈希处理。函数 ord returns 字符的 ASCII 值。

我知道这不是一个很好的散列函数，所以我很想听听一些改进这个函数或实现一些完全不同的想法。我看到了基于用两个 64 位二进制数表示棋盘的想法，其中第一个数字包含玩家 1 在所有其他地方都有棋子和零的地方，第二个数字包含玩家 2 在所有其他地方都有棋子和零的地方地方。在那之后，我记得，我必须使用某种算法对这两个数字进行哈希处理。问题是，我不知道这是否是好的散列函数以及我是否可以实现它。

需要注意的重要一点是我不能使用内置哈希函数或从某些库导入的任何其他函数。我必须使用某种算法制作自定义哈希函数。

提前致谢。

Answer 1

正如我在对我的原始（虚假）评论的回复中指出的那样，您可以将每个董事会状态视为一个 64 位 base-3 数字。这种方法将为每个可能的配置生成一个唯一的整数值——可以将其视为其“哈希”值。

这就是我的意思：

def hash_func(board):
    numstr = (''.join(''.join(row) for row in board)).replace('.', '0')
    return int(numstr, 3)  # Convert to an integer.


sample = [['.', '.', '.', '.', '.', '.', '.', '.'],
          ['.', '2', '1', '.', '.', '.', '.', '.'],
          ['.', '.', '2', '.', '.', '.', '.', '.'],
          ['.', '.', '1', '2', '1', '.', '.', '.'],
          ['.', '.', '.', '1', '2', '.', '.', '.'],
          ['.', '.', '.', '.', '.', '.', '.', '.'],
          ['.', '.', '.', '.', '.', '.', '.', '.'],
          ['.', '.', '.', '.', '.', '.', '.', '.']]

print(f'{hash_func(sample):,}')  # -> 135,688,629,099,716,090,516,394,594

如何为散列矩阵（黑白棋盘）制作自定义散列函数到数字

How to make custom hash function for hashing matrix (Othello board) to number

python

algorithm

hash

reversi

othello