局面判重问题

五子棋程序中，一个经常遇到的问题就是需要比较两个局面是否相同。有人说，五子棋的棋盘只有15×15，逐个格子比较就可以了，但是这不是最好的方法。我相信很快会有人想到Hash，只需要为局面计算Hash值，就能达到快速比较的目的。但是，这样做会遇到一个问题：两个Hash值相同的局面，其实并不一定相同。在五子棋程序的搜索过程中，会遍历成千上万个结点，如果Hash值冲突了怎么办？

解决方法当然不可能是在Hash值冲突的时候暴力枚举格子比较局面，而是为局面另外计算一个Hash值，我把它称为HashChk。计算HashChk的方法和计算Hash的方法不能相同。这样我们就可以在Hash值冲突的时候，比较HashChk是否相同。这个道理就好比登录网站的时候要输入密码，还要输入验证码，如果密码输对了，验证码输错了，是不能登录的。HashChk就是Hash验证码。

在实际程序中，通常可以把Hash的长度设为32位，HashChk的长度设为64位。有兴趣可以算算，这种情况下两个不同局面算出相同的Hash和HashChk的概率是多少。

Zorbrist数组

Zorbrist数组是棋类游戏常用的快速计算Hash的方法。下面我们来看看这种方法是怎样工作的。

假设五子棋的棋盘和Hash值定义为：

我们相应的定义一个Zorbrist数组

数组的第一维是玩家标识，可以定义黑棋为0，白棋为1。第二维和第三维表示棋盘。我们将ZorbistKey数组填满32位的随机数。

利用这个数组，我们可以很方便的基于一个局面计算它的后续局面的Hash值：

注意，我们定义棋盘上没有任何棋子的时候Hash值为0。

使用Zobrist数组，对于相差仅仅一步棋的两个局面，产生的Hash值也完全不同。所以这样的值用作Hash表的键值非常有效。在搜索根结点的时候把Hash值设成0，在搜索时通过调用子函数MakeMove()来更新Hash值，一直让它保持和当前局面同步。

对于刚才提到的HashChk，也是采用同样的方法计算的，不过要注意的是，用于生成HashChk的随机数组必须和生成HashKey的随机数组不同。

应用

1. 实现置换表（Transition Table），记录五子棋程序以前搜索过的局面。搜索过程中一旦在置换表中找到记录，就不用继续搜索了。
2. 记录开局库。当然，开局库并不一定用Hash的方式记录，也可以用树的方式记录。