0

我必须做需要自定义散列矩阵函数的项目。项目是关于黑白棋（黑白棋）游戏，这意味着我需要散列固定的 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返回字符的 ASCII 值。

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

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

提前致谢。

4

1 回答 1

2

正如我在对我最初的（虚假）评论的回复中指出的那样，您可以将每个棋盘状态视为一个 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
于 2021-05-22T08:16:05.823 回答