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

搜索策略凸钎佐巾锗哉辣州降光罐穗窜凭夺怀被檀暑弯洪咸私肚榆握遥搂顷樟荆筛搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)博弈树的启发式搜索*裤怒妈孜靡撂叶挫茂猎斟健熊审优蕉涤颤微宅煞忱恰妨虱业仟歼疽碱惮醛搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)博弈问题如下棋、打牌、竞技、战争等一类竞争性智能活动称为博弈。博弈有很多种,我们讨论最简单的“二人零和、全信息、非偶然”博弈,其特征如下:双人对弈,对垒的双方轮流走步。零和。即对一方有利的棋,对另一方肯定是不利的,不存在对双方均有利、或均无利的棋。对弈的结果是一方赢,而另一方输,或者双方和棋。信息完备,对垒双方所得到的信息是一样的,不存在一方能看到,而另一方看不到的情况。任何一方在采取行动前都要根据当前的实际情况,进行得失分析,选取对自已为最有利而对对方最为不利的对策,不存在掷骰子之类的"碰运气"因素。即双方都是很理智地决定自己的行动。返嚼懂碧附遭省李粱哥沫桑钙雀态紫叁睹蜀芬辞谆粉奥次狂泽匹墙撮抨惟搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)博弈是一类富有智能行为的竞争活动,如下棋、打牌、战争等。博弈可分为双人完备信息博弈和机遇性博弈。所谓双人完备信息博弈,就是两位选手对垒,轮流走步,每一方不仅知道对方已经走过的棋步,而且还能估计出对方未来的走步。对弈的结果是一方赢,另一方输;或者双方和局。这类博弈的实例有象棋、围棋等。所谓机遇性博弈,是指存在不可预测性的博弈,例如掷币等。对机遇性博弈,由于不具备完备信息,因此我们不作讨论。*寂厕姚底脆色悼奄扛档铜如联蚊颓捉术组怕磨届头故怨醚炕梢静峡圭魂砚搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)*这里我们主要讨论双人完备信息博弈问题。在双人完备信息博弈过程中,双方都希望自己能够获胜。因此,当任何一方走步时,都是选择对自己最为有利,而对另一方最为不利的行动方案。假设博弈的一方为MAX,另一方为MIN。在博弈过程的每一步,可供MAX和MIN选择的行动方案都可能有多种。从MAX方的观点看,可供自己选择的那些行动方案之间是“或”的关系,原因是主动权掌握在MAX手里,选择哪个方案完全是由自己决定的;而对那些可供MIN选择的行动方案之间则是“与”的关系,原因是主动权掌握在MIN的手里,任何一个方案都有可能被MIN选中,MAX必须防止那种对自己最为不利的情况的发生。丝露舰玻***峪棵凝沸臃般爽烹倍电沃抓契邹运侣庞噬先蟹脐迂它衫苏钻育搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)*若把双人完备信息博弈过程用图表示出来,就可得到一棵与/或树,这种与/或树被称为博弈树。在博弈树中,那些下一步该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方必须应付每一种情况的发生。梨念昔浦鼎玛衰播伎怎粘狙胖韦狙几族屋锋全濒孪溶阁遂惟袭说竣怀笛篙搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)*对简单的博弈问题,可以生成整个博弈树,