第3个专题(2)博弈搜索ppt课件.ppt

一、状态空间搜索和回溯技术的例子二、博弈搜索,第3个专题（2）：搜索技术（博弈搜索）,MIN 7(1)MAX 6-1(1)5-2(1)4-3(1)MIN 5-1-1(0)4-2-1(1)3-2-2(0)3-3-1(1)MAX 4-1-1-1(0)3-2-1-1(1)2-2-2-1（0）MIN 3-1-1-1-1(0)2-2-1-1-1（1）MAX 2-1-1-1-1-1（0）,复习：状态空间表示法的构成,状态空间方法:是用来表示问题及其搜索的一种方法，以状态和算符为基础来表示和求解问题，其四要素如下：1.状态2.算符3.状态空间4.问题的解,例子1.回溯策略(皇后问题),在一个44的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获,(),(),Q,(1,1),(),Q,Q,(1,1),(1,1)(2,3),(),Q,(1,1),(1,1)(2,3),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),Q,(1,1)(2,4)(3.2),(),Q,Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),Q,(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),(),(1,1),(1,1)(2,3),(1,1)(2,4),(1,1)(2,4)(3.2),Q,(1,2),Q,(1,2)(2,4),Q,(1,2)(2,4)(3,1),Q,(1,2)(2,4)(3,1)(4,3),例2：修道士和野人过河问题,问题描述：有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到和的右岸。约束条件：但该船每次只能装载2个人，在任何岸边野人的数目都不能超过修道士的人数，否则修道士就会被野人吃掉。假设野人服从从任何一种过河安排，请问如何规划过河计划才能让所有人都安全地渡到河的右岸。,第一步：定义问题状态的描述形式。S=(Nx,Ny,C)，其中Nx表示修道士在左岸的实际人数；Ny表示野人在左岸的实际人数，C来指示船是否在左岸。C=1表示在左岸，C=0表示不在左岸。第二步：把所有的状态描述出来（32个状态）,第三步：定义算符L(i,j)和R(i,j)从左到右：L(1,0),L(2,0),L(1,1),L(0,1),L(0,2)从右到做：R(1,0),R(2,0),R(1,1),R(0,1),R(0,2),第四步：状态空间搜索图,二、博弈搜索,博 弈：被认为高智能行为游戏;,不断为AI研究提出新课题，推动AI研究的发展。,基于博弈搜索的搜索策略,博弈问题及博弈树概念 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈搜索优化-剪枝,博弈问题及博弈树概念,博弈问题：对抗的双方参加博弈，取胜的因素不仅取决于一方的如意算盘，还需充分考虑对方的应付策略，（一字棋、国际象棋、打扑克、中国象棋、围棋）。,双人完备信息：对垒的双方轮流走步，对弈的条件和走步规则完全相同。每一方不仅知道对方已走过的所有棋步，而且还能估计出对方未来可能走的棋步。,博弈问题及博弈树概念,博弈问题描述：棋局描述；棋局走步规则。,博弈搜索过程：搜索棋局走步规则，隐含生成一棵特殊的与或树,博弈问题求解：,博弈问题及博弈树概念,与或节点分层交替出现的与或树,从甲的立场出发,或节点,与节点,或节点,博弈问题及博弈树概念,判断走步的极小-极大原则：,考虑对方走步时（与节点）：假定对手不会犯错误，他总是选择对自己最有利，对我方最不利的棋步走。因此，我方不能采取任何冒险行动,视对手将走出的棋局为极小值；,考虑我方走步时（或节点）：应在对方造成的最坏的局势中尽可能地选择最好的棋着走，视自己可能走出的棋局为极大值。,基于博弈搜索的搜索策略,博弈问题及博弈树 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈树的-剪枝,完整的博弈搜索策略（盲目搜索策略）有界深度博弈搜索策略,完整的博弈搜索策略,核心思想：从博弈的初始格局开始，轮番考虑自己与对方可能的所有走步，生成出棋局的各个格局，直到达到分出胜负输赢的终止格局为止，此搜索过程产生的一棵完整的博弈树。,完整的博弈搜索策略,博弈问题实例：有一堆数目为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立场,与节点,或节点,与节点,特点：搜索策略简单，易于控制，可用于简单的博弈或一个复杂博弈的残局；,完整的博弈搜索策略,不适合复杂的博弈问题搜索-指数爆炸。例，中国象棋：设每种格局有40种走法，一盘棋双方平均走50步，完整的博弈搜索-搜索节点数（402）50 10160，搜索深度达100层。,有必要引入有界深度博弈搜索策略。,基于博弈搜索的搜索策略,博弈问题及博弈树 博弈搜索控制策略,完整的博弈搜索策略（盲目搜索策略）有界深度博弈搜索策略（启发式搜索策略）,有界深度搜索策略,核心思想：根据对方已走出的棋步，构造出具有一定深度的博弈树，并从此局部博弈树中选择相对好的棋着走。,需解决的关键问题：,定义估计终结棋局优劣的评价函数；,给出棋局优劣性传递的计算方法。,定义棋局的评价函数,设 P 为有界博弈树中棋局；(P):棋局优劣的评价函数。,例1：从当前棋局到离我方最后取胜的差距：胜利在望(P)值较大，败局显露(P)值较小；例2：从当前棋局到到某个明显有利于我方棋局的差距：吃掉对方一子,或者“叫吃”。,(P)MAX赢=(P)MIN输=+(P)MAX输=(P)MIN赢=-(P)平=0,(P)任一终叶棋局优劣的评价函数的定义原则：,计算棋局的评价函数,有界博弈树中任一棋局（节点）评价函数值的计算：,对于终叶节点：赋静态评价函数值(P);,对于非终叶节点：按极小-极大走步原则，采用倒推的方法，自下而上地由子节点计算父节点的动态评价函数值(P)。,基于极小-极大原则的评价函数计算实例,静态启发式评价函数值,基于博弈搜索的搜索策略,博弈问题及博弈树 博弈搜索控制策略 有界深度搜索算法及其应用实例 博弈树的-剪枝,有界深度搜索算法及其应用实例,针对当前对方给出的棋局 s：1、按宽度优先法自上而下地生成规定深度的博弈树；2、为有界深度博弈树的所有叶节点赋静态评价函数估计值 3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点的动态评价函数估计值，直至求到起始节点的评价函数值(s)为止。,比较我方可走的各棋局的评价函数估计值，从中选择最好的棋步走。,再根据对方走出的棋局 s，重复上述过程。,有界深度搜索算法及其应用实例,一字棋（站在MAX的立场）定义特殊棋局估计函数h1(P)h1(P)MAX赢=+h1(P)MAX输=-h1(P)平=,有界深度搜索算法及其应用实例,一字棋（站在MAX的立场）定义棋局评价函数：将整行、整列或整条对角线称为赢线。如果一条赢线上只有（）方的棋子或为空，而没有（）方的棋子，则称此赢线称为（）方的赢线。设方任意棋局的静态评价函数 h1(P)：(P)=的赢线数的赢线数,MAX走步,有界深度搜索算法及其应用实例,有界深度搜索算法及其应用实例,MAX走步,MAX走步,极大极小值算法说明,递归算法按照定义计算每个后继节点的极大极小值/搜索是从目标到初始节点的反向推导算法对博弈树实行了深度优先搜索如果博弈树的最大深度为m，每个节点的合法招数为b，则算法的时间复杂度是O(bm)每次生成全部后继节点的空间复杂度是O(bm)每次只生成一个后继节点的空间复杂度是O(m),极大极小值算法,Function MAX-MIN-DECISION(state)returns an actioninputs:state(current state in game)v MAX-VALUE(state)return the action in SUCCESSORS(state)with value vFunction MAX-VALUE(state)returns a utility valueif TERMINAL-TEST(state)then return UTILITY(state)v-for a,s in SUCCESSORS(state)do v MAX(v,MIN-VALUE(s)return v(a=action招数)Function MIN-VALUE(state)returns a utility valueif TERMINAL-TEST(state)then return UTILITY(state)v+for a,s in SUCCESSORS(state)do v MIN(v,MAX-VALUE(s)return v,基于博弈搜索的搜索策略,问题：启发式博弈搜索策略-将扩展生成博弈树的过程与计算、评价及确定最优走步的过程完全分开进行，导致了搜索效率的低下。,对策：-剪枝技术-在生成博弈树同时计算和评价棋局节点，对不必要展开的节点进行剪枝，可减少许多不必要节点的生成和计算工作量，提高搜索效率。,基于博弈搜索的搜索策略,博弈问题及博弈树概念 博弈搜索控制策略 博弈搜索算法及其应用实例 博弈搜索优化-剪枝,博弈树的-剪枝,h(3)17,h(3)25,博弈树的-剪枝,值：设博弈树中某节点 n 属于极大层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的下界值，或称为 值，节点 n 的评价函数值 h(n)决不会小于此 值。,n 的值,博弈树的-剪枝,值：设博弈树中某节点 n 属于极小层。它左边第一个子节点 n1的评价函数值 h(n1)可视为节点 n 的上界值，或称为 值，节点 n 的 h(n)决不会大于此 值。,n 的值,m,博弈树的-剪枝,剪枝：若任一极小层节点 m 的 值小于或等于其位于极大层的父节点的 值，即，则可终止该极小层中节点 m 以下的搜索过程。,值,值,m,博弈树的-剪枝,值,值,剪枝：若任一极大层节点 m 的 值大于或等于其位于极小层的父节点的 值，即，则可终止该极大层中节点 m 以下的搜索过程。,-剪枝算法(1),在极大极小值算法基础上增加了剪枝功能，即在返回值基础上增加了判断Function ALPHA-BETA-SEARCH(state)returns an actioninputs:state(current state in game)v MAX-VALUE(state,-,+)return the action in SUCCESSORS(state)with value v,-剪枝算法(2),Function MAX-VALUE(state,)returns a utility valueinputs:state,the value of the best alternative for MAX along the path to state,the value of the best alternative for MIN along the path to stateif TERMINAL-TEST(state)then return UTILITY(state)v-for a,s in SUCCESSORS(state)dov MAX(v,MIN-VALUE(s,)if v then return v MAX(,v)return v,-剪枝算法(3),Function MIN-VALUE(state,)returns a utility valueinputs:state,the value of the best alternative for MAX along the path to state the value of the best alternative for MIN along the path to stateif TERMINAL-TEST(state)then return UTILITY(state)v+for a,s in SUCCESSORS(state)dov MIN(v,MAX-VALUE(s,)if v then return v MIN(,v)return v,-剪枝算法的说明,-剪枝可以应用树的任何深度，许多情况下可以剪掉整个子树/其原则是如果在节点n的父节点或者更上层的节点有一个更好的选择m，则在实际游戏(搜索)中永远不会到达n=到目前为止在路径上任意点发现的MAX最佳选择=到目前为止在路径上任意点发现的MIN最佳选择-搜索不断更新/值，当某个节点的值分别比/值更差时剪掉该节点的剩余分支,-剪枝的效率,-剪枝的效率很大程度上取决于检查后继节点的次序应该先检查那些可能最好的后继如果能够先检查那些最好的后继，则-剪枝算法只需检查O(bd/2)个节点以决定最佳招数/极大极小值算法为O(bd)有效分支因子b到b的平方根效率大大提高,进一步研究技术：,博弈子树改变排列顺序时，-剪枝可能无计可施。,对弈双方不大可能使用同一个棋局估计函数。,静态评价函数并非绝对可靠。一旦某个节点发生误差，由于无法动态调整误差，则此误差将会通过极大-极小计算原则向上传播，导致决策的失误。,在有界深度搜索的全过程中，将深度固定不尽合理。有时暂时的局部的放弃可能导致全面的重大胜利。,呆板的自下而上的计算估计值方法，难于体现对弈弈手的灵活的作战意图，如声东击西、诱敌深入等。,作 业,博弈搜索作业：,设局部博弈树如图所示，其中，方格表示或节点属极大层，圆圈表示与节点属极小层，叶节点下面的数字为静态评价函数值 h，请在图上标出：.对博弈树进行的必要的或剪枝（要求标出剪去的分枝以及剪枝采用的技术类型）；.按极小极大原则计算的非叶节点的函数估计值；3.确定1最终走出的棋步。,