lihongxun945/myblog

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

lihongxun945 opened this issue · 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。那么我们需要进行两部分操作:

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

首先对于第一条,比较简单,只要在落子和删除的时候调用 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设计教程第二版八:算杀

Zobrist算法的维基链接……

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

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

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

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