人工智能一种现代方法第5章对抗搜索

博弈

对抗搜索&＃xff1a;竞争环境中每个Agent的目标之间是有冲突的&＃xff0c;也成为博弈。
博弈&＃xff1a;有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏。
剪枝&＃xff1a;在搜索树中忽略那些不影响最后决定的部分。
启发式评估函数&＃xff1a;在不进行完全搜索的情况下估计某些状态的真实效用值。
效用函数&＃xff08;目标函数、收益函数&＃xff09;UTILITY(s,p)&＃xff1a;定义游戏者p在终止状态下的数值。

博弈中的优化决策

考虑一个Max和Min两个人的下棋问题&＃xff1a;
最优解&＃xff1a;到达目标状态的一系列行动
中止状态&＃xff1a;一方取胜
极小极大值&＃xff1a;可以理解为有两个人MAX和MIN&＃xff0c;MAX喜欢移动到有极大值的地方&＃xff0c;MIN喜欢移动到有极小值的地方&＃xff0c;终端状态由效用函数进行评价。MAX指向有最高极小极大值的中止状态。假设对手的决策均为最优。

上图中&＃xff0c;终止结点是Max的效用值&＃xff1b;其他结点旁标的数字是Max和Min的极小极大值。Max在根节点的最佳行棋是a1&＃xff0c;因为它指向有最高极小极大值的后继&＃xff0c;而Min此时的最佳行棋是b1&＃xff0c;因为它指向有最低的极小极大值的后继。

给定一棵博弈树&＃xff0c;最优策略可以通过检查每个结点的极小极大值来决定&＃xff0c;记作MINmAX(s)。MAX喜欢移动到有极大值的地方&＃xff0c;MIN喜欢移动到有极小值的地方。根据上述博弈树可得到如下公式。

Minmax算法(极小极大算法)

极小极大算法从当前状态计算极小极大决策。它使用了简单的递归算法计算每个后继的极小极大值。递归算法自上而下一直前进到树的叶子节点&＃xff0c;递归回溯通过搜索树把极小极大值回传。
理解&＃xff1a;每一步都是最小化敌方的最大收益。

多人博弈时的最优决策

超过两个人的博弈利用MINIMAX算法&＃xff0c;由于之前研究的两人博弈一方得分可以反应另一方得分&＃xff0c;故仅用一个数值表示状态得分&＃xff0c;对于多人游戏&＃xff0c;应该使用向量值替换单一效用值。每个节点的回传至是该选手在节点的后继者效用值向量中选择的结果。

多人博弈通常会涉及在游戏选手之间出现正式或非正式联盟的情况。

α-β剪枝&＃xff08;重点&＃xff09;

极大极小值搜索时间复杂度呈指数级增加&＃xff0c;α-β剪枝可以将复杂度减半&＃xff0c;很多情况下可以剪裁掉整个子树。

在某节点的父节点有更好的选择&＃xff0c;则不会探索到该节点。

• α&＃xff1a;到目前为止路径上发现的MAX的最佳选择&＃xff08;极大值&＃xff09;
• β&＃xff1a;到目前为止路径上MIN的最佳选择&＃xff08;极小值&＃xff09;

此技术应用到标准的极小极大搜索树上&＃xff0c;会剪掉那些不可能影响决策的分支。比α小则停止探索&＃xff0c;比β大则停止探索。

一个α-β剪枝实例
目标&＃xff1a;判断下图中根节点的决策是走到BCD中的哪一个结点。

过程如下

选择B的子节点下最小的值3&＃xff0c;即B的值至多为3&＃xff0c;返回给A,A的α值变为3&＃xff0c;即根节点的值至少为3

C下面的第一个叶子结点值为2&＃xff0c;表示C这个Min结点的值至多为2&＃xff0c;不过已经知道了B点值是3&＃xff0c;所以Max不会选择C。故可不用考虑C的其他结点了&＃xff0c;可以剪枝

D下面的第一二个结点的值分别为14,5。因此&＃xff0c;都要进行搜索。第3个结点值为2&＃xff0c;故D这个Min结点的值至多是2&＃xff0c;所以Max结点&＃xff08;根节点&＃xff09;的决策是走到值为3的B结点。

上述过程可以看作是对MinMax公式的简化。如上述过程中C的两个没有计算的子节点的值是x和y。根结点的值计算如下&＃xff1a;

在以下情况下&＃xff0c;α-β的增益最大&＃xff1a;

• 如果以增加备份值的方式对Min节点的Max子节点进行升序排序&＃xff0c;则效果更好。例如&＃xff0c;对D这个Min结点的子节点进行从小到大排序2、5、14&＃xff0c;则可以不计算结点5、14。
• 如果对Max结点的Min结点进行降序排序&＃xff0c;则效果更好。

这种情况下&＃xff0c;α-β算法可以裁掉其中的一大部分&＃xff0c;只需要检查O(b^(m/2))个结点来做出决策&＃xff0c;其中&＃xff0c;b是决策深度
极小极大算法搜索整个博弈空间&＃xff0c;需要检查的结点数为O(b^m)
如果后继状态采用随机顺序而不是最佳优先的顺序&＃xff0c;那么α-β算法需要检查的总结点数大约是O(b^(3m/4 ))&＃xff0c;采用最佳优先排序时只需检查O(b^(m/2))个结点

不完美的实时决策

由于实时决策允许的模拟时间很短&＃xff0c;故需要尽早截断搜索、将启发式评估函数用于搜索。
启发式评估函数EVAL&＃xff08;可以评估中间状态&＃xff09;–替代效用函数
用决策什么时候运用EVAL的截断测试(cutoff test)–替代终止测试

评估函数

①对终止状态的排序应该和真正的效用函数的排序结果一样
②评估函数的计算成本不能花费太长时间
③对于非终止状态&＃xff0c;评估函数应该和取胜几率密切相关

截断搜索

最简单的节点搜索&＃xff1a;设置固定的搜索深度
地平线效应&＃xff1a;当好棋出现在固定搜索深度之后时&＃xff0c;无法探索到好棋

向前剪枝

向前剪枝&＃xff1a;在某节点上无需进一步考虑而直接剪枝一些节点
柱搜索&＃xff1a;只考虑最好的n步行棋&＃xff0c;但无法保证最好的行棋不被剪枝掉

资源分享

实验代码下载&＃xff1a;
https://github.com/yyl424525/AI_Homework
人工智能-一种现代方法中文第三版pdf、课件、作业及解答、课后习题答案、实验代码和报告、历年考博题下载&＃xff1a;https://download.csdn.net/download/yyl424525/11310392