五子棋人机对战(无禁手)

试玩

https://lilei-c.github.io/gobang/dist/index.html

从零开始

评估函数

• 电脑能下棋的前提是它能对当前局面做出评估, 比如某一方五子相连就是赢了, 双三就快赢了, 有多个活二则大概率赢
• 尝试每一个可以落子的位置, 完了评估局面优劣, 最终选择对自己有利的局面
• 几乎不可能设计一个完美的评估函数, 只能尽量准确
• 评估函数的准确程度, 从根本上决定了电脑的棋力

深度搜索

• 只考虑一步棋, 这不智能
• 如果电脑算力无限大, 落子时, 考虑后续每一个局面直至终局, 则电脑必能走出完美着法
• 然而, 对于 15*15 的棋盘, 穷举带来的指数增长, 电脑无能为力
• minimax 算法, 在有限的步骤中, 双方同样聪明, 总能选择对自己最有利, 对对方最不利的着法
• 如果双方真的同样聪明, 那就很难分出胜负了, 所以关键是, 默认对手和自己同样聪明, 如果他没那么聪明, 那他大概率会输
• 对电脑而言聪明指的是评估函数的准确性

Alpha-Beta 剪枝

看图更好理解 https://baike.baidu.com/item/Alpha-Beta%E7%AE%97%E6%B3%95

• 基于 minimax 的改进, 减少搜索次数, 不会降低棋力
• Alpha 剪枝: 当 max 节点在一个分支中获得分数 N 时, 那么在该分支的兄弟分支中, 当 min 节点获得一个小于 N 的分数 M 时, 则整个 min 节点的后续不必再搜索, 因为无论后续如何 min 也只会选择 M 或比 M 更小的分数, 已经不可能获得比 N 更大的分数了
• Beta 剪枝: 和 Alpha 同样的原理, 当 min 节点从 a 分支 获得分数 N 后, 在搜索 a 的兄弟时, 如果出现大于 N 的分数, 则该兄弟分支不用继续搜索

启发式搜索

• 单纯增加 AB 剪枝 (随机搜索子节点), 已经可以节省几倍算力, 但对指数增长来说几倍比较乏力
• 如果从最优节点开始搜索, 可以将搜索节点数从 N 降低到 根号 N
• 实际上, 不可能评估出最优节点, 如果能那就不用深度搜索了:)
• 即使只是大致的评估, 也能极大提高剪枝效率
• 好的开局和评估函数更重要, 单纯增加搜索深度棋力不一定提高
• 如果对子节点打分排序后, 只选择有限的子节点继续搜索, 能增加搜索深度, 与此同时, 棋力会相当依赖打分是否合理
• 在某个版本的测试中, 搜素 6 层 选取 40 个子节点, 棋力高于 8 层 30 节点

以下验证数据, 并不精确, 但能看到实际评估节点已达到 根号 N 的数量级, 效果明显

随机排序

搜索深度	候选棋子数	全部节点	评估节点	直接剪掉节点	实际剪掉节点
4	15	50625	8365	824	42260
4	20	160000	31485	2535	128515

按价值排序

搜索深度	候选棋子数	全部节点	评估节点	直接剪掉节点	实际剪掉节点
4	15	50625	813	127	49812
4	20	160000	760	551	159240

算杀

• 尝试在类似冲四连续进攻, 对方只能被迫防守的情况下获胜
• 因为连续进攻需要考虑的棋子数很少, 所以这一步可以搜索的非常深
• 实际很少会搜索到最终的深度, 连续进攻不是一直有的:)
• 棋力提升程度并不高, 对于普通玩家来说, 算杀相当厉害, 对于高手来说, 很难有冲杀的机会
• 算杀是一个对方失误时的冲杀利器; 对于下出好的盘中, 算杀没有任何帮助, 还是得看评估函数

缓存 / zobrist hash

• 在深度搜索的过程中, 会出现搜索重复局面的情况
• 例如这两种落子方式, 方式 1: 黑(8,7) 白(8,8) 黑(8,9) 方式 2: 黑(8,9) 白(8,8) 黑(8,7) 它们形成的局面是相同的
• 搜索深度影响缓存效率, 越深重复概率越大, 缓存越有用
• 启发函数影响缓存效率, 剪枝效率越高, 重复概率越小, 缓存越没用
• 实际测试中, 当搜索深度为 4 ~ 6 层时, 节省时间约 0% ~ 20% , 8 层时约 10% ~ 50%

开局库

• 待补充

性能优化

• js 基础
• 位操作总是性能最优, 但编码上会复杂一点, 合理取舍
• 避免字符串拼接
• 必要时, 尝试用数组/类型化数组 代替 Object/Map
• 数组的 unshift 比 push 慢约 7 倍
• for 快于 forEach, for of
• for 快于 while
• 算法相关
• 深度搜索时, 在同一棋盘实例上下棋再回滚更优, 不要生成终端节点实列
• 不必全局遍历, 优先选择可能的位置, 也有利于充分利用 alphabeta 剪枝

测试性能的误区

为了测试可能会这样写
for(var i=0;i<10000;i++){ ... }

这里可能存在问题, 例如 hashmap 取值

单纯 for 循环去读取同一个属性值, 会有缓存或者自动优化,
尝试一个多层的 Object/Map 每次取不同的属性值, 性能会直线下降