第3个专题(2)-博弈搜索

一、状态空间搜索和回溯技术的例子二、博弈搜索第3个专题（2）：搜索技术（博弈搜索）MIN7(1)MAX6-1(1)5-2(1)4-3(1)MIN5-1-1(0)4-2-1(1)3-2-2(0)3-3-1(1)MAX4-1-1-1(0)3-2-1-1(1)2-2-2-1（0）MIN3-1-1-1-1(0)2-2-1-1-1（1）MAX2-1-1-1-1-1（0）复习：状态空间表示法的构成状态空间方法:是用来表示问题及其搜索的一种方法，以状态和算符为基础来表示和求解问题，其四要素如下：1.状态2.算符3.状态空间4.问题的解例子1.回溯策略(皇后问题)在一个4×4的国际象棋棋盘上,一次一个地摆布四枚皇后棋子,摆好后要满足每行、每列和对象线上只允许出现一枚棋子,即棋子间不许相互俘获QQQQ()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((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个状态）S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(3,0,1)S4=(3,3,0)S5=(3,2,0)S6=(3,1,0)S7=(3,0,0)S8=(2,3,1)S9=(2,2,1)S10=(2,1,1)S11=(2,0,1)S12=(2,3,0)S13=(2,2,0)S14=(2,1,0)S15=(2,0,0)S16=(1,3,1)S17=(1,2,1)S18=(1,1,1)S19=(1,0,1)S20=(1,3,0)S21=(1,2,0)S22=(1,1,0)S23=(1,0,0)S24=(0,3,1)S25=(0,2,1)S26=(0,1,1)S27=(0,0,1)S28=(0,3,0)S29=(0,2,0)S30=(0,1,0)S31=(0,0,0)第三步：定义算符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)。站在MAX立场基于极小-极大原则的评价函数计算实例静态启发式评价函数值动态评价函数值基于博弈搜索的搜索策略博弈问题及博弈树博弈搜索控制策略有界深度搜索算法及其应用实例博弈树的α-β剪枝有界深度搜索算法及其应用实例针对当前对方给出的棋局s：1、按宽度优先法自上而下地生成规定深度的博弈树；2、为有界深度博弈树的所有叶节点赋静态评价函数估计值3、根据极小-极大走步原则自下而上地逐级计算各非终叶节点的动态评价函数估计值，直至求到起始节点的评价函数值ｈ(s)为止。比较我方可走的各棋局的评价函数估计值，从中选择最好的棋步走。再根据对方走出的棋局s，重复上述过程。有界深度搜索算法及其应用实例一字棋（站在MAX的立场）定义特殊棋局估计函数h1(P)h1(P)MAX赢=+∞h1(P)MAX输=-∞h1(P)平=０h1(P)MAX赢=+∞h1(P)MAX输=-∞h1(P)平=０有界深度搜索算法及其应用实例一字棋（站在MAX的立场）定义棋局评价函数：将整行、整列或整条对角线称为赢线。如果一条赢线上只有ＭＡＸ（ＭＩＮ）方的棋子或为空，而没有ＭＩＮ（ＭＡＸ）方的棋子，则称此赢线称为ＭＡＸ（ＭＩＮ）方的赢线。设ＭＡＸ方任意棋局的静态评价函数h1(P)：ｈ１(P)=ＭＡＸ的赢线数–ＭＩＮ的赢线数h(p)MAX=6–4=2h(p)MＩＮ=4–6=-2MAX走棋第一步(深度为2)：MAX走步有界深度搜索算法及其应用实例有界深度搜索算法及其应用实例MAX走棋第二步：MAX走棋第三步：MAX走步MAX走步极大极小值算法说明递归算法—按照定义计算每个后继节点的极大极小值/搜索是从目标到初始节点的反向推导算法对博弈树实行了深度优先搜索如果博弈树的最大深度为m，每个节点的合法招数为b，则算法的时间复杂度是O(bm)每次生成全部后继节点的空间复杂度是O(bm)每次只生成一个后继节点的空间复杂度是O(m)极大极小值算法FunctionMAX-MIN-DECISION(state)returnsanactioninputs:state(currentstateingame)v←MAX-VALUE(state)returntheactioninSUCCESSORS(state)withvaluevFunctionMAX-VALUE(state)returnsautilityvalueifTERMINAL-TEST(state)thenreturnUTILITY(state)v←-∞fora,sinSUCCESSORS(state)dov←MAX(v,MIN-VALUE(s))returnv(a=action招数)FunctionMIN-VALUE(state)returnsautilityvalueifTERMINAL-TEST(state)thenreturnUTILITY(state)v←+∞fora,sinSUCCESSORS(state)dov←MIN(v,MAX-VALUE(s))returnv基于博弈搜索的搜索策略问题：启发式博弈搜索策略-将扩展生成博弈树的过程与计算、评价及确定最优走步的过程完全分开进行，导致了搜索效率的低下。对策：α-β剪枝技术-在生成博弈树同时计算和评价棋局节点，对不必要展开的节点进行剪枝，可减少许多不必要节点的生成和计算工作量，提高搜索效率。基于博弈搜索的搜索策略博弈问题及博弈树概念博弈搜索控制策略博弈搜索算法及其应用实例博弈搜索优化-α-β剪枝博弈树的α-β剪枝h(3)≤17h(3)25nn1博弈树的α-β剪枝α值：设博弈树中某节点n属于极大层。它左边第一个子节点n1的评价函数值h(n1)可视为节点n的下界值，或称为α值，节点n的评价函数值h(n)决不会小于此α值。n的α值nn1博弈树的α-β剪枝β值：设博弈树中某节点n属于极小层。它左边第一个子节点n1的评价函数值h(n1)可视为节点n的上界值，或称为β值，节点n的h(n)决不会大于此β值。n的β值m博弈树的α-β剪枝α剪枝：若任一极小层节点m的β值小于或等于其位于极大层的父