Zobrist 算法

Zobrist 是一个快速Hash算法，非常适合用在各种棋类游戏中（事实上也是在各种棋类游戏中有大量应用）。

我们前面讲了负极大值搜索，其实很多时候会有重复的搜索，比如这种：

  1. [7,7],[8,7],[7,6],[7,9]

其实它和下面这种的走法只是顺序不同 ，最终走出来的局面是一样的:

  1. [7,6],[7,9],[7,7],[8,7]

对于大部分棋类来说，并不关心你是如何到达这个局面的，只要当前局面上的棋子一样，局势就是一样的。

那么如果我们搜索中碰到了上面两种情况，我们会对两种情况都进行一次打分，而其实有了第一次的打分，完全可以缓存起来，第二次就不用打分直接使用缓存数据了。除了这种情况，其实以前的搜索结果也可以存下来，可以用在启发式搜索中。

那么现在的问题就是，我们应该怎么表示一种局面呢？显然需要通过一种哈希算法，而且这个算法不能太慢，不然可能反而会降低搜索速度。而 Zobrist 就是一种满足我们需求的快速数组哈希算法。关于Zobrist算法请参考 https://en.wikipedia.org/wiki/Zobrist_hashing

Zobrist 效率非常高，每下一步棋，只需要进行一次 异或 操作，相对于对每一步棋的打分来说，这一次异或操作带来的性能消耗可以忽略不计。Zobrist具体实现如下：

  • 初始化一个两个 Zobrist[M][M] 的二维数组，其中M是五子棋的棋盘宽度。当然也可以是 Zobrist[M*M] 的一维数组。设置两个是为了一个表示黑棋，一个表示白旗。
  • 上述数组的每一个都填上一个随机数，至少保证是32位的长度（即32bit)，最好是64位。初始键值也设置一个随机数。
  • 每下一步棋，则用当前键值异或Zobrist数组里对应位置的随机数，得到的结果即为新的键值。如果是删除棋子（悔棋），则再异或一次即可。

对应的JS代码如下：

zobrist.js

  1. import R from "./role.js"
  2. import Random from "random-js"
  4. var Zobrist = function(size) {
  5.   this.size = size || 15;
  6. }
  8. Zobrist.prototype.init = function() {
  9. this.com = [];
  10.   this.hum = [];
  11.   for(var i=0;i<this.size*this.size;i++) {
  12. this.com.push(this._rand());
  13.     this.hum.push(this._rand());
  14.   }
  16.   this.code = this._rand();
  17. }
  19. var engine = Random.engines.mt19937().autoSeed()
  21. Zobrist.prototype._rand = function() {
  22.   return Random.integer(1, 1000000000)(engine);  //再多一位就溢出了。。
  23. }
  25. Zobrist.prototype.go = function(x, y, role) {
  26.   var index = this.size * x + y;
  27.   this.code ^= (role == R.com ? this.com[index] : this.hum[index]);
  28.   return this.code;
  29. }
  31. var z = new Zobrist();
  32. z.init();
  34. export default z;

源码在 zobrist.js 文件里。

注意每次走棋都要进行一次zobrist操作。千万不要自行设计哈希函数，除非你能保证你的哈希函数比一次64位整数的异或操作更简单，并且同时证明冲突的概率很低。Zobrist数组中的随机数的 质量 很重要，因此我并没有采用JS内置的 Math.random() 函数，而是使用了一个第三方的高质量随机函数库。

有了这个快速hash算法，我们就可以通过一个64位的整数来表示一个棋局。那么我们应该存储哪些信息，以及合适取出来用呢？

集成 Zobrist

我们在 negamax 搜索的过程中，会把搜索结果存储在 置换表中，存储的key就是 zobrist的key。那么我们需要进行两部分操作：

  1. 每当有添加或者删除棋子的时候，更新 zobrist 值
  2. 在搜索的时候存储结果，在合适的时候取出来使用。

首先对于第一条，比较简单，只要在落子和删除的时候调用 zobrist 即可：

  1. put (p, role) {
  2.     this.board[p[0]][p[1]] = role
  3.     this.zobrist.go(p[0], p[1], role)
  4.     // ...
  5.   }
  7.   //移除棋子
  8.   remove (p) {
  9.     var r = this.board[p[0]][p[1]]
  10.     this.zobrist.go(p[0], p[1], r)
  11.     //...
  12.   }

这样每当我们的棋盘有变动的时候，zobrist 模块会自动更新自己的 key

然后我们需要在搜索的时候能存储和使用结果，基本思路是：
1, 每当搜索完成一个节点，我们就把结果存储在置换表中
2, 当开始搜索一个节点的时候，尝试从置换表取出结果，取到了就直接使用

但是有一点要注意，就是搜索深度的问题，如果我们搜索点 p，需要一个往下搜 4 层的结果，但是我们存储的是 2 层搜索的结果，那么显然不满足我们的要求，因为搜索深度不够，结果不够准确。因此我们需要考虑搜索深度：

1, 每当搜索完成一个节点，我们就把结果存储在置换表中，同时把搜索深度也存进去
2, 当开始搜索一个节点的时候，尝试从置换表取出结果，取到了就比较搜索深度，大于等于当前深度我们就是使用，否则就放弃。、

实现代码如下：

  1. var r = function(deep, alpha, beta, role, step, steps, spread) {
  3.   if(config.cache) {
  4.     var c = Cache[board.zobrist.code]
  5.     if(c) {
  6.       if(c.deep >= deep) { // 如果缓存中的结果搜索深度不比当前小，则结果完全可用
  7.         cacheGet ++
  8.         // 记得clone，因为这个分数会在搜索过程中被修改，会使缓存中的值不正确
  9.         return {
  10.           score: c.score.score,
  11.           steps: steps,
  12.           step: step + c.score.step,
  13.           c: c
  14.         }
  15.     }
  16.   }
  18.   var _e = board.evaluate(role)
  20.   var leaf = {
  21.     score: _e,
  22.     step: step,
  23.     steps: steps
  24.   }
  25.     return leaf
  26.   }
  28.   var best = {
  29.     score: MIN,
  30.     step: step,
  31.     steps: steps
  32.   }
  33.   // 双方个下两个子之后，开启star spread 模式
  34.   var points = board.gen(role, step > 1, step > 1)
  36.   if (!points.length) return leaf
  38.   config.debug && console.log('points:' + points.map((d) => '['+d[0]+','+d[1]+']').join(','))
  39.   config.debug && console.log('A~B: ' + alpha + '~' + beta)
  41.   for(var i=0;i<points.length;i++) {
  42.     var p = points[i]
  43.     board.put(p, role)
  45.     var _deep = deep-1
  47.     var _spread = spread
  49.     var _steps = steps.slice(0)
  50.     _steps.push(p)
  51.     var v = r(_deep, -beta, -alpha, R.reverse(role), step+1, _steps, _spread)
  52.     v.score *= -1
  53.     board.remove(p)
  56.     // 注意，这里决定了剪枝时使用的值必须比MAX小
  57.     if(v.score > best.score) {
  58.       best = v
  59.     }
  60.     alpha = Math.max(best.score, alpha)
  61.     //AB 剪枝
  62.     // 这里不要直接返回原来的值，因为这样上一层会以为就是这个分，实际上这个节点直接剪掉就好了，根本不用考虑，也就是直接给一个很大的值让他被减掉
  63.     // 这样会导致一些差不多的节点都被剪掉，但是没关系，不影响棋力
  64.     // 一定要注意，这里必须是 greatThan 即 明显大于，而不是 greatOrEqualThan 不然会出现很多差不多的有用分支被剪掉，会出现致命错误
  65.     if(math.greatOrEqualThan(v.score, beta)) {
  66.       config.debug && console.log('AB Cut [' + p[0] + ',' + p[1] + ']' + v.score + ' >= ' + beta + '')
  67.       ABcut ++
  68.       v.score = MAX-1 // 被剪枝的，直接用一个极大值来记录，但是注意必须比MAX小
  69.       v.abcut = 1 // 剪枝标记
  70.       // cache(deep, v) // 别缓存被剪枝的，而且，这个返回到上层之后，也注意都不要缓存
  71.       return v
  72.     }
  73.   }
  75.   cache(deep, best)
  77.   //console.log('end: role:' + role + ', deep:' + deep + ', best: ' + best)
  78.   return best
  79. }
  81. var cache = function(deep, score) {
  82.   if(!config.cache) return false
  83.   if (score.abcut) return false // 被剪枝的不要缓存哦，因为分数是一个极值
  84.   // 记得clone，因为score在搜索的时候可能会被改的，这里要clone一个新的
  85.   var obj = {
  86.     deep: deep,
  87.     score: {
  88.       score: score.score,
  89.       steps: score.steps,
  90.       step: score.step
  91.     },
  92.     board: board.toString()
  93.   }
  94.   Cache[board.zobrist.code] = obj
  95.   // config.debug && console.log('add cache[' + board.zobrist.code + ']', obj)
  96.   cacheCount ++
  97. }

下一篇：五子棋AI设计教程第二版八：算杀