如何为散列矩阵（Otherlo board）定制散列函数

Question

我必须做的项目，我需要为散列矩阵自定义函数。该项目是关于奥赛罗（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

函数接受board（矩阵），并首先生成包含所有board字段的字符串，其顺序和状态与board中的相同。之后，我使用for循环中的公式对该字符串进行散列。函数ord返回字符的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