搜索(博弈树的启发式搜索)ppt课件.ppt

《搜索(博弈树的启发式搜索)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、博弈树的启发式搜索1博弈问题如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种，我们讨论最简单的“二人零和、全信息、非偶然”博弈，其特征如下：双人对弈，对垒的双方轮流走步。零和。即对一方有利的棋，对另一方肯定是不利的，不存在对双方均有利、或均无利的棋。对弈的结果是一方赢，而另一方输，或者双方和棋。信息完备，对垒双方所得到的信息是一样的，不存在一方能看到，而另一方看不到的情况。任何一方在采取行动前都要根据当前的实际情况，进行得失分析，选取对自已为最有利而对对方最为不利的对策，不存在掷骰子之类的"碰运气"因

2、素。即双方都是很理智地决定自己的行动。博弈是一类富有智能行为的竞争活动，如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈，就是两位选手对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。对弈的结果是一方赢，另一方输；或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈，是指存在不可预测性的博弈，例如掷币等。对机遇性博弈，由于不具备完备信息，因此我们不作讨论。34这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中，双方都希望自己能够获胜。因此

3、，当任何一方走步时，都是选择对自己最为有利，而对另一方最为不利的行动方案。假设博弈的一方为MAX，另一方为MIN。在博弈过程的每一步，可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看，可供自己选择的那些行动方案之间是“或”的关系，原因是主动权掌握在MAX手里，选择哪个方案完全是由自己决定的；而对那些可供MIN选择的行动方案之间则是“与”的关系，原因是主动权掌握在MIN的手里，任何一个方案都有可能被MIN选中，MAX必须防止那种对自己最为不利的情况的发生。5若把双人完备信息博弈过程用图表示出来，就可得到一

4、棵与/或树，这种与/或树被称为博弈树。在博弈树中，那些下一步该MAX走步的节点称为MAX节点，而下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点：（l）博弈的初始状态是初始节点；（2）博弈树中的“或”节点和“与”节点是逐层交替出现的；（3）整个博弈过程始终站在某一方的立场上，所有能使自己一方获胜的终局都是本原问题，相应的节点是可解节点；所有使对方获胜的终局都是不可解节点。例如，站在MAX方，所有能使MAX方获胜的节点都是可解节点，所有能使MIN方获胜的节点都是不可解节点。一.博弈树概述博弈问题空间模型化只考虑

5、两个游戏者:MAX和MIN,两个人轮流出招,直到游戏结束.四元组：（初始状态，操作集合，终止测试（非目标测试），判定函数）初始状态：包括棋局的局面和确定该哪个游戏者出招后继函数：返回(move,state)对的一个列表,其中每一对表示一个合法的着数和其结果状态终止测试：判断游戏是否结束,游戏结束的状态称为终止状态判定函数：又称为目标函数或者收益函数,对终止状态给出一个数值.（比如：可以-1表示输，0表示和局，1表示赢）博弈的初始格局是初始节点在博弈树中，"或"节点和"与"节点是逐层交替出现的。如果我们站在MAX方的立场

6、上，则可供MAX方选择的若干行动方案之间是“或”关系，因为主动权操在MAX方手里，他或者选择这个行动方案，或者选择另一个行动方案，完全由MAX方自已决定。当MAX方选取任一方案走了一步后，MIN方也有若干个可供选择的行动方案，此时这些行动方案对MAX方来说它们之间则是"与"关系，因为这时主动权操在MIN方手里，这些可供选择的行动方案中的任何一个都可能被MIN方选中，MAX方必须应付每一种情况的发生。8对简单的博弈问题，可以生成整个博弈树，找到必胜的策略。但对于复杂的博弈，如国际象棋，大约有10120个节点，可见要生成整

7、个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树，由于该博弈树的叶节点一般不是哪一方的获胜节点，因此，需利用估价函数f(n)对叶节点进行静态评估，对MAX有利的节点其估价函数取正值；那些对MIN有利的节点，其估价函数取负值；那些使双方均等的节点，其估价函数取接近于0的值。二.极大极小过程为了计算非叶节点的值，必须从叶节点向上倒推。对于MAX节点，由于MAX方总是选择估值最大的走步，因此，MAX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点，由于MIN方总是选择使估值最小的走步，因此M

8、IN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值，直至求出初始节点的倒推值为止。由于我们是站在MAX的立场上，因此应选择具有最大倒推值的走步。这一过程称为极大极小过程。下面给出一个极大极小过程的例子。极小极大法基本思想:首先假定，有一个评价函数可以对所有的棋局进行评估。当评价函数值大于0时，表示棋局对我方有利，