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

北京航空航天大学软件开发环境国家重点实验室 Slide 1问题求解基本原理博 弈：被认为高智能行为游戏; 不断为AI研究提出新课题，推动AI研究的发展。搜 索 技 术 ( 三 )博 弈 搜 索北京航空航天大学软件开发环境国家重点实验室 Slide 2基于博弈搜索的搜索策略n 博弈问题及博弈树概念n 博弈搜索控制策略n 博弈搜索算法及其应用实例n 博弈树的 - 剪枝 北京航空航天大学软件开发环境国家重点实验室 Slide 3博弈问题及博弈树概念n 博弈问题：对抗的双方参加博弈，取胜的因素不仅取决于一方的如意 算盘，还需充分考虑对方的应付策略，（一字棋、国际象 棋、打扑克、中国象棋、围棋）。§ 双人完备信息：对垒的双方轮流走步，对弈的条件和走步规则完全相同。每 一方不仅知道对方已走过的所有棋步，而且还能估计出对方 未来可能走的棋步。北京航空航天大学软件开发环境国家重点实验室 Slide 4博弈问题及博弈树概念n 博弈问题描述：w 棋局描述；w 棋局走步规则。 § 博弈搜索过程：搜索棋局走步规则，隐含生成一棵特殊的与或树博弈问题求解：北京航空航天大学软件开发环境国家重点实验室 Slide 5博弈问题及博弈树概念与或节点分层交替出现的与或树从甲的立场出发或节点与节点或节点完全取胜解 图甲走步北京航空航天大学软件开发环境国家重点实验室 Slide 6博弈问题及博弈树概念n判断走步的极小-极大原则：v 考虑对方走步时（与节点）：假定对手不会犯错 误，他总是选择对自己最有利，对我方最不利的 棋步走。因此，我方不能采取任何冒险行动,视对 手将走出的棋局为极小值；v 考虑我方走步时（或节点）：应在对方造成的 最坏的局势中尽可能地选择最好的棋着走，视自己 可能走出的棋局为极大值。北京航空航天大学软件开发环境国家重点实验室 Slide 7基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略n 博弈搜索算法及其应用实例n 博弈树的 - 剪枝 w 完整的博弈搜索策略（盲目搜索策略）w 有界深度博弈搜索策略北京航空航天大学软件开发环境国家重点实验室 Slide 8完整的博弈搜索策略n核心思想：从博弈的初始格局开始，轮番考虑自己与对方可能的所有走步，生成出棋局的各个格局，直到达到分出胜负输赢的终止格局为止，此搜索过程产生的一棵完整的博弈树。北京航空航天大学软件开发环境国家重点实验室 Slide 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层。§ 有必要引入有界深度博弈搜索策略。北京航空航天大学软件开发环境国家重点实验室 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) 任一终叶棋局优劣的评价函数的定义原则：北京航空航天大学软件开发环境国家重点实验室 Slide 15计算棋局的评价函数有界博弈树中任一棋局（节点）评价函数值的计算：w 对于终叶节点：赋静态评价函数值(P);w 对于非终叶节点：按极小-极大走步原则，采用 倒推的方法，自下而上地由子节点计算父节点的动态 评价函数值(P)。北京航空航天大学软件开发环境国家重点实验室 Slide 16站在MAX立场基于极小-极大原则的评价函数计算实例静态启发式 评价函数值动态评价函 数值北京航空航天大学软件开发环境国家重点实验室 Slide 17基于博弈搜索的搜索策略n 博弈问题及博弈树n 博弈搜索控制策略n 有界深度搜索算法及其应用实例n 博弈树的 - 剪枝北京航空航天大学软件开发环境国家重点实验室 Slide 18有界深度搜索算法及其应用实例§ 针对当前对方给出的棋局 s ：1、按宽度优先法自上而下地生成规定深度的博弈树；2、为有界深度博弈树的所有叶节点赋静态评价函数估计值3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点 的动态评价函数估计值，直至求到起始节点的评价函数值 (s) 为止。§ 比较我方可走的各棋局的评价函数估计值，从中选择最好的棋 步走。 § 再根据对方走出的棋局 s，重复上述过程。北京航空航天大学软件开发环境国家重点实验室 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走步北京航空航天大学软件开发环境国家重点实验室 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博弈树的 - 剪枝§ 值：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