文档介绍：搜索策略
博弈树的启发式搜索
2
博弈问题
如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种,我们讨论最简单的“二人零和、全信息、非偶然”博弈,其特征如下:
双人对弈,对垒的双方轮流走步。
零和。即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利、或均无利的棋。对弈的结果是一方赢,而另一方输,或者双方和棋。
信息完备,对垒双方所得到的信息是一样的,不存在一方能看到,而另一方看不到的情况。
任何一方在采取行动前都要根据当前的实际情况,进行得失分析,选取对自已为最有利而对对方最为不利的对策,不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。
博弈是一类富有智能行为的竞争活动,如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈,就是两位选手对垒,轮流走步,每一方不仅知道对方已经走过的棋步,而且还能估计出对方未来的走步。对弈的结果是一方赢,另一方输;或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈,是指存在不可预测性的博弈,例如掷币等。对机遇性博弈,由于不具备完备信息,因此我们不作讨论。
4
5
这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中,双方都希望自己能够获胜。因此,当任何一方走步时,都是选择对自己最为有利,而对另一方最为不利的行动方案。
假设博弈的一方为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的立场上,因此应选择具有最大倒推值的走步。这一过程称为极大极