五子棋AI教程第二版七：Zobrist 置换表

Question

五子棋AI教程第二版七：Zobrist 置换表

lihongxun945 opened this issue 6 years ago · 6 comments

Zobrist 算法

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

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

[7,7],[8,7],[7,6],[7,9]

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

[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

import R from "./role.js"
import Random from "random-js"

var Zobrist = function(size) {
  this.size = size || 15;
}

Zobrist.prototype.init = function() {
this.com = [];
  this.hum = [];
  for(var i=0;i<this.size*this.size;i++) {
this.com.push(this._rand());
    this.hum.push(this._rand());
  }

  this.code = this._rand();
}

var engine = Random.engines.mt19937().autoSeed()

Zobrist.prototype._rand = function() {
  return Random.integer(1, 1000000000)(engine);  //再多一位就溢出了。。
}

Zobrist.prototype.go = function(x, y, role) {
  var index = this.size * x + y;
  this.code ^= (role == R.com ? this.com[index] : this.hum[index]);
  return this.code;
}

var z = new Zobrist();
z.init();

export default z;

源码在 zobrist.js 文件里。

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

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

集成 Zobrist

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

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

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

put (p, role) {
    this.board[p[0]][p[1]] = role
    this.zobrist.go(p[0], p[1], role)
    // ...
  }

  //移除棋子
  remove (p) {
    var r = this.board[p[0]][p[1]]
    this.zobrist.go(p[0], p[1], r)
    //...
  }

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

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

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

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

实现代码如下：

var r = function(deep, alpha, beta, role, step, steps, spread) {

  if(config.cache) {
    var c = Cache[board.zobrist.code]
    if(c) {
      if(c.deep >= deep) { // 如果缓存中的结果搜索深度不比当前小，则结果完全可用
        cacheGet ++
        // 记得clone，因为这个分数会在搜索过程中被修改，会使缓存中的值不正确
        return {
          score: c.score.score,
          steps: steps,
          step: step + c.score.step,
          c: c
        }
    }
  }

  var _e = board.evaluate(role)

  var leaf = {
    score: _e,
    step: step,
    steps: steps
  }
    return leaf
  }
  
  var best = {
    score: MIN,
    step: step,
    steps: steps
  }
  // 双方个下两个子之后，开启star spread 模式
  var points = board.gen(role, step > 1, step > 1)

  if (!points.length) return leaf

  config.debug && console.log('points:' + points.map((d) => '['+d[0]+','+d[1]+']').join(','))
  config.debug && console.log('A~B: ' + alpha + '~' + beta)

  for(var i=0;i<points.length;i++) {
    var p = points[i]
    board.put(p, role)

    var _deep = deep-1

    var _spread = spread

    var _steps = steps.slice(0)
    _steps.push(p)
    var v = r(_deep, -beta, -alpha, R.reverse(role), step+1, _steps, _spread)
    v.score *= -1
    board.remove(p)
 

    // 注意，这里决定了剪枝时使用的值必须比MAX小
    if(v.score > best.score) {
      best = v
    }
    alpha = Math.max(best.score, alpha)
    //AB 剪枝
    // 这里不要直接返回原来的值，因为这样上一层会以为就是这个分，实际上这个节点直接剪掉就好了，根本不用考虑，也就是直接给一个很大的值让他被减掉
    // 这样会导致一些差不多的节点都被剪掉，但是没关系，不影响棋力
    // 一定要注意，这里必须是 greatThan 即 明显大于，而不是 greatOrEqualThan 不然会出现很多差不多的有用分支被剪掉，会出现致命错误
    if(math.greatOrEqualThan(v.score, beta)) {
      config.debug && console.log('AB Cut [' + p[0] + ',' + p[1] + ']' + v.score + ' >= ' + beta + '')
      ABcut ++
      v.score = MAX-1 // 被剪枝的，直接用一个极大值来记录，但是注意必须比MAX小
      v.abcut = 1 // 剪枝标记
      // cache(deep, v) // 别缓存被剪枝的，而且，这个返回到上层之后，也注意都不要缓存
      return v
    }
  }

  cache(deep, best)
  
  //console.log('end: role:' + role + ', deep:' + deep + ', best: ' + best)
  return best
}

var cache = function(deep, score) {
  if(!config.cache) return false
  if (score.abcut) return false // 被剪枝的不要缓存哦，因为分数是一个极值
  // 记得clone，因为score在搜索的时候可能会被改的，这里要clone一个新的
  var obj = {
    deep: deep,
    score: {
      score: score.score,
      steps: score.steps,
      step: score.step
    },
    board: board.toString()
  }
  Cache[board.zobrist.code] = obj
  // config.debug && console.log('add cache[' + board.zobrist.code + ']', obj)
  cacheCount ++
}

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

Answer 1 · 2018-07-20T01:32:12.000Z

Zobrist算法的维基链接……

Answer 2 · 2018-07-20T01:42:28.000Z

@lance6716 已更正

Answer 3 · 2019-09-09T13:49:51.000Z

在negamax.js中，var Cache = {}，var c = Cache[board.zobrist.code]，c.deep >= deep。有这样的代码，第一句我知道，是建立一个空对象。这个问题可能有点蠢，但博主能不能解释下第二句什么意思呀。没接触过JS，基本都看懂了，但这块一直看不懂。拜托🙏

Answer 4 · 2019-09-10T02:59:41.000Z

@SuperSocks 没看懂你的问题，你是说 var c = Cache[board.zobrist.code] 看不懂么，这就是一个简单的取值

Answer 5 · 2019-09-10T03:40:43.000Z

我不懂的是，Cache是一个空对象，Cache[board.zobrist.code] 取的是什么值，谢谢博主

Answer 6 · 2019-09-10T03:51:28.000Z

抱歉抱歉我懂了博主，之前有些特性不了解