《湖南大学人工智能课件5》由会员分享，可在线阅读，更多相关《湖南大学人工智能课件5（32页珍藏版）》请在金锄头文库上搜索。
1、第五章 对抗搜索,内容提要,博弈 -剪枝 不完美的实时决策 随机博弈 部分可观察的博弈 发展现状,博弈,竞争环境中多个agent之间的目标是有冲突的，称为对抗搜索问题，也称为博弈 博弈 有完整信息的，确定的，轮流行动的，两个游戏者的零和游戏,如国际象棋 难于求解 注重时间效率,两个人之间的游戏,游戏表示成搜索问题 S0初始状态 Player(s)谁行动 Action(s)状态下的合法移动集合 Result(s,a)转移模型 Terminal-test(s):终止测试 Utility(s,p):效用函数,博弈树,零和游戏 叶子结点表示结果 赢:1 输:-1 和:0,博弈中的优化决策,博弈树的最优
2、策略通过检查每个结点的极大极小值来决定：minimax(n) Max喜欢移动到有极大值的状态，min喜欢移动到有极小值的状态,极小极大算法,极小极大算法,3,极小极大算法,完备性？ 最优性？ 时间复杂度？ 空间复杂度？,多人博弈,与两人博弈的不同 用向量值取代单一值 通常选择使自己效用值最大的行为 联盟与破坏联盟,-剪枝,游戏状态数目的增长是指数级的 通过剪枝来消除对部分分支的搜索，且被剪掉的分支不影响最终的决策,-剪枝, - 剪枝,-剪枝,-剪枝,-剪枝的效率很大程度上依赖于检查后继状态的顺序 最佳剪枝情况下可以将时间复杂度从极大极小算法的O(bm)减少到O(bm/2)，采用随机顺序检查的总
3、结点数大约是O(b3m/4),资源限制,当遇到大的问题的时候搜索空间是非常大的 解决问题的方法： 截断测试 限制搜索深度或搜索时间 评估函数 评估当前位置的有效性值,评估函数,评估函数的定义准则： 对于终止状态的排序应该和效用函数一致 计算时间不能太长 对于非终止状态应该和取胜几率相关,评估函数,评估函数的效率值可能被映射到多个终止状态 用终止状态的概率值来表示当前状态的期望值 0.72*1+0.2*0+0.08*(-1)=0.76,评估函数,对于国际象棋问题，典型的评估函数是线性加权评估： Eval(s) = w1f1(s) + w2f2(s) + + wnfn(s) Eg. w1=9, f
4、1=(白棋皇后数量)-(黑棋皇后数量) 线性评估假定特征之间是独立的，然而实际中特征之间具有关联性，比如国际象棋在残局中2个象比单个象的价值要高出2倍,截断搜索, Environment: Patient, hospital, staff Actuators: Screen display (questions, tests, diagnoses, treatments, referrals) Sensors: Keyboard (entry of symptoms, findings, patients answers),在-剪枝算法中 Terminal-test 被替换程cutoff-te
5、st(state,depth) Utility被替换程eval(state) cutoff-test(state,depth)截断策略： 当大于固定深度是返回True 根据游戏允许的时间来决定深度,截断搜索,评估函数的近似性会使截断搜索可能导致错误 评估函数只适应于静态棋局，即不会很快出现大摇摆的棋局,地平线效应,22,对方招数导致我方严重损失并且理论上基本无法避免,黑棋行棋后，黑象命运已定，但是黑方可以通过检查白王和兵，迫使王吃兵。这样就将象拉出了地平线，被牺牲掉的兵被搜索算法视为好棋招,前向剪枝,23,无需考虑直接剪枝一些子结点 柱搜索 每一层只考虑最好的n步棋 可能导致最佳的行棋被剪掉
6、Probcut算法 使用先验的统计信息在一定程度上保护最佳行棋不被剪枝掉 首先浅层搜索计算结点的v值，再根据经验来估计深度d上的值是否在(,)范围外,搜索与查表,开局时的行棋大多依赖于人类的专业知识 接近尾声的棋局可能性有限 在开局和尾声阶段可以通过查表的方式来进行行棋,随机博弈,25,许多博弈存在不确定性的随机因素，如掷骰子，我们称为随机博弈 如西洋双陆棋 结合了运气和技巧 通过掷骰子决定合法行动,白方掷骰子(6-5)将有4中合法移动,随机博弈,西洋双陆棋的博弈树除了max和min结点之外还必须包括随机结点,没有明确的极大极小值，而是期望值,随机博弈,27,期望极大极小值,机会博弈的评估函数,评估函数应该与棋局获胜的概率成线性变换 时间复杂度(bmnm),部分可观察的博弈,军旗 棋子可以移动但对方看不见棋子是什么 使用信念状态 牌类 随机部分可观察 需要概率推算来制定决策,发展现状,30,国际象棋：深蓝打败世界冠军。深蓝在30个IBM RS/6000处理器并行计算机上运行-剪枝。 西洋跳棋：Chinook程序1990年战胜了世界冠军 奥赛罗：也叫翻转棋，1997年6比0击败人类世界冠军 西洋双陆棋：1992年Gerry Teasuro使用强化学习与神经网络训练的评估函数性能良好。,总结,博弈 -剪枝 不完美的实时决策 随机博弈 部分可观察的博弈 发展现状,Qa？,
