搜索博弈树的启发式搜索.pptx

该【搜索博弈树的启发式搜索 】是由【niuwk】上传分享，文档一共【34】页，该文档可以免费在线阅读，需要了解更多关于【搜索博弈树的启发式搜索 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。博弈问题
如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种,我们讨论最简单的“二人零和、全信息、非偶然”博弈,其特征如下:
双人对弈,对垒的双方轮流走步。
零和。即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利、或均无利的棋。对弈的结果是一方赢,而另一方输,或者双方和棋。
信息完备,对垒双方所得到的信息是一样的,不存在一方能看到,而另一方看不到的情况。
任何一方在采取行动前都要根据当前的实际情况,进行得失分析,选取对自已为最有利而对对方最为不利的对策,不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。
第1页/共34页
博弈是一类富有智能行为的竞争活动,如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈,就是两位选手对垒,轮流走步,每一方不仅知道对方已经走过的棋步,而且还能估计出对方未来的走步。对弈的结果是一方赢,另一方输;或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈,是指存在不可预测性的博弈,例如掷币等。对机遇性博弈,由于不具备完备信息,因此我们不作讨论。
2
第2页/共34页
3
这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中,双方都希望自己能够获胜。因此,当任何一方走步时,都是选择对自己最为有利,而对另一方最为不利的行动方案。
假设博弈的一方为MAX,另一方为MIN。在博弈过程的每一步,可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看,可供自己选择的那些行动方案之间是“或”的关系,原因是主动权掌握在MAX手里,选择哪个方案完全是由自己决定的;而对那些可供MIN选择的行动方案之间则是“与”的关系,原因是主动权掌握在MIN的手里,任何一个方案都有可能被MIN选中,MAX必须防止那种对自己最为不利的情况的发生。
第3页/共34页
4
若把双人完备信息博弈过程用图表示出来,就可得到一棵与/或树,这种与/或树被称为博弈树。在博弈树中,那些下一步该MAX走步的节点称为MAX节点,而下一步该MIN走步的节点称为MIN节点。博弈树具有如下特点:
(l)博弈的初始状态是初始节点;
(2)博弈树中的“或”节点和“与”节点是逐层交替出现的;
(3)整个博弈过程始终站在某一方的立场上,所有能使自己一方获胜的终局都是本原问题,相应的节点是可解节点;所有使对方获胜的终局都是不可解节点。例如,站在MAX方,所有能使MAX方获胜的节点都是可解节点,所有能使MIN方获胜的节点都是不可解节点。

第4页/共34页
博弈问题空间模型化
只考虑两个游戏者:MAX和MIN,两个人轮流出招,直到游戏结束.
四元组:
(初始状态,操作集合,终止测试(非目标测试),判定函数)
初始状态:包括棋局的局面和确定该哪个游戏者出招
后继函数:返回(move,state)对的一个列表,其中每一对表示一个合法
的着数和其结果状态
终止测试:判断游戏是否结束,游戏结束的状态称为终止状态
判定函数:又称为目标函数或者收益函数,对终止状态给出一个数值.
(比如:可以-1表示输,0表示和局,1表示赢)
第5页/共34页
博弈的初始格局是初始节点
在博弈树中,"或"节点和"与"节点是逐层交替出现的。
如果我们站在MAX方的立场上,则可供MAX方选择的若干行动方案之间是“或”关系,因为主动权操在MAX方手里,他或者选择这个行动方案,或者选择另一个行动方案,完全由MAX方自已决定。
当MAX方选取任一方案走了一步后,MIN方也有若干个可供选择的行动方案,此时这些行动方案对MAX方来说它们之间则是"与"关系,因为这时主动权操在MIN方手里,这些可供选择的行动方案中的任何一个都可能被MIN方选中,MAX方必须应付每一种情况的发生。
第6页/共34页
7
对简单的博弈问题,可以生成整个博弈树,找到必胜的策略。但对于复杂的博弈,如国际象棋,大约有10120个节点,可见要生成整个搜索树是不可能的。一种可行的方法是用当前正在考察的节点生成一棵部分博弈树,由于该博弈树的叶节点一般不是哪一方的获胜节点,因此,需利用估价函数f(n)对叶节点进行静态评估,对MAX有利的节点其估价函数取正值;那些对MIN有利的节点,其估价函数取负值;那些使双方均等的节点,其估价函数取接近于0的值。

为了计算非叶节点的值,必须从叶节点向上倒推。对于MAX节点,由于MAX方总是选择估值最大的走步,因此,MAX节点的倒推值应该取其后继节点估值的最大值。对于MIN节点,由于MIN方总是选择使估值最小的走步,因此MIN节点的倒推值应取其后继节点估值的最小值。这样一步一步的计算倒推值,直至求出初始节点的倒推值为止。由于我们是站在MAX的立场上,因此应选择具有最大倒推值的走步。这一过程称为极大极小过程。
下面给出一个极大极小过程的例子。
第7页/共34页
极小极大法
基本思想:
首先假定,有一个评价函数可以对所有的棋局进行评估。
当评价函数值大于0时,表示棋局对我方有利,对对方不利;
当评价函数小于0时,表示棋局对我方不利,对对方有利;
而评价函数值越大,表示对我方越有利。当评价函数值等于正无穷大时,表示我方必胜。
评价函数值越小,表示对我方越不利。当评价函数值等于负无穷大时,表示对方必胜;
假设双方都是对弈高手,在只看一步棋的情况下,我方一定走评价函数值最大的一步棋,而对方一定走评价函数值最小的一步棋。
第8页/共34页
人下棋的思考方式
人下棋实际上采用一种试探性的方法:
假定走了一步棋,看对方会有哪些应法;
再根据对方的每一种应法,看我方是否有好的回应;
这一过程一直进行下去,直到若干步后,找到一个满意的走法为止.
极大极小搜索方法模拟的就是人的这样一种思维过程.
第9页/共34页
极大极小搜索方法是一种在有限搜索深度范围进行求解的方法.
A
B
C
D
3
12
8
2
14
5
2
4
6
b1
b2
b3
3
c1
c2
c3
2
d1
d2
d3
2
a1
a2
a3
MAX
MIN
3
定义一个静态估计函数f,以便对棋局的叶子节点作出优劣估值

,如A节点的估计值是3
,如D节点的估计值是2
,计算所有叶节点的评价函数值。
获得根节点取值的那一分枝,即为所选择的最佳走步
节点A,轮到MAX下棋….
第10页/共34页