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