试玩
https://lilei-c.github.io/gobang/dist/index.html
- 电脑能下棋的前提是它能对当前局面做出评估, 比如某一方五子相连就是赢了, 双三就快赢了, 有多个活二则大概率赢
- 尝试每一个可以落子的位置, 完了评估局面优劣, 最终选择对自己有利的局面
- 几乎不可能设计一个完美的评估函数, 只能尽量准确
- 评估函数的准确程度, 从根本上决定了电脑的棋力
- 只考虑一步棋, 这不智能
- 如果电脑算力无限大, 落子时, 考虑后续每一个局面直至终局, 则电脑必能走出完美着法
- 然而, 对于 15*15 的棋盘, 穷举带来的
指数增长
, 电脑无能为力 minimax
算法, 在有限的步骤中, 双方同样聪明, 总能选择对自己最有利, 对对方最不利的着法- 如果双方真的同样聪明, 那就很难分出胜负了, 所以关键是, 默认对手和自己同样聪明, 如果他没那么聪明, 那他大概率会输
- 对电脑而言
聪明
指的是评估函数的准确性
看图更好理解 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 |
- 尝试在类似冲四连续进攻, 对方只能被迫防守的情况下获胜
- 因为连续进攻需要考虑的棋子数很少, 所以这一步可以搜索的非常深
- 实际很少会搜索到最终的深度, 连续进攻不是一直有的:)
棋力提升程度
并不高, 对于普通玩家来说, 算杀相当厉害, 对于高手来说, 很难有冲杀的机会- 算杀是一个对方失误时的冲杀利器; 对于下出好的盘中, 算杀没有任何帮助, 还是得看
评估函数
- 在深度搜索的过程中, 会出现搜索重复局面的情况
- 例如这两种落子方式, 方式 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 每次取不同的属性值, 性能会直线下降