搜索(博弈樹(shù)的啟發(fā)式搜索)

《搜索(博弈樹(shù)的啟發(fā)式搜索)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、搜索策略博弈樹(shù)的啟發(fā)式搜索2博弈問(wèn)題如下棋、打牌、競(jìng)技、戰(zhàn)爭(zhēng)等一類(lèi)競(jìng)爭(zhēng)性智能活動(dòng)稱(chēng)為博弈。博弈有很多種，我們討論最簡(jiǎn)單的“二人零和、全信息、非偶然”博弈，其特征如下：雙人對(duì)弈，對(duì)壘的雙方輪流走步。零和。即對(duì)一方有利的棋，對(duì)另一方肯定是不利的，不存在對(duì)雙方均有利、或均無(wú)利的棋。對(duì)弈的結(jié)果是一方贏，而另一方輸，或者雙方和棋。信息完備，對(duì)壘雙方所得到的信息是一樣的，不存在一方能看到，而另一方看不到的情況。任何一方在采取行動(dòng)前都要根據(jù)當(dāng)前的實(shí)際情況，進(jìn)行得失分析，選取對(duì)自已為最有利而對(duì)對(duì)方最為不利的對(duì)策，不存在擲骰子之類(lèi)的"碰運(yùn)氣"因素。即雙方都是很理智

2、地決定自己的行動(dòng)。博弈是一類(lèi)富有智能行為的競(jìng)爭(zhēng)活動(dòng)，如下棋、打牌、戰(zhàn)爭(zhēng)等。博弈可分為雙人完備信息博弈和機(jī)遇性博弈。所謂雙人完備信息博弈，就是兩位選手對(duì)壘，輪流走步，每一方不僅知道對(duì)方已經(jīng)走過(guò)的棋步，而且還能估計(jì)出對(duì)方未來(lái)的走步。對(duì)弈的結(jié)果是一方贏，另一方輸；或者雙方和局。這類(lèi)博弈的實(shí)例有象棋、圍棋等。所謂機(jī)遇性博弈，是指存在不可預(yù)測(cè)性的博弈，例如擲幣等。對(duì)機(jī)遇性博弈，由于不具備完備信息，因此我們不作討論。45這里我們主要討論雙人完備信息博弈問(wèn)題。在雙人完備信息博弈過(guò)程中，雙方都希望自己能夠獲勝。因此，當(dāng)任何一方走步時(shí)，都是選擇對(duì)自己最為有利，而對(duì)

3、另一方最為不利的行動(dòng)方案。假設(shè)博弈的一方為MAX，另一方為MIN。在博弈過(guò)程的每一步，可供MAX和MIN選擇的行動(dòng)方案都可能有多種。從MAX方的觀點(diǎn)看，可供自己選擇的那些行動(dòng)方案之間是“或”的關(guān)系，原因是主動(dòng)權(quán)掌握在MAX手里，選擇哪個(gè)方案完全是由自己決定的；而對(duì)那些可供MIN選擇的行動(dòng)方案之間則是“與”的關(guān)系，原因是主動(dòng)權(quán)掌握在MIN的手里，任何一個(gè)方案都有可能被MIN選中，MAX必須防止那種對(duì)自己最為不利的情況的發(fā)生。6若把雙人完備信息博弈過(guò)程用圖表示出來(lái)，就可得到一棵與/或樹(shù)，這種與/或樹(shù)被稱(chēng)為博弈樹(shù)。在博弈樹(shù)中，那些下一步該MAX走步的節(jié)

4、點(diǎn)稱(chēng)為MAX節(jié)點(diǎn)，而下一步該MIN走步的節(jié)點(diǎn)稱(chēng)為MIN節(jié)點(diǎn)。博弈樹(shù)具有如下特點(diǎn)：（l）博弈的初始狀態(tài)是初始節(jié)點(diǎn)；（2）博弈樹(shù)中的“或”節(jié)點(diǎn)和“與”節(jié)點(diǎn)是逐層交替出現(xiàn)的；（3）整個(gè)博弈過(guò)程始終站在某一方的立場(chǎng)上，所有能使自己一方獲勝的終局都是本原問(wèn)題，相應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)；所有使對(duì)方獲勝的終局都是不可解節(jié)點(diǎn)。例如，站在MAX方，所有能使MAX方獲勝的節(jié)點(diǎn)都是可解節(jié)點(diǎn)，所有能使MIN方獲勝的節(jié)點(diǎn)都是不可解節(jié)點(diǎn)。一.博弈樹(shù)概述博弈問(wèn)題空間模型化只考慮兩個(gè)游戲者:MAX和MIN,兩個(gè)人輪流出招,直到游戲結(jié)束.四元組：（初始狀態(tài)，操作集合，終止測(cè)試（非目標(biāo)

5、測(cè)試），判定函數(shù)）初始狀態(tài)：包括棋局的局面和確定該哪個(gè)游戲者出招后繼函數(shù)：返回(move,state)對(duì)的一個(gè)列表,其中每一對(duì)表示一個(gè)合法的著數(shù)和其結(jié)果狀態(tài)終止測(cè)試：判斷游戲是否結(jié)束,游戲結(jié)束的狀態(tài)稱(chēng)為終止?fàn)顟B(tài)判定函數(shù)：又稱(chēng)為目標(biāo)函數(shù)或者收益函數(shù),對(duì)終止?fàn)顟B(tài)給出一個(gè)數(shù)值.（比如：可以-1表示輸，0表示和局，1表示贏）博弈的初始格局是初始節(jié)點(diǎn)在博弈樹(shù)中，"或"節(jié)點(diǎn)和"與"節(jié)點(diǎn)是逐層交替出現(xiàn)的。如果我們站在MAX方的立場(chǎng)上，則可供MAX方選擇的若干行動(dòng)方案之間是“或”關(guān)系，因?yàn)橹鲃?dòng)權(quán)操在MAX方手里，他或者選擇這個(gè)行動(dòng)方案，或者選擇另一個(gè)行動(dòng)方案，完

6、全由MAX方自已決定。當(dāng)MAX方選取任一方案走了一步后，MIN方也有若干個(gè)可供選擇的行動(dòng)方案，此時(shí)這些行動(dòng)方案對(duì)MAX方來(lái)說(shuō)它們之間則是"與"關(guān)系，因?yàn)檫@時(shí)主動(dòng)權(quán)操在MIN方手里，這些可供選擇的行動(dòng)方案中的任何一個(gè)都可能被MIN方選中，MAX方必須應(yīng)付每一種情況的發(fā)生。9對(duì)簡(jiǎn)單的博弈問(wèn)題，可以生成整個(gè)博弈樹(shù)，找到必勝的策略。但對(duì)于復(fù)雜的博弈，如國(guó)際象棋，大約有10120個(gè)節(jié)點(diǎn)，可見(jiàn)要生成整個(gè)搜索樹(shù)是不可能的。一種可行的方法是用當(dāng)前正在考察的節(jié)點(diǎn)生成一棵部分博弈樹(shù)，由于該博弈樹(shù)的葉節(jié)點(diǎn)一般不是哪一方的獲勝節(jié)點(diǎn)，因此，需利用估價(jià)函數(shù)f(n)對(duì)葉節(jié)點(diǎn)進(jìn)

7、行靜態(tài)評(píng)估，對(duì)MAX有利的節(jié)點(diǎn)其估價(jià)函數(shù)取正值；那些對(duì)MIN有利的節(jié)點(diǎn)，其估價(jià)函數(shù)取負(fù)值；那些使雙方均等的節(jié)點(diǎn)，其估價(jià)函數(shù)取接近于0的值。二.極大極小過(guò)程為了計(jì)算非葉節(jié)點(diǎn)的值，必須從葉節(jié)點(diǎn)向上倒推。對(duì)于MAX節(jié)點(diǎn)，由于MAX方總是選擇估值最大的走步，因此，MAX節(jié)點(diǎn)的倒推值應(yīng)該取其后繼節(jié)點(diǎn)估值的最大值。對(duì)于MIN節(jié)點(diǎn)，由于MIN方總是選擇使估值最小的走步，因此MIN節(jié)點(diǎn)的倒推值應(yīng)取其后繼節(jié)點(diǎn)估值的最小值。這樣一步一步的計(jì)算倒推值，直至求出初始節(jié)點(diǎn)的倒推值為止。由于我們是站在MAX的立場(chǎng)上，因此應(yīng)選擇具有最大倒推值的走步。這一過(guò)程稱(chēng)為極大極小過(guò)程。

8、下面給出一個(gè)極大極小過(guò)程的例子。極小極大法基本思想:首先假定，有一個(gè)評(píng)價(jià)函數(shù)可以對(duì)所有的棋局進(jìn)行評(píng)估。當(dāng)評(píng)價(jià)函數(shù)值大于0時(shí)，表示棋局對(duì)我