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

搜索策略
瘦喻蝎演狡针骇凌檄模抉闭惮鹅撩筒描涕窒收馈***宇泡瘟菊砰天瓤厢栅符搜索(博弈树的启发式搜索)搜索(博弈树的启发式搜索)
博弈树的启发式搜索
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方必须应付每一种情况的发生。
宇