电子文档交易市场
安卓APP | ios版本
电子文档交易市场
安卓APP | ios版本

博弈搜索-copy_北航6系人工智能课件ppt课件

32页
  • 卖家[上传人]:ZJ****4
  • 文档编号:51837056
  • 上传时间:2018-08-16
  • 文档格式:PPT
  • 文档大小:790.50KB
  • / 32 举报 版权申诉 马上下载
  • 文本预览
  • 下载提示
  • 常见问题
    • 1、北京航空航天大学软件开发环境国家重点实验室 Slide 1问题求解基本原理博 弈:被认为高智能行为游戏; 不断为AI研究提出新课题,推动AI研究的发展。搜 索 技 术 ( 三 )博 弈 搜 索北京航空航天大学软件开发环境国家重点实验室 Slide 2基于博弈搜索的搜索策略n 博弈问题及博弈树概念n 博弈搜索控制策略n 博弈搜索算法及其应用实例n 博弈树的 - 剪枝 北京航空航天大学软件开发环境国家重点实验室 Slide 3博弈问题及博弈树概念n 博弈问题:对抗的双方参加博弈,取胜的因素不仅取决于一方的如意 算盘,还需充分考虑对方的应付策略,(一字棋、国际象 棋、打扑克、中国象棋、围棋)。 双人完备信息:对垒的双方轮流走步,对弈的条件和走步规则完全相同。每 一方不仅知道对方已走过的所有棋步,而且还能估计出对方 未来可能走的棋步。北京航空航天大学软件开发环境国家重点实验室 Slide 4博弈问题及博弈树概念n 博弈问题描述:w 棋局描述;w 棋局走步规则。 博弈搜索过程:搜索棋局走步规则,隐含生成一棵特殊的与或树博弈问题求解:北京航空航天大学软件开发环境国家重点实验室 Slide 5博弈问

      2、题及博弈树概念与或节点分层交替出现的与或树从甲的立场出发或节点与节点或节点完全取胜解 图甲走步北京航空航天大学软件开发环境国家重点实验室 Slide 6博弈问题及博弈树概念n判断走步的极小-极大原则:v 考虑对方走步时(与节点):假定对手不会犯错 误,他总是选择对自己最有利,对我方最不利的 棋步走。因此,我方不能采取任何冒险行动,视对 手将走出的棋局为极小值;v 考虑我方走步时(或节点):应在对方造成的 最坏的局势中尽可能地选择最好的棋着走,视自己 可能走出的棋局为极大值。北京航空航天大学软件开发环境国家重点实验室 Slide 7基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略n 博弈搜索算法及其应用实例n 博弈树的 - 剪枝 w 完整的博弈搜索策略(盲目搜索策略)w 有界深度博弈搜索策略北京航空航天大学软件开发环境国家重点实验室 Slide 8完整的博弈搜索策略n核心思想:从博弈的初始格局开始,轮番考虑自己与对方可能的所有走步,生成出棋局的各个格局,直到达到分出胜负输赢的终止格局为止,此搜索过程产生的一棵完整的博弈树。北京航空航天大学软件开发环境国家重点实验室 Slid

      3、e 9完整的博弈搜索策略n博弈问题实例:有一堆数目为N的钱币,甲、乙二人轮流分堆。要求每人每次挑 选其中某一堆钱币,将其分成数目不等的两小堆。分堆过程持 续,直至其中一人无法再将任一堆钱币分成数目不等的两堆时 ,则认输。 博弈问题描述:分堆格局(状态): (x1,x2,xn,M), 其中,xi: 第 i 堆钱币的个数;M: 当前走步人编号 -(MAX, MIN)走步规则:IF (x1,x2,xn,M) (xi = Y+Z) (Y Z)THEN (x1,x2,xi-1, Y, Z, xi+1, , xn, M)北京航空航天大学软件开发环境国家重点实验室 Slide 10完整的博弈搜索策略站在MAX立场与节点或节点 与节点完全取胜的完 备策略北京航空航天大学软件开发环境国家重点实验室 Slide 11n特点: w 搜索策略简单,易于控制,可用于简单的博弈或一个复 杂博弈的残局;完整的博弈搜索策略w不适合复杂的博弈问题搜索 - 指数爆炸。例,中国象棋:设每种格局有40种走法,一盘棋双方平均走50步,完整的博弈搜索-搜索节点数(402)50 10160,搜索深度达100层。 有必要引入有界深度

      4、博弈搜索策略。北京航空航天大学软件开发环境国家重点实验室 Slide 12基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略w 完整的博弈搜索策略(盲目搜索策略)w 有界深度博弈搜索策略(启发式搜索策略)北京航空航天大学软件开发环境国家重点实验室 Slide 13有界深度搜索策略n 核心思想:根据对方已走出的棋步,构造出具有一定深度的博 弈树,并从此局部博弈树中选择相对好的棋着走。 需解决的关键问题:定义估计终结棋局优劣的评价函数;给出棋局优劣性传递的计算方法。北京航空航天大学软件开发环境国家重点实验室 Slide 14定义棋局的评价函数设 P 为有界博弈树中棋局;(P): 棋局优劣的评价函数。 例1:从当前棋局到离我方最后取胜的差距:胜利在望 (P)值较大,败局显露 (P)值较小; 例2:从当前棋局到到某个明显有利于我方棋局的差距:吃掉对方一子, 或者 “叫吃”。v (P)MAX赢 = (P)MIN输 = + v (P)MAX输 = (P)MIN赢 = - v (P)平 = 0v (P) 任一终叶棋局优劣的评价函数的定义原则:北京航空航天大学软件开发环境国家重点实验室 S

      5、lide 15计算棋局的评价函数有界博弈树中任一棋局(节点)评价函数值的计算:w 对于终叶节点:赋静态评价函数值(P);w 对于非终叶节点:按极小-极大走步原则,采用 倒推的方法,自下而上地由子节点计算父节点的动态 评价函数值(P)。北京航空航天大学软件开发环境国家重点实验室 Slide 16站在MAX立场基于极小-极大原则的评价函数计算实例静态启发式 评价函数值动态评价函 数值北京航空航天大学软件开发环境国家重点实验室 Slide 17基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略n 有界深度搜索算法及其应用实例n 博弈树的 - 剪枝北京航空航天大学软件开发环境国家重点实验室 Slide 18有界深度搜索算法及其应用实例 针对当前对方给出的棋局 s :1、按宽度优先法自上而下地生成规定深度的博弈树;2、为有界深度博弈树的所有叶节点赋静态评价函数估计值3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点 的动态评价函数估计值,直至求到起始节点的评价函数值 (s) 为止。 比较我方可走的各棋局的评价函数估计值,从中选择最好的棋 步走。 再根据对方走出的棋局 s,重复上

      6、述过程。北京航空航天大学软件开发环境国家重点实验室 Slide 19有界深度搜索算法及其应用实例一字棋(站在MAX的立场)定义特殊棋局估计函数h1(P)v h1(P)MAX赢 = + v h1(P)MAX输 = - v h1(P)平 = h1(P)MAX赢 = +h1(P)MAX输 = -h1(P)平 = 北京航空航天大学软件开发环境国家重点实验室 Slide 20有界深度搜索算法及其应用实例n一字棋(站在MAX的立场)n定义棋局评价函数:将整行、整列或整条对角线称为赢线。 如果一条赢线上只有() 方的棋子或为空,而没有( )方的棋子,则称此赢线称为 ()方的赢线。 设方任意棋局的静态评价函数 h1(P) :w(P) = 的赢线数 的赢线数h(p)MAX = 6 4 = 2h(p)M = 4 6 = - 2北京航空航天大学软件开发环境国家重点实验室 Slide 21v MAX走棋第一步( 深度为2 ):MAX走步有界深度搜索算法及其应用实例北京航空航天大学软件开发环境国家重点实验室 Slide 22有界深度搜索算法及其应用实例v MAX走棋第二步:v MAX走棋第三步:MAX走步MAX

      7、走步北京航空航天大学软件开发环境国家重点实验室 Slide 23基于博弈搜索的搜索策略问题:启发式博弈搜索策略 - 将扩展生成博弈树的过程与计算、评价 及确定最优走步的过程完全分开进行,导致了搜索效率的低下。对策: - 剪枝技术 - 在生成博弈树同时计算和评价棋局节点,对不必要展开的节点进行剪枝,可减少许多不必要节点的生成和计算 工作量,提高搜索效率。北京航空航天大学软件开发环境国家重点实验室 Slide 24基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略n 有界深度搜索算法及其应用实例n 博弈树的 - 剪枝北京航空航天大学软件开发环境国家重点实验室 Slide 25博弈树的 - 剪枝h(3) 17h(3) 25北京航空航天大学软件开发环境国家重点实验室 Slide 26nn1博弈树的 - 剪枝n 值:w 设博弈树中某节点 n 属于极大层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的下界值,或称为 值,节点 n 的评价函数值 h(n)决不会小于此 值。n 的值北京航空航天大学软件开发环境国家重点实验室 Slide 27nn1博弈树的 - 剪枝 值:

      8、u 设博弈树中某节点 n 属于极小层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的上界值,或称为 值,节点 n 的 h(n)决不会大于此 值。 n 的值北京航空航天大学软件开发环境国家重点实验室 Slide 28m博弈树的 - 剪枝n 剪枝:w 若任一极小层节点 m 的 值小于或等于其位于极大层的父节点的 值,即 ,则可终止该极小层中节点 m 以下的搜索过程。 值值北京航空航天大学软件开发环境国家重点实验室 Slide 29m博弈树的 - 剪枝值值 剪枝:u 若任一极大层节点 m 的 值大于或等于其位于极小层的父节点的 值,即 ,则可终止该极大层中节点 m 以下的搜索过程。北京航空航天大学软件开发环境国家重点实验室 Slide 30进一步研究技术:n博弈子树改变排列顺序时, - 剪枝可能无计可施。n 对弈双方不大可能使用同一个棋局估计函数。n 静态评价函数并非绝对可靠。一旦某个节点发生误差,由于 无法动态调整误差,则此误差将会通过极大-极小计算原则向 上传播,导致决策的失误。n 在有界深度搜索的全过程中,将深度固定不尽合理。有时暂 时的局部的放弃可能导致全面的重大胜利。n 呆板的自下而上的计算估计值方法,难于体现对弈弈手的灵活 的作战意图,如声东击西、诱敌深入等。北京航空航天大学软件开发环境国家重点实验室 Slide 31作 业北京航空航天大学软件开发环境国家重点实验室 Slide 32博弈搜索作业:n设局部博弈树如图所示,其中, 方格表示或节点属极大层, 圆圈表示与节点属极小层, 叶节点下面的数字为静态评价函 数值 h,请在图上标出:. 对博弈树进行的必要的或 剪枝(要求标出剪去的分枝以 及剪枝采用的技术类型);. 按极小极大原则计算的非叶 节点的函数估计值;3. 确定1最终走出的棋步。 1234567101189302173 89143

      《博弈搜索-copy_北航6系人工智能课件ppt课件》由会员ZJ****4分享,可在线阅读,更多相关《博弈搜索-copy_北航6系人工智能课件ppt课件》请在金锄头文库上搜索。

      点击阅读更多内容
    最新标签
    发车时刻表 长途客运 入党志愿书填写模板精品 庆祝建党101周年多体裁诗歌朗诵素材汇编10篇唯一微庆祝 智能家居系统本科论文 心得感悟 雁楠中学 20230513224122 2022 公安主题党日 部编版四年级第三单元综合性学习课件 机关事务中心2022年全面依法治区工作总结及来年工作安排 入党积极分子自我推荐 世界水日ppt 关于构建更高水平的全民健身公共服务体系的意见 空气单元分析 哈里德课件 2022年乡村振兴驻村工作计划 空气教材分析 五年级下册科学教材分析 退役军人事务局季度工作总结 集装箱房合同 2021年财务报表 2022年继续教育公需课 2022年公需课 2022年日历每月一张 名词性从句在写作中的应用 局域网技术与局域网组建 施工网格 薪资体系 运维实施方案 硫酸安全技术 柔韧训练 既有居住建筑节能改造技术规程 建筑工地疫情防控 大型工程技术风险 磷酸二氢钾 2022年小学三年级语文下册教学总结例文 少儿美术-小花 2022年环保倡议书模板六篇 2022年监理辞职报告精选 2022年畅想未来记叙文精品 企业信息化建设与管理课程实验指导书范本 草房子读后感-第1篇 小数乘整数教学PPT课件人教版五年级数学上册 2022年教师个人工作计划范本-工作计划 国学小名士经典诵读电视大赛观后感诵读经典传承美德 医疗质量管理制度 2 2022年小学体育教师学期工作总结 2022年家长会心得体会集合15篇
     
    收藏店铺
    关于金锄头网 - 版权申诉 - 免责声明 - 诚邀英才 - 联系我们
    手机版 | 川公网安备 51140202000112号 | 经营许可证(蜀ICP备13022795号)
    ©2008-2016 by Sichuan Goldhoe Inc. All Rights Reserved.