搜索策略博弈树的启发式搜索2博弈问题如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博 弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈， 其特征如下：l双人对弈，对垒的双方轮流走步。l零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均 有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方 和棋。l信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而 另一方看不到的情况。l任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选 取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的“ 碰运气“因素。即双方都是很理智地决定自己的行动。 博弈是一类富有智能行为的竞争活动，如下棋 、打牌、战争等。博弈可分为双人完备信息博 弈和机遇性博弈。所谓双人完备信息博弈，就 是两位选手对垒，轮流走步，每一方不仅知道 对方已经走过的棋步，而且还能估计出对方未 来的走步。对弈的结果是一方赢，另一方输； 或者双方和局。这类博弈的实例有象棋、围棋 等。所谓机遇性博弈，是指存在不可预测性的 博弈，例如掷币等。对机遇性博弈，由于不具 备完备信息，因此我们不作讨论。45这里我们主要讨论双人完备信息博弈问题。 在双人完备信息博弈过程 中，双方都希望自己能够获胜。因此，当任何一方走步时，都是选择 对自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步， 可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看 ，可供自己选择的那些行动方案之间是“或”的关系，原因是主动权掌 握在MAX手里，选择哪个方案完全是由自己决定的；而对那些可供 MIN选择的行动方案之间则是“与”的关系，原因是主动权掌握在MIN 的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自 己最为不利的情况的发生。 6若把双人完备信息博弈过程用图表示出来，就可得到一棵与/或 树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走 步的节点称为MAX节点，而下一步该MIN走步的节点称为MIN节点 。博弈树具有如下特点：（l）博弈的初始状态是初始节点；（2）博弈树中的“或”节点和“与”节点是逐层交替出现的；（3）整个博弈过程始终站在某一方的立场上，所有能使自己一方 获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜 的终局都是不可解节点。例如，站在MAX方，所有能使MAX方获胜 的节点都是可解节点，所有能使MIN方获胜的节点都是不可解节点。一.博弈树概述博弈问题空间模型化只考虑两个游戏者: MAX和MIN, 两个人轮流出招,直到游戏结 束. 四元组： （初始状态，操作集合，终止测试（非目标测试），判定函数）初始状态：包括棋局的局面和确定该哪个游戏者出招 后继函数：返回(move,state)对的一个列表,其中每一对表示一个 合法的着数和其结果状态 终止测试：判断游戏是否结束, 游戏结束的状态称为终止状态 判定函数：又称为目标函数或者收益函数,对终止状态给出一个数 值. （比如：可以-1表示输，0表示和局，1表示赢）博弈的初始格局是初始节点在博弈树中，“或“节点和“与 “节点是逐层交替出现的。如果我们站在MAX方的立场上，则可供 MAX方选择的若干行动方案之间是“或”关 系，因为主动权操在MAX方手里，他或者 选择这个行动方案，或者选择另一个行 动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有 若干个可供选择的行动方案，此时这些行动方 案对MAX方来说它们之间则是“与“关系，因为 这时主动权操在MIN方手里，这些可供选择的 行动方案中的任何一个都可能被MIN方选中， MAX方必须应付每一种情况的发生。9对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但 对于复杂的博弈，如国际象棋，大约有10120个节点，可见要生成整 个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成 一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方的获胜节点 ，因此，需利用估价函数f(n)对叶节点进行静态评估，对MAX有利的 节点其估价函数取正值；那些对MIN有利的节点，其估价函数取负值 ；那些使双方均等的节点，其估价函数取接近于0的值。二. 极大极小过程为了计算非叶节点的值，必须从叶节点向上倒推。对于MAX节点 ，由于 MAX方总是选择估值最大的走步，因此，MAX节点的倒推值 应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选 择使估值最小的走步，因此MIN节点的倒推值应取其后继节点估值的 最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为 止。由于我们是站在MAX的立场上，因此应选择具有最大倒推值的走 步。这一过程称为极大极小过程。下面给出一个极大极小过程的例子。极小极大法基本思想:首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，对对方不利;当评价函数小于0时，表示棋局对我方不利，对对方有利;而评价函数值越大，表示对我方越有利。当评价函数值等于正无穷大时，表示我方必胜。评价函数值越小，表示对我方越不利。当评价函数值等于负无穷大时，表示对方必胜;假设双方都是对弈高手，在只看一步棋的情况下，我方一定走评价函数值最大的一步棋，而对方一定走评价函数值最小的一步棋。人下棋的思考方式人下棋实际上采用一种试探性的方法:假定走了一步棋,看对方会有哪些应法;再根据对方的每一种应法,看我方是否有好的回应;这一过程一直进行下去,直到若干步后,找到一个满意的走法为止.极大极小搜索方法模拟的就是人的这样一种思维过程.极大极小搜索方法是一种在有限搜索深度范围进行求解的方法.ABCD31282145246b1b2b33c1c2c32d1d2d32a1 a2a3MAXMIN3定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值2.非叶子节点的估值由倒推取值的方法取得a.MAX走步必然选择对自己最有利的 一步,如A节点的估计值是3b.MIN走步必然选择对自 己最有利的一步,如D节 点的估计值是21.首先按照一定的搜索深度生成出给定深度d以内的所有状态 ，计算所有叶节点的评价函数值。获得根节点取值的那一 分枝，即为所选择的最 佳走步节点A,轮到MAX下棋.算法框架 整个算法分为四个步骤： 1、以当前状态为根结点产生一个博弈树。 2、对博弈树的每一个叶结点，利用判定函数给出它的判定值。 3、从叶结点开始，一层一层地回溯。在回溯过程中，利用最大/最小判定为每一个结 点给出其判定值。 4、MAX方选择下一层中判定值最大的结点，作为它的下一状态。Function Minimax-Decision(state) return an actionvMax-Value(state) return action in successors(state) with value vFunction Max-Value(state) return a utility valueif Terminal-Test(state) then return Utility(state)v- for s in successors(state) dov Max(v, Min_Value(s) Return vFunction Min-Value(state) return an utility valueif Terminal-Test(state) then return Utility(state)v+ for s in successors(state) dov Min(v, Max_Value(s) Return v14例： 一字棋游戏。设有一个三行三列的棋盘，如下图所示，两个棋 手轮流走步，每个棋手走步时往空格上摆一个自己的棋子，谁先使自 己的棋子成三子一线为赢。设MAX方的棋子用标记，MIN方的棋子 用 标记，并规定MAX方先走步。解：为了对叶节点进行静态估值，规定估价函数e（P）如下：若 P是 MAX的必胜局， 则 e（P）= + ；若 P是 MIN 的必胜局， 则 e（P）= - ；若P对MAX、MIN都是胜负未定局 ，则e（P）= e（+P）e（-P） 其中，e（+P）表示棋局 P上有可能使 成三子一线的数目；e（-P）表示棋 局 P上有可能使 成三子一线的数目。二. 极大极小过程15例如，对图1所示的棋局有估价函数值 e（P）6-42图1 棋局1在搜索过程中，具有对称性的棋局认为是同一棋 局。例如，图2所示的棋局可以认为是同一个棋局，这 样可以大大减少搜索空间。图3给出了第一着走棋以后 生成的博弈树。图中叶节点下面的数字是该节点的静 态估值，非叶节点旁边的数字是计算出的倒推值。从 图中可以看出，对MAX来说S2是一着最好的走棋，它 具有较大的倒推值。图2 对称棋局的例子16图3 一子棋的极大极小搜索S0S1S2S3S4S5-1 1 -26-5=15-5=06-5=15-5=04-5=-15-6=-15-5=06-6=05-6=-14-6=-25-4=16-4=2一字棋游戏极小极大树定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值2.非叶子节点的估值由倒 推取值的方法取得a.MAX走步必然选择对自己最有利的 一步,如节点的估计值是1b.MIN走步必然选择对自己最有 利的一步,如节点的估计值是-21.首先按照一定的搜索深度生成出给定深度d以内的所有状态，计算所有叶节 点的评价函数值。获得根节点取值的那一分枝 ，即为所选择的最佳走步MAX在初始节点时应该怎么走一字棋游戏极小极大树MAX在第二步应该怎么走-剪枝在极小极大搜索方法中，由于要先生成指定深度以内的所 有节点，其节点数将随着搜索深度的增加呈指数增长。这极大 地限制了极小极大搜索方法的使用。-剪枝的基本思想:边生成博弈树边计算评估各节点的倒推值，并且根据评估 出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点 ，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销 ，提高了搜索效率。 ABCD- ,+ - , 3 3128 3, + - ,+ 2 2 3 , 3 - 14 14 3, 14 52 2 , 2 3, 3 -剪枝= 到目前为止我们在路径上的任意选择点发现MAX的最佳(即极大值)选择= 到目前为止我们在路径上的任意选择点发现MIN的最佳(即极小值)选择算法框架(1) 对于一个与节点MIN，若能估计出其倒推值的上确界，并且这个值不大 于 MIN的父节点(一定是或节点)的估计倒推值的下确界，即，则就不 必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推 值已无任何影响)。这一过程称为剪枝。(2) 对于一个或节点MAX，若能估计出其倒推值的下确界，并且这个值不小 于 MAX的父节点(一定是与节点)的估计倒推值的上确界，即，则就不 必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值 已无任何影响)。这一过程称为剪枝。算法特点： (1) MAX节点(包括起始节点)的值永不减少； (2) MIN节点(包括起始节点)的值永不增加。和值的计算方法： (1) 一个MAX节点的值等于其后继节点当前最大的最终倒推值。 (2) 一个MIN节点的值等于其后继节点当前最小的最终倒推值。一字棋第一阶段-剪枝方法 第一个被访问的叶子节点访问完节点1, 初始节点s的取值范围是-1 ,+ 开始访问完节点7, 访问完节点8, 节点7的取值范围是- ,-1 节点7的父节点是s 此时, 节点7不 必在分裂下去了, 即剪掉该枝深度搜索例若以最理想的情况进行搜索，即对MIN节点先扩展最低估