4.与或图与博弈搜索(2)-max详解

第四章与或图搜索问题4.1与或图搜索4.2AO*算法4.3博弈搜索4.4极大极小决策4.5–剪枝4.3博弈搜索•从智能体角度看，博弈是多智能体之间的竞争和对抗，在竞争的环境中，每个智能体的目标是冲突的，由此引出对抗搜索问题—称为博弈。例如：一字棋、中国象棋、跳棋。•本节探讨两个问题—如何搜索到取胜的路径/如何提高搜索效率•相应的方法—极大极小决策方法/-剪枝方法博弈游戏的描述•两个游戏者的博弈可以定义为一类搜索问题，其中包括：–初始状态：棋盘局面和哪个游戏者出招–规则集：合法走步（招数）的一个列表–终止测试：判断游戏是否结束–效用函数—或称目标函数，对终止状态给出一个数值如输赢和平局(以-∞/+∞/0表示)–双方的初始状态和合法招数定义了游戏的博弈树—此为博弈搜索（最优解是导致取胜的终止状态的一系列招数）博弈游戏的搜索策略•完整的搜索策略：–状态数多，搜索分支多，效率低•极大极小搜索策略：–寻找一步好棋，待对手回敬后再考虑寻找另一步好棋–关键：给定当前状态，如何从合法走步中选择一个较优招数（考虑双方对弈若干步之后，再从当前状态可能的走步中选一个相对较好的招数，即在有限的搜索深度范围内进行求解。为此定义静态估计函数ｆ，用来评价棋局优劣）。–约定：MAX代表程序方，MIN代表对手，MAX先走，f值范围从-∞(对方赢)到+∞(程序方赢)，值越大对程序方越有利。极大极小策略分析31282461452ABDC3223MAXMINMAX–端节点的棋局值通过f(s)计算得到，其余节点采取倒推法计算；–B、C、D是MIN走步节点，MAX考虑最坏情况，取子节点估值最小(MIN取极小)；–Ａ是MAX走步节点，可考虑最好情况，取子节点估值最大者(MAX取极大)极大极小搜索过程•算法分两阶段：–2-4步用宽度优先法生成规定深度的全部博弈树，并计算端节点棋局值–6-8步从底向上逐级倒推非端节点的棋局值。•算法的结果(求当前状态的最佳走子算法)：当前棋局的一步走法，而图搜索找到的是从初始状态到目标状态的解路径极大极小策略的应用示例ABCD在九宫格棋盘上，两位选手轮流摆放棋子，先走出三子一线的一方取胜。教材P68***************1-1-216-5=15-5=05-5=06-5=14-5=-15-6=-15-5=06-6=05-6=-14-6=-25-4=16-4=2MAXMIN极大极小策略分析•效率低–MINMAX过程是把搜索树的生成和棋局估值这两个过程分开进行。见教材P71-∞1282461452ABDC223MAXMINMAX-∞-搜索策略•基本思想–将结点生成和倒推估值同时进行，并根据一定的条件判断，尽早修剪掉无用的分支。-搜索策略:剪枝示例(1)4AB[-∞,4](a)3AB4[-∞,3](b)3AB[3,+∞]48[3,3](c)3ABC[3,+∞][-∞,2]482[3,3](d)-搜索策略:剪枝示例(2)[-∞,14]3ABDC[3,14][-∞,2]48214[3,3](e)3ABDC[3,3][-∞,2][2,2]4821452[3,3](f)总结:在搜索过程中记住棋局倒推值的上下界（和）并进行比较,便可以实现剪枝操作.-搜索策略:剪枝示例(3)-搜索策略•在极大极小值算法基础上增加了剪枝功能,并采用深度优先策略进行搜索。•极大节点的棋局倒推值下界为,极小节点的棋局倒推值上界为。•剪枝的条件：–后辈节点的值(MIN层)≤祖先节点的值时(MAX层)，剪枝–后辈节点的值(MAX层)≥祖先节点的值时(MIN层)，剪枝(剪枝:终止后辈节点以下的搜索过程)•简记为：–极小≤极大，剪枝–极大≥极小，剪枝-搜索策略86-31453-3503-3022-30-2309-300-303305411-31661abcdefghijkmn注意：只有一个结点的值“固定”以后，其值才能向其父结点传递Ｋ＝４MINMINMAXMAX-剪枝的效率•-剪枝的效率很大程度上取决于检查后继节点的次序—应该先检查那些可能最好的后继•如果能够先检查那些最好的后继，则-剪枝算法只需检查O(bd/2)个节点以决定最佳招数/极大极小值算法为O(bd)—有效分支因子b到b的平方根—效率大大提高