Zobrist Hash表示棋盘状态的思路

Ray

先从知乎引入一段Zobrist方法的定义：
Zobrist 哈希是一种专门针对棋类游戏而提出来的编码方式,以其发明者 Albert L.Zobrist 的名字命名。Zobrist 哈希通过一种特殊的置换表,也就是对棋盘上每一位置的各个可能状态赋予一个编码索引值,来实现在极低冲突率的前提下在一个整型数据上对棋盘进行编码。其编码步骤描述如下:
1) 将棋盘分为最小单位(如果将9X9围棋盘分为81个交叉点),求出每个单位上不同状态数(如围棋盘上的 1 个交叉点有 3 个状态)。
2) 为每个单位上的每种状态生成一个一定范围内(如64位整数)随机数。
3) 对于特定的棋局,将每个单位上的状态对应的随机数作异或运算,所得即为哈希值。
用 Zobrist 哈希为棋局状态编码至少具备两个优点:
当随机数的范围足够大时,不同的棋局产生哈希冲突的概率非常小,在实际应用中通常可以忽略。
在棋局进行过程中,不必每次重新开始计算棋局的哈希值,只需计算棋局状态发生改变的部分。
来源：https://zhuanlan.zhihu.com/p/605462944

对于我们的五子棋棋局，我们需要3*19*19+1个随机数来表示所有棋盘。
我们需要19*19个随机数来表示空格，19*19个随机数来表示黑棋，19*19个随机数来表示白棋，1个随机数来表示棋盘。
每次开局时，我们先将所有空格随机数和棋盘随机数（也就是19*19+1个随机数）一起xor，得到一个整数H，对应当前棋局。
每次落子后，我们将H与对应坐标的空格随机数和对应坐标的黑/白棋随机数一起xor，得到一个新的整数H'，即可对应新的棋局。
那我们有以下论断：
1. 同一个棋局对应的整数H相等。
2. 落子顺序不影响棋局对应的整数H。
3. 同一个整数H对应的棋局不一定相等，但是大概率完全没关系。
此时我们就可以用一个整数来表示一个棋盘。

应用1. 我们可以用一个数组组成的列表，如[(H1,Value1),(H2,Value2),(H3,Value3),...]来存储深度搜索过程中不同棋局的价值。这可以在搜索中减少重复运算（如搜索a1,a2,a3,a4,a5,a6与搜索a1,a6,a3,a2,a5,a4两条落子路径会引向同一个棋盘），并且为算杀提升效率。
应用2. 我们还可以用这个整数提前运算，并且将不同棋局的价值存储在文本文件中。但是此时我们需要一组固定的随机数。我们可以用random.seed()来实现这一点，亦或是先打一组固定的随机数表。（还有没有别的方法？）

Ray

另，这些随机数要多大才算够大？
这些整数是不是最好要mod一个素数后存储？如果是的话，这个素数取什么比较好？

种肉肉的农夫

32位会有哈希冲突，64位才可以完全杜绝哈希冲突