对弈类游戏的人工智能设计（2）：性能优化
发表于2016-06-08
GameRes游资网授权发布 文/mumuxinfei
上一篇着重讲述了评估函数+博弈树, 本文着重讲述学习算法, 以及性能优化问题。
一、学习算法
分析:
评估函数的引入, 为游戏AI提供了理论基础。
1 | G(s) = a1 * f1(s) + a2 * f2(s) + ... + an * fn(s) |
但评估函数的选定并非简单, 其面临的问题如下:
1、评估因素的选择, 如何挑选, 因素是否越多越好
2、对评估因素得分的归一化处理
3、如何进行合理的权重系数分配
这些都是需要思考和优化的地方, 归纳而言就是特征(因素)选择, 权重系数学习。
有人提到了强化学习, 通过与环境的交互反馈来学习模型，参见博文: "几种智能算法在黑白棋程序中的应用∗".
当然机器学习中的随机算法: 模拟退火/遗传算法, 也是有效的方式, 而且其更简单, 也更容易理解, 作者将在这边重点阐释。
遗传算法:
遗传算法(GA)是模拟自然界的进化过程而实现的。"物竞天择, 适者生成"是其永恒的定律。
首先让我们来定义个体向量(染色体):
1 | 评估函数各个特征的权重系数构成权重向量 (a1, a2, a3, ..., an), 视为个体向量 |
其必须满足的约束如下:
· 经变异/交叉操作后, 系数权重和不为1, 则归一化过程统一为:
1 | ai' = ai / ∑ ai (i = 0, 1, 2, ..., n) |
来定义操作子:
· 复制: 下一代拷贝上一代的权重系数向量即可
· 变异: 随机选定某个权重系数ai, 其值设定为某个(0~1)的随机值, 再进行归一化处理
· 交叉: 选定两个个体向量, 按概率进行对位权重系数交换, 再进行归一化处理。
适应度函数: 个体与其他个体的互相PK, 总得分即为其适应度值。
1、初始阶段: 选择N个随机值的向量个体
2、互相PK阶段: N个向量互相PK, 获取各自的适应度值
3、进化阶段: 按适应度值排序, 引入淘汰率/变异率等, 进行复制/变异/交叉操作, 诞生新的N个个体
持续迭代2), 3)两阶段, 直到选取合适的个体。
该过程能达到我们的学习需求, 当然我们可以继续做如下优化:
· 引入陪跑员机制: 依经验挑选精英个体, 参加PK阶段, 用于评估个体的适应度, 但不参与进化(复制, 变异, 交叉)过程。
· 按适应值概率进化: 防止群体中极少数适应度高的个体被复制和遗传而达到局部最优解的情况。
复制/变异/交叉的比率, 以及群体数, 都会影响迭代次数和收敛效果。
小结:
使用遗传算法进行参数学习后, 可以合理地分配权重系数, 那事先说好的特征挑选呢? 简而言之, 通过筛选掉权重系数近似为0的特征即可, ^_^。
二、博弈树优化
启发搜索:
博弈树本质是极大极小的求解过程, 而alpha+beta剪枝则加速该求解过程。
让我们来构建一个简单的alpha+beta剪枝用例:
注: 紫色代表极大值求解, 绿色代表极小值求解。
通过人工演算和模拟, 整个博弈过程, 成功地减少了3个节点的计算量的, 效果一般。
这个过程, 我们是否有优化的余地呢? 让我们调整下, 节点S1和S2的搜索顺序。
与调整顺序之前相比, 其alpha+beta剪枝的效果提升, 砍去了一个大分支, 减少了4个节点的计算量。
从这个例子中, 我们可以清晰的看到, 对于博弈树而言, 其alpha+beta的剪枝效果, 和搜索顺序是有一定关系的。 简单的总结: alpha+beta效果, 对搜素的顺序敏感。
于是我们找到了一个优化方向: 调整可行步的顺序, 并优先搜索预期高的分支。 该技巧命名为: 启发搜索。 常有人借助历史值, killer步来构造启发函数。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | // 负极大值算法int negamax(GameState S, int depth, int alpha, int beta) { // 游戏是否结束 || 探索的递归深度是否到边界 if ( gameover(S) || depth == 0 ) { return evaluation(S); } // 依据预估(历史, 经验)对可行步, 进行排序 sort (candidate list); // 遍历每一个候选步 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;} |
此时的核心算法结构中: 添加了可行步排序过程(sort (candidate list))。
当然该过程是有一定代价的, 在alpha+beta剪枝效果提升和排序损耗需要均衡和折中。 一般采用计算简单的预估函数即可。
让我们回到黑白棋AI, 我们可以简单选定, 预估函数等同于位置表, 即P(x, y) = Map(x, y)。 (Map 为 黑白棋棋面的位置重要度矩阵), 效果斐然。
置换表:
搞过ACM的人, 都知道DP求解的一种方式: 记忆化搜索。 本质就是把中间状态保存, 减少重复搜索的一种技巧。
置换表的核心思想基本一致: 状态保存, 减少重复搜索。
但置换表的难点不在于思想, 而在于状态保存。
具体可以分析如下:
1、游戏局面S本身占用空间大, 而且需要保存的状态S集合多, 因此需要一个转换函数F(S) => key, (key为不长二进制串, 或一个很大的整数)
2、转换后的key, 一一对应了某个具体局面S (冲突率很低可忽略, 或不存在)
让我们以黑白棋来做个例子, 局面转换为矩阵(0: 空白, 1: 黑棋, 2:白棋), 扁平化为字符串, 在借助强有力的Hash函数来转化。
这边展示了具体的流程, 其效果的好坏, 取决于Hash函数的选择。
简单采用MD5算法, 其实是可行的, 不过比较消耗CPU。 Zobrist hashing算法也是备受推荐。
和记忆化搜索相比, 置换表对应的局面是, 只是中间的预测节点, 因此该状态除了本身和游戏局面相关, 还和当前的搜索深度有关。
因此具体代码可修正如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | // 负极大值算法int negamax(GameState S, int depth, int alpha, int beta) { // 判断状态已存在于置换表中, 且搜索深度小于等于已知的, 则直接返回 if ( exists(TranspositionTable[S]) && TranspositionTable[S].depth >= depth ) { return TranspositionTable[S].value } // 游戏是否结束 || 探索的递归深度是否到边界 if ( gameover(S) || depth == 0 ) { return evaluation(S); } // 遍历每一个候选步 foreach ( move in candidate list ) { S' = makemove(S); value = -negamax(S', depth - 1, -beta, -alpha); // 保存S'到置换表中, 当depth更深时. TranspositionTable[S'] <= (depth, value) If TranspositionTable[S'].depth < depth unmakemove(S') if ( value > alpha ) { // alpha + beta剪枝点 if ( value >= beta ) { return beta; } alpha = value; } } return alpha;} |
总结:
启发搜索和置换表, 两者都是很好的思路, 前者通过调整搜索顺序来加速剪枝效果。 后者通过空间换时间。 总而言之, 这些都是博弈树上很常见的优化手段。 当然在具体游戏中, 需要权衡和评估。 下一篇讲讲出于游戏性的考虑, 如何进行优化和策略选择。