问题求解基本原理课件

基于博弈搜索的搜索策略v 博弈问题及博弈树概念博弈问题及博弈树概念v 博弈搜索控制策略博弈搜索控制策略v 博弈搜索算法及其应用实例博弈搜索算法及其应用实例v 博弈树的博弈树的 -剪枝剪枝 博弈问题及博弈树概念v 博弈问题：博弈问题：对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算盘，还需充分考虑对方的应付策略，盘，还需充分考虑对方的应付策略，（一字棋、国际象棋、一字棋、国际象棋、打扑克、中国象棋、围棋打扑克、中国象棋、围棋）。双人完备信息：对垒的双方轮流走步，对弈的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步，而且还能估计出对方未来可能走的棋步。博弈问题及博弈树概念v 博弈问题描述：博弈问题描述：棋局描述；棋局描述；棋局走步规则。棋局走步规则。博弈搜索过程：搜索棋局走步规则，隐含生成一棵特殊的与或树博弈问题求解：博弈问题及博弈树概念与或节点分层交替出现的与或树从甲的立场出发或节点与节点或节点完全取胜解 图甲走步博弈问题及博弈树概念v判断走步的判断走步的极小极小-极大原则极大原则：v 考虑对方走步时（与节点）：假定对手不会犯错误，他总是选择对自己最有利，对我方最不利的棋步走。因此，我方不能采取任何冒险行动,视对手将走出的棋局为极小值；v考虑我方走步时（或节点）：应在对方造成的最坏的局势中尽可能地选择最好的棋着走，视自己可能走出的棋局为极大值。基于博弈搜索的搜索策略v 博弈问题及博弈树博弈问题及博弈树v 博弈搜索控制策略博弈搜索控制策略v 博弈搜索算法及其应用实例博弈搜索算法及其应用实例v 博弈树的博弈树的 -剪枝剪枝 w 完整的博弈搜索策略（盲目搜索策略）w 有界深度博弈搜索策略完整的博弈搜索策略v核心思想：核心思想：从博弈的从博弈的初始格局初始格局开始，轮番考虑自己与对方可开始，轮番考虑自己与对方可能的所有走步，生成出棋局的各个格局，直到能的所有走步，生成出棋局的各个格局，直到达到分出胜负输赢的达到分出胜负输赢的终止格局终止格局为止，此搜索过为止，此搜索过程程产生的一棵产生的一棵完整的博弈树完整的博弈树。完整的博弈搜索策略v博弈问题实例博弈问题实例：有一堆数目为有一堆数目为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)完整的博弈搜索策略站在MAX立场与节点或节点与节点完全取胜的完备策略v特点：特点：搜索策略简单，易于控制，搜索策略简单，易于控制，可用于可用于简单的博弈简单的博弈或一个复或一个复杂博弈的杂博弈的残局残局；完整的博弈搜索策略w不适合复杂的博弈问题搜索-指数爆炸。例，中国象棋：设每种格局有40种走法，一盘棋双方平均走50步，完整的博弈搜索-搜索节点数（402）50 10160，搜索深度达100层。有必要引入有界深度博弈搜索策略。基于博弈搜索的搜索策略v 博弈问题及博弈树博弈问题及博弈树v 博弈搜索控制策略博弈搜索控制策略w 完整的博弈搜索策略（盲目搜索策略）w 有界深度博弈搜索策略（启发式搜索策略）有界深度搜索策略v 核心思想：核心思想：根据对方已走出的棋步，构造出具有一定深度的博根据对方已走出的棋步，构造出具有一定深度的博弈树，并从此局部博弈树中弈树，并从此局部博弈树中选择选择相对好相对好的的棋着棋着走走。需解决的关键问题：定义估计终结棋局优劣的评价函数；给出棋局优劣性传递的计算方法。定义棋局的评价函数设设 P 为为有界博弈树有界博弈树中棋局；中棋局；(P):棋局优劣的评价函数。棋局优劣的评价函数。例1：从当前棋局到离我方最后取胜的差距：胜利在望 (P)值较大，败局显露 (P)值较小；例2：从当前棋局到到某个明显有利于我方棋局的差距：吃掉对方一子,或者“叫吃”。v(P)MAX赢=(P)MIN输=+v(P)MAX输=(P)MIN赢=-v(P)平 =0v(P)任一终叶棋局优劣的评价函数的定义原则：计算棋局的评价函数有界博弈树中任一棋局（节点）有界博弈树中任一棋局（节点）评价评价函数函数值的值的计算计算：w 对于终叶节点：赋静态评价函数值(P);w 对于非终叶节点：按极小-极大走步原则，采用倒推的方法，自下而上地由子节点计算父节点的动态评价函数值(P)。站在MAX立场基于极小-极大原则的评价函数计算实例静态启发式评价函数值动态评价函数值基于博弈搜索的搜索策略v 博弈问题及博弈树博弈问题及博弈树v 博弈搜索控制策略博弈搜索控制策略v 有界深度搜索算法及其应用实例有界深度搜索算法及其应用实例v 博弈树的博弈树的 -剪枝剪枝有界深度搜索算法及其应用实例 针对当前对方给出的棋局 s：1、按宽度优先法自上而下地生成规定深度的博弈树；2、为有界深度博弈树的所有叶节点赋静态评价函数估计值 3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点的动态评价函数估计值，直至求到起始节点的评价函数值(s)为止。比较我方可走的各棋局的评价函数估计值，从中选择最好的棋步走。再根据对方走出的棋局 s，重复上述过程。有界深度搜索算法及其应用实例一字棋一字棋（站在（站在MAX的立场）的立场）定义定义特殊特殊棋局估计函数棋局估计函数h1(P)v h1(P)MAX赢赢=+v h1(P)MAX输输=-v h1(P)平平=h1(P)MAX赢=+h1(P)MAX输=-h1(P)平=有界深度搜索算法及其应用实例v一字棋一字棋（站在（站在MAX的立场）的立场）v定义棋局评价函数：定义棋局评价函数：将整行、整列或整条对角线称为将整行、整列或整条对角线称为赢线赢线。如果一条赢线上只有（）如果一条赢线上只有（）方的棋子或为空，而没有（方的棋子或为空，而没有（）方的棋子，则称此赢线称为）方的棋子，则称此赢线称为（）方的赢线（）方的赢线。设设方方任意棋局的任意棋局的静态评价函数静态评价函数 h1(P)：(P)=的赢线数的赢线数的赢线数的赢线数h(p)MAX=6 4=2h(p)M=4 6=-2v MAX走棋第一步(深度为2)：MAX走步有界深度搜索算法及其应用实例有界深度搜索算法及其应用实例v MAX走棋第二步：v MAX走棋第三步：MAX走步MAX走步基于博弈搜索的搜索策略问题：启发式博弈搜索策略-将扩展生成博弈树的过程与计算、评价及确定最优走步的过程完全分开进行，导致了搜索效率的低下。对策：-剪枝技术-在生成博弈树同时计算和评价棋局节点，对不必要展开的节点进行剪枝，可减少许多不必要节点的生成和计算工作量，提高搜索效率。基于博弈搜索的搜索策略v 博弈问题及博弈树博弈问题及博弈树v 博弈搜索控制策略博弈搜索控制策略v 有界深度搜索算法及其应用实例有界深度搜索算法及其应用实例v 博弈树的博弈树的 -剪枝剪枝博弈树的 -剪枝h(3)17h(3)25nn1博弈树的-剪枝v 值：值：设博弈树中某节点设博弈树中某节点 n 属于极大层。它左边第属于极大层。它左边第一个子节点一个子节点 n1的评价函的评价函数值数值 h(n1)可视为节点可视为节点 n 的的下界值下界值，或称为，或称为 值值，节点，节点 n 的评价函数的评价函数值值 h(n)决不会小于此决不会小于此 值值。n 的值nn1博弈树的-剪枝 值：u 设博弈树中某节点 n 属于极小层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的上界值，或称为 值，节点 n 的 h(n)决不会大于此 值。n 的值m博弈树的-剪枝v 剪枝：剪枝：若任一极小层节点若任一极小层节点 m 的的 值值小于或等小于或等于于其位于极大层的其位于极大层的父父节点节点的的 值值，即，即 ，则可终止该极小层，则可终止该极小层中节点中节点 m 以下的搜索以下的搜索过程。过程。值值m博弈树的 -剪枝值值 剪枝：u 若任一极大层节点 m 的 值大于或等于其位于极小层的父节点的 值，即 ，则可终止该极大层中节点 m 以下的搜索过程。进一步研究技术：v博弈子树改变排列顺序时，博弈子树改变排列顺序时，-剪枝可能无计可施。剪枝可能无计可施。n 对弈双方不大可能使用同一个棋局估计函数。n 静态评价函数并非绝对可靠。一旦某个节点发生误差，由于无法动态调整误差，则此误差将会通过极大-极小计算原则向上传播，导致决策的失误。n 在有界深度搜索的全过程中，将深度固定不尽合理。有时暂时的局部的放弃可能导致全面的重大胜利。n 呆板的自下而上的计算估计值方法，难于体现对弈弈手的灵活的作战意图，如声东击西、诱敌深入等。作 业博弈搜索作业：v设局部博弈树如图所示，其中，设局部博弈树如图所示，其中，方格表示方格表示或或节点属极大层，节点属极大层，圆圈表示圆圈表示与与节点属极小层，节点属极小层，叶节点下面的数字为静态评价函叶节点下面的数字为静态评价函数值数值 h，请在图上标出：，请在图上标出：.对博弈树进行的必要的对博弈树进行的必要的或或剪剪枝（要求标出剪去的分枝以及剪枝（要求标出剪去的分枝以及剪枝采用的技术类型）；枝采用的技术类型）；.按极小极大原则计算的非叶节按极小极大原则计算的非叶节点的函数估计值点的函数估计值；3.确定确定1最终走出的棋步。最终走出的棋步。1234567101189302173 89143