湖南大学人工智能课件5.pptx
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《湖南大学人工智能课件5.pptx》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 湖南大学 人工智能 课件
- 资源描述:
-
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),采用随机顺序检查的总结点数大约是O(b3m/4)当遇到大的问题的时候搜索空间是非常大的解决问题的方法:截断测试限制搜索深度或搜索时间 评估函数评估当前位置的有效性值结点为结点为
3、为真如果IN) 1),(min) 1),(max),()(),()()(MsdasRESULTMINIMAXHMAXsdasRESULTMINIMAXHdsTESTCUTOFFsEVALdsMINMAXHsActionsasActionsa评估函数的定义准则:对于终止状态的排序应该和效用函数一致计算时间不能太长对于非终止状态应该和取胜几率相关评估函数的效率值可能被映射到多个终止状态用终止状态的概率值来表示当前状态的期望值0.72*1+0.2*0+0.08*(-1)=0.76对于国际象棋问题,典型的评估函数是线性加权评估:Eval(s) = w1f1(s) + w2f2(s) + + wnfn(
展开阅读全文