最小最大搜索 Alpha-Beta搜索

《最小最大搜索 Alpha-Beta搜索》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、最小-最大和負(fù)值最大搜索　　搜索樹中有三種類型的結(jié)點(diǎn)：　　(1)偶數(shù)層的中間結(jié)點(diǎn)，代表棋手甲要走的局面；　　(2)奇數(shù)層的中間結(jié)點(diǎn)，代表棋手乙要走的局面；　　(3)葉子結(jié)點(diǎn)，代表棋局結(jié)束的局面，即棋手甲或棋手乙獲勝，或者是和局?！〔┺臉涞脑u(píng)價(jià)　　　假設(shè)某個(gè)中間結(jié)點(diǎn)的所有子結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，那么棋局會(huì)在一回合內(nèi)結(jié)束?，F(xiàn)在我們假設(shè)棋手會(huì)挑選最好的著法，如果有一個(gè)著法能使他贏下棋局，那么他一定會(huì)走這步。如果沒有可以贏的著法，但是有取得和局的著法，那么他會(huì)走這步取得和局的著法。但是，如果所有的著法都使得對(duì)手獲勝，那么無論如何他都會(huì)輸?！　∫虼嗽谌~子結(jié)點(diǎn)的上一層結(jié)點(diǎn)，我們就能知道棋局

2、的結(jié)果。現(xiàn)在我們知道了這個(gè)結(jié)點(diǎn)的結(jié)果，那么我們可以用同樣的方法作推演，知道葉子結(jié)點(diǎn)的上兩層結(jié)點(diǎn)的結(jié)果，然后是上三層結(jié)點(diǎn)，等等，直到我們達(dá)到搜索樹的根結(jié)點(diǎn)。在每個(gè)結(jié)點(diǎn)上，棋手只要找到一個(gè)子結(jié)點(diǎn)能讓他獲勝，那么他就可以贏下棋局；他只要找到一個(gè)形成和局的子結(jié)點(diǎn)，棋局就和了；如果獲勝與和局的子結(jié)點(diǎn)都沒有，那么肯定是輸?shù)摹Ｈ绻覀冇凶銐蚨嗟臅r(shí)間來計(jì)算，那么這就給了我們一個(gè)可以下棋的完美算法。但是對(duì)于任何常規(guī)的棋類游戲，我們都不可能有足夠的計(jì)算時(shí)間，因?yàn)樗阉鳂鋵?shí)在太大了?！　×硗?，“正確”的評(píng)價(jià)函數(shù)只有三個(gè)值，贏、輸或者和局。在實(shí)際的棋類程序中，我們通常使用一個(gè)更寬泛的實(shí)數(shù)來作評(píng)價(jià)值，

3、就是因?yàn)橼A、輸或者和局是不確定的。如果棋手甲獲勝的值用+1表示，和局的值用0表示，棋手乙獲勝的值用-1表示，那么博弈樹的每個(gè)中間結(jié)點(diǎn)的值就是子結(jié)點(diǎn)的最大值或最小值，這取決于棋手甲還是棋手乙著棋?！〔糠值牟┺臉洹　　≡趯?shí)戰(zhàn)中，我們的搜索算法只能對(duì)博弈樹展開一部分。我們用一些“中止規(guī)則”來決定搜索樹展開到哪個(gè)結(jié)點(diǎn)就停下來，例如我們?cè)?步變化以后聽下來。由于棋局沒有在葉子結(jié)點(diǎn)結(jié)束，我們只能用評(píng)價(jià)函數(shù)來猜哪一方獲勝。現(xiàn)在我們來假設(shè)在我們展開的結(jié)點(diǎn)中，棋手甲總是希望棋局到達(dá)評(píng)價(jià)函數(shù)大的局面，而棋手乙總是希望棋局到達(dá)評(píng)價(jià)函數(shù)小的局面?！　∪绻p方都用這種方法來下棋，那么我們可以使用同樣

4、的最小-最大過程，來確定到達(dá)的葉子結(jié)點(diǎn)的評(píng)價(jià)值，這個(gè)過程如下：對(duì)每個(gè)中間結(jié)點(diǎn)，計(jì)算子結(jié)點(diǎn)的最大值或最小值，這取決于是棋手甲還是棋手乙走棋。到達(dá)葉子結(jié)點(diǎn)的線路稱為“主要變例”(PrincipalVariation)。最小-最大博弈樹的基本原理，就是對(duì)博弈樹作部分展開，去找主要變例，并走出變例中的第一步?！V度優(yōu)先和深度優(yōu)先搜索，負(fù)值最大代碼　　　正如上面所講的，計(jì)算博弈樹的值是一個(gè)廣度優(yōu)先的過程(我們要自下而上地，一次一層地計(jì)算)。然而實(shí)戰(zhàn)中，我們使用深度優(yōu)先(即后序遍歷)的遞歸過程來遍歷搜索樹，即要得到一個(gè)結(jié)點(diǎn)的值，就對(duì)子結(jié)點(diǎn)做遞歸，然后根據(jù)它們的返回值來決定自身的返回值。

5、這樣要節(jié)省很多空間，因?yàn)椴恍枰獊泶鎯?chǔ)整個(gè)博弈樹，而只是存儲(chǔ)一條線路(相對(duì)來說非常短，例如上面提到的8步中止的規(guī)則)。下次我們討論Alpha-Beta搜索時(shí)，會(huì)發(fā)現(xiàn)深度優(yōu)先的遍歷會(huì)有很大的優(yōu)勢(shì)，你可以用目前得到的信息來決定某些結(jié)點(diǎn)是不需要訪問的，這樣就節(jié)省下很多的時(shí)間?！　≈灰獙?duì)搜索樹的值作一個(gè)很小的改動(dòng)，就可以用一個(gè)求最大值的操作來代替最小值和最大值交替的過程。在搜索樹的奇數(shù)層(即輪到棋手乙下棋的結(jié)點(diǎn))，就對(duì)上面提到的評(píng)價(jià)值取負(fù)數(shù)。因此在每個(gè)結(jié)點(diǎn)上，這些值都可以由子結(jié)點(diǎn)的負(fù)值求得。我把博弈樹搜索的源代碼寫出來，恐怕就會(huì)清楚很多了。　//將博弈樹搜索到一定的深度，返回根結(jié)點(diǎn)的

6、評(píng)價(jià)值doublenegamax(intdepth){　if(depth<=0

7、

8、棋局結(jié)束)　　returneval(pos);　else{　　doublee=-infty;　　for(當(dāng)前局面所有可能的著法m){　　　執(zhí)行著法m;　　　e=max(e,-negamax(depth-1));　　　撤消著法m;　　}　　returne;　}}　　　注意，這個(gè)過程只能找到評(píng)價(jià)值，但是無法得知著法。我們只要在搜索樹的根結(jié)點(diǎn)找到著法(盡管很多程序都返回整個(gè)主要變例)就可以了，要做到這一點(diǎn)，可以對(duì)根結(jié)點(diǎn)的搜索稍作改動(dòng)：　//將博弈樹搜索到一定的深度，返回根結(jié)點(diǎn)的著法moveroots

9、earch(intdepth){　doublee=-infty;　movemm;　for(當(dāng)前局面所有可能的著法m){　　執(zhí)行著法m;　　doubleem=-negamax(depth-1);　　if(e