文档介绍：搜索策略博弈树的启发式搜索 2博弈问题如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种,我们讨论最简单的“二人零和、全信息、非偶然”博弈, 其特征如下: ?双人对弈,对垒的双方轮流走步。?零和。即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利、或均无利的棋。对弈的结果是一方赢,而另一方输,或者双方和棋。?信息完备,对垒双方所得到的信息是一样的,不存在一方能看到,而另一方看不到的情况。?任何一方在采取行动前都要根据当前的实际情况,进行得失分析,选取对自已为最有利而对对方最为不利的对策,不存在掷骰子之类的" 碰运气"因素。即双方都是很理智地决定自己的行动。?博弈是一类富有智能行为的竞争活动,如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈,就是两位选手对垒,轮流走步,每一方不仅知道对方已经走过的棋步,而且还能估计出对方未来的走步。对弈的结果是一方赢,另一方输; 或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈,是指存在不可预测性的博弈,例如掷币等。对机遇性博弈,由于不具备完备信息,因此我们不作讨论。 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表示赢) 博弈的初始格局是初始节点在博弈树中, "或"节点和" 与"节点是逐层交替出现的。 9 对简单的博弈问题,可以生成整个博弈树,找到必胜的策略。但对于复杂的博弈,如国际象棋,大约有 10 120 个节点,可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树,由于该博弈树的叶节点一般不是哪一方的获胜节点,因此,需利用估价函数 f(n) 对叶节点进行静态评估,对 MAX 有利的节点其估价函数取正值;那些对 MIN 有利的节点,其估价函数取负值;那些使双方均等的节点,其估价函数取接近于 0的值。二. 极大极小过程为了计算非叶节点的值,必须从叶节点向上倒推。对于 MAX 节点,由于 MAX 方总是选择估值最大的走步,因此, MAX 节点的倒推值应该取其后继节点估值的最大值。对于 MIN 节点,由于 MIN 方总是选择使估值最小的走步,因此 MIN 节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值,直至求出初始节点的倒推值为止。由于我们是站在 MAX 的立场上,因此应选择具有最大倒推值的走步。这一过程称为极大极小过程。下面给出一个极大极小过程的例子。极小极***基本思想:首先假定,有一个评价函数可以对所有的棋局进行评估。当评价函数值大于 0时,表示棋局对我方有利,对对方不利; 当评价函数小于 0时,表示棋局对我方不利,对对方有利; 而评价函数值越大,表示对我方越有利。当评价函数值等于正无穷大时,表示我方必胜。评价函数值越小,表示对我方越不利。当评价函数值等于负无穷大时,表示对方必胜;