前⾔:
对弈类游戏的智能算法, ⽹上资料颇多, ⼤同⼩异. 我写这篇⽂章, 并⾮想做互联⽹的搬运⼯. ⽽是想对当年的经典<<PC游戏编程(⼈机博弈)>>表达敬意, 另⼀⽅⾯, 也想对⾃⼰当年的游戏编程⼈⽣做下回顾.
这边我们以⿊⽩棋游戏为例, 从博弈和学习两⽅⾯来阐述游戏AI的编写要点. 本⽂侧重于讲述博弈(评估函数+博弈算法).
热泵热水
博弈：
以前看围棋⽐赛, 常有⼈评价棋⼿⽔平⾼: ⼤局观强(评估局⾯好), 算路精准(计算步数深, 实战效果好). 他⼭之⽯可以攻⽟, 对弈类游戏的AI 本质上也是在评估局⾯, 博弈深度这两点上做⾜了⽂章. (⼀)评估函数： 让我们先来谈谈局⾯评估, 那如何从程序的⾓度去合理评估游戏的局势呢? ⾸先局⾯的好坏, 需要综合考虑多个因素(权重不同, 不同阶段重要性的变化), 其次因素影响⼒需转化为数值来衡量. 为了简化模型, 我们引⼊评估函数G(s), s为当前的局⾯, G(s)为当前局⾯的评估值. 1G(s) = a1 * f1(s) + a2 * f2(s) + ... + an * fn(s)精密电主轴
at89s52最小系统 注: fi(s)为某个评估因素的得分, ai为某个评估因素的权重⽐ 评估函数G(s)的引⼊, 为游戏AI的智能引⼊了数学模型, 也是⼀切的基础. 回到⿊⽩棋游戏本⾝, 依据经验选定如下特征评估因素: 1).地势估值表 ⿊⽩棋和围棋⼀样, 也遵守着"⾦⾓银边烂肚⽪"的定律, 四个⾓的地势值⾮常⼤, 其次是四条边. 因此我们再给8*8地图点分配地势值时, ⼤体满⾜⾓边重, 中腹轻的模式.
1potential_enegy(s) = ∑ pe[x, y] {map[x,y] is occupied, 8>x>=0, 8>y>=0}
注: potential_enegy(s) 为地势评估函数, pe[x,y] 为地势估值矩阵, map[x,y]是游戏地图本⾝. 2).⾏动⼒ 基于这样的假设: 在某局⾯中, 选择多, 则灵活主动, ⽽选择少, 则往往陷⼊被动. 因此选择多少, 就成为了评估局⾯好坏的参考因素了. 于是我们把⾯对某⼀局⾯, 可以落⼦的个数, 称之为⾏动⼒. 3).稳定⼦ 所谓稳定⼦, 是指⽆论如何, 都不可能被翻覆的⼦, 最简单的稳定⼦就是4个⾓点, 稳定值越多, 获胜的⼏率就越⼤.
有了这些评估因素后, 再赋予⼀定的权重系数, 评估函数就⽐较完善了. 此时游戏的AI也基本构建完毕, 其棋⼒能击败初学者, 应该不成问题.
但此时的AI很脆弱, 看似每步都选择最佳落⼦, 却很容易落⼊陷阱. 这就是贪⼼算法, 导致的局部最优陷阱. 如何破这个局呢? 期待王者到来: 博弈树. (⼆)博弈树： 博弈树本质就是极⼤极⼩的搜索过程，相关资料可参考博⽂: "". 极⼤极⼩的算法, 分⽀繁多⽽冗余, 于是引⼊alpha+beta剪枝做优化, 它
可以快速裁剪不必要的搜索分⽀, 提⾼搜索效率. 关于这块, 就不再具体展开, 参见如下博⽂: , ; alpha+beta剪枝的极⼤极⼩过程⽰意图:
负极⼤值算法伪码:
1
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21// 负极⼤值算法
int negamax(GameState S, int depth, int alpha, int beta) { // 游戏是否结束 || 探索的递归深度是否到边界
if( gameover(S) || depth == 0 ) {
return evaluation(S);
}
// 遍历每⼀个候选步
foreach ( move in candidate list ) {
S' = makemove(S);
value = -negamax(S', depth - 1, -beta, -alpha);
unmakemove(S')
if( value > alpha ) {
// alpha + beta剪枝点乳鸽养殖
if( value >= beta ) {
射击标靶return beta;
}
alpha = value;
}
连续供墨打印机}
return alpha;
}
展望:
有了评估函数和博弈树后, 其游戏AI有了飞跃的进步, 但⼀⼭更有⼀⼭⾼, 我们是否能够更进⼀步呢? 对于评估函数, 我们当前的策略是基于经验, 选择评估因素和权重分配. 能否⽤机器学习的⽅法,⾃动实现因素(特征)选择, 权重系数合理分配呢? ⽽对于博弈算法本⾝, 是否还有优化的地⽅? 搜索深度和搜索分⽀的⼴度如何权衡? 最重要的如何设置进阶的AI难度, 增强⽤户的体验? 因篇幅受限, 决定放到下⼀篇博⽂中.
总结:
为何选择⿊⽩棋作为对弈类游戏AI解说的对象, ⼀⽅⾯游戏规则简单, 另⼀⽅⾯其评估模型容易构建, 且其搜索分⽀少+搜索深度深, 这些对快速实现并理解博弈游戏的AI核⼼算法有⾮常⼤的帮助. 该博⽂主要讲述了评估函数和博弈树的原理和优化. 下⽂讲着重讲述下博弈游戏的AI如何学习, 以及性能优化的进阶篇.
写在最后： 如果你觉得这篇⽂章对你有帮助, 请⼩⼩打赏下. 其实我想试试, 看看写博客能否给⾃⼰带
来⼀点⼩⼩的收益. ⽆论多少, 都是对楼主⼀种由衷的肯定.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议