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.sizethis.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. }