七：Zobrist缓存

您所在的位置：网站首页 › 五子棋没意思 › 七：Zobrist缓存

七：Zobrist缓存

2024-05-23 14:17| 来源: 网络整理| 查看: 265

Zobrist 算法集成 ZobristZobrist 算法

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= 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 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缓存

七：Zobrist缓存

今日新闻

推荐新闻