模式的编码

11.4　模式的编码

谈到编码，最简单的就是直观的对模式进行编码，如图11.6（f）中的模式，我们只表示除了中心点外的8个点，其中黑为1，白为2，则可以编码为00102201，将其转换为二进制或十六进制后则可仅用一个32位的整数便可表示。

如图11.2、图11.3和图11.4所示的眼的模式，每个模式下面的字串就是该模式的编码。在该编码中，我们不仅考虑了颜色，也考虑到了边界信息，而且一个棋子是否落在边界上其编码是不同的；而且，对于棋盘外部，我们也假设是有棋盘线的，只是编码和棋盘上真实空点的编码不同，这样处理主要有两个好处，一是可以让所有模式编码位数一致，在匹配时比较方便；二是让模式的内容更加准确，一个模式是否临棋盘的边角，其应对是不尽相同的。

在上例中，我们做了如下编码，空为0＝000，黑为1＝001，白为2＝010，棋盘外面为3＝011，一个棋子如果落在棋盘边框上则对其编码加4＝100，因而，边框上的黑为5＝101，边框上的白为6＝110。对于3×3的模式，需要有8个数字来表示，每个数字如果转换成二进制则占3位，因而，总共占3×8＝24位，正好可以用一个整型来表示。

前面提到，每个模式有16种等价的变形，如果只考虑一种颜色也是8种等价形，这就需要将其所有等价形式转换成一个统一的形式做个等价转换。在处理模式时，我们通常的处理是，抓取出一个模式之后，如果是通过白棋生成的模式，那么首先转换成黑棋，之后算出其等价的8个编码，最后取最小的那个数值作为该模式的编码。

如果采用这种编码方式，对于3×3的模式还可以表示，但如果再大一些的模式，就难以用一个整数来表示，当对速度要求较高的时候，如果不能将模式用一个整数编码，那么模式就会成为影响效率的一个较大的障碍。为了能在一个整数范围内表示更加复杂的模式，就需要采用一种并非一对一的哈希算法，Zobrist哈希就是这样一种专门针对棋类游戏进行哈希编码的算法，可以在保证较低的冲突率的基础上，实现将整个棋盘映射到一个整数上。