湖南大学人工智能课件5PPT资料.pptx

湖南大学人工智能课件5PPT资料.pptx

《湖南大学人工智能课件5PPT资料.pptx》由会员分享，可在线阅读，更多相关《湖南大学人工智能课件5PPT资料.pptx（32页珍藏版）》请在冰点文库上搜索。

效用函数,博弈树,零和游戏叶子结点表示结果赢:

1输:

-1和:

0,博弈中的优化决策,博弈树的最优策略通过检查每个结点的极大极小值来决定：

minimax（n）Max喜欢移动到有极大值的状态，min喜欢移动到有极小值的状态,极小极大算法,极小极大算法,3,极小极大算法,完备性？

最优性？

时间复杂度？

空间复杂度？

多人博弈,与两人博弈的不同用向量值取代单一值通常选择使自己效用值最大的行为联盟与破坏联盟,-剪枝,游戏状态数目的增长是指数级的通过剪枝来消除对部分分支的搜索，且被剪掉的分支不影响最终的决策,-剪枝,-剪枝,-剪枝,-剪枝,-剪枝的效率很大程度上依赖于检查后继状态的顺序最佳剪枝情况下可以将时间复杂度从极大极小算法的O（bm）减少到O（bm/2），采用随机顺序检查的总结点数大约是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,f1=（白棋皇后数量）-（黑棋皇后数量）线性评估假定特征之间是独立的，然而实际中特征之间具有关联性，比如国际象棋在残局中2个象比单个象的价值要高出2倍,截断搜索,Environment:

Patient,hospital,staffActuators:

Screendisplay（questions,tests,diagnoses,treatments,referrals）Sensors:

Keyboard（entryofsymptoms,findings,patientsanswers）,在-剪枝算法中Terminal-test被替换程cutoff-test（state,depth）Utility被替换程eval（state）cutoff-test（state,depth）截断策略：

当大于固定深度是返回True根据游戏允许的时间来决定深度,截断搜索,评估函数的近似性会使截断搜索可能导致错误评估函数只适应于静态棋局，即不会很快出现大摇摆的棋局,地平线效应,22,对方招数导致我方严重损失并且理论上基本无法避免,黑棋行棋后，黑象命运已定，但是黑方可以通过检查白王和兵，迫使王吃兵。

这样就将象拉出了地平线，被牺牲掉的兵被搜索算法视为好棋招,前向剪枝,23,无需考虑直接剪枝一些子结点柱搜索每一层只考虑最好的n步棋可能导致最佳的行棋被剪掉Probcut算法使用先验的统计信息在一定程度上保护最佳行棋不被剪枝掉首先浅层搜索计算结点的v值，再根据经验来估计深度d上的值是否在（,）范围外,搜索与查表,开局时的行棋大多依赖于人类的专业知识接近尾声的棋局可能性有限在开局和尾声阶段可以通过查表的方式来进行行棋,随机博弈,25,许多博弈存在不确定性的随机因素，如掷骰子，我们称为随机博弈如西洋双陆棋结合了运气和技巧通过掷骰子决定合法行动,白方掷骰子（6-5）将有4中合法移动,随机博弈,西洋双陆棋的博弈树除了max和min结点之外还必须包括随机结点,没有明确的极大极小值，而是期望值,随机博弈,27,期望极大极小值,机会博弈的评估函数,评估函数应该与棋局获胜的概率成线性变换时间复杂度（bmnm）,部分可观察的博弈,军旗棋子可以移动但对方看不见棋子是什么使用信念状态牌类随机部分可观察需要概率推算来制定决策,发展现状,30,国际象棋：

深蓝打败世界冠军。

深蓝在30个IBMRS/6000处理器并行计算机上运行-剪枝。

西洋跳棋：

Chinook程序1990年战胜了世界冠军奥赛罗：

也叫翻转棋，1997年6比0击败人类世界冠军西洋双陆棋：

1992年GerryTeasuro使用强化学习与神经网络训练的评估函数性能良好。

总结,博弈-剪枝不完美的实时决策随机博弈部分可观察的博弈发展现状,Qa？