-
窗口搜索
鎖定
在計算機博弈程序中，通常採用是Alpha-Beta算法，為了進一步提高搜索速度，先後又出現了一些改進的算法。窗口搜索便是博弈樹搜索算法的優化。
- 中文名
- 窗口搜索
- 適用領域
- 博弈樹搜索
- 應用學科
- 計算機
窗口搜索渴望搜索
窗口搜索算法思路
渴望搜索是一種為了縮小搜索範圍而實現的算法，它的原理是將a一p剪枝看作是一種對求解的範圍不斷縮小的過程。在一定的範圍裏面，如果能夠精確預計搜索將會得到的值,那麼搜索的效率是可以大大提高的，在極限情況下，如果預計的完全準確,那麼剪枝的效率將和原來的樹的總節點數相同。但是,顯然這樣的預計是不可能的，所以渴望搜索將預計的結果增加一個範圍,來加強搜索命中的概率。
窗口搜索算法流程
渴望搜索一共分為三步：
第一步完全搜索深度為N-1時候的情況，並且得到解值X；
第二步建立新窗口(a，b)，其中a=X-windwos，b=X+windows進行深度為N的搜索；
第三步將得到的值和原來的a，b比較，如果落在這個範圍裏面就表示猜測命中,反之,需要根據情況進行偏高和偏低處理。
這樣的設計雖然可能大大增加剪枝數量,但是也會引起一個新的問題，當猜測值落在(alpha,beta)這個區間範圍之外，就不能得到最優解了，而且我們也不知道到底結果是落在區間的左邊亡
還是落在區間的右邊
。這就要求我們改善原有的Alpha一Beta算法，讓它至少告訴我們在搜索失敗的情況下到底是因為結果落在區間的左邊還是右邊，所以我們改變原來的算法，讓它能夠返回計算值。
intFalPhabeta(intnPly,intalpha,intbeta)
{
curreent=-INFINITY//可能的最佳值為最小值
if(Gameove)
rerturn evaluation();//勝負己分,返回估值
if(depth==0)//葉子節點
return eveluation();//調用估值函數,返回估值
for(each Possible move m)//對每一種可能的行動進行測試
{
MakeMove(m); //虛擬採取這個行動
value=-Falphabeta(nPly,-beta,-alPha);//遞歸搜索子節點
UnMakeMove(m);//分析後復原原來的局面
if(value>current)
{
current=value; //保留極大值
if(value>=alpha)
alpha=value;//修改邊界
}
if(alpha>=beta)
break;//beta剪枝
}
return current;//返回最大值
}
從上面的偽代碼中我們可以看到，程序中新加入一個current的量，這樣做的好處在於，得到的返回值可以記錄在這個變量裏面，它能夠告訴上一層記錄如果失敗，到底失敗的原因是因為估計值偏大還是偏小。
有了這個保證之後，我們仍然需要對上面的思想提供處理異常的措施，根據分析，進行縮小範圍的搜索後可能出現下面三種情況的一種，我們需要分別為它們制定策略：
(1)返回值恰好落在我們估計的範圍之內，這種情況下説明我們已經得到了最優解，不需要再執行其他措施就能得到最優解了。
(2)返回值落在估計範圍的左邊，也就是我們過高估計了我們的形式,實際上要糟糕一點，這時我們要從
的區間重新分析這個問題。我一開始分析的時候一直不能明白為什麼current的結果就不是那個最優解，分析後得到是：current只是一個和alpha比較的值，它只能説明得到的所有current都比alpha小，而最後得到的那個current是不是眾多current中最小的那個沒有辦法保證，所以我們需要重新計算。
(3)返回值落在估計範圍的右邊，也就是我們低估了自己的形式,實際上要好一點,這時我們要從
的區間重新分析這個問題。
這種算法之所以稱為渴望,也正因為它一直希望得到一個較小的搜索範圍，下面我們看一下它的偽代碼:
int AsPirationseareh(int depth)
{
int x=FAlphaBeta(depth-1,-INFINITY,INFINIYT);//計算出n一1層的最佳值
int alpha=X-WINDOW:
int beta=X+WINDOW
int current=AFlPhaBeta(depth,alpha,beta);//確定左右邊界,進行搜索
if(current<alpha)
current=FAIphabeta(depth,-INFINITY,alpha);//處理估值偏高情況
if(current>beta)
current=FAlphaBeta(depth,beta,INFINIYT);//處理估值偏低情況
return current;//返回估值
}
窗口搜索極小窗口搜索
窗口搜索算法思路
第二種減少窗口範圍的思想被稱為空窗口搜索或極小窗口搜索。因為從上面的算法我們可以看到，窗口越小那麼可能減去的枝會越多,那麼當窗口是O的情況下，會發生什麼樣的變化呢?
同時，極小窗口搜索和渴望搜索不同的地方在於它是根據完全搜索第一個節點作為估計值的，它的優點就在於,它有一個保留的最小值，也就是説在最好的情況下第一個節點就是最優解行動帶來的,那麼它也就是樹的最優值。極小窗口搜索會帶來效率的一定增加，而且可以避免渴望搜索的一些問題，但同小窗口搜索一樣，我們也要解決如何判斷估值的問題。
窗口搜索算法流程
極小窗口搜索的流程可以分為五步：
(1)對於第一個節點,我們按照原來的範圍
進行搜索，我們會得到一個最優解bestvalue。
(2)我們用(besvtalue,bestvalue+1)作為窗口進行測試。
(3)如果得到的值大於bestvaufe並且小於beta時，就説明有更好的方法，需要對(bestvalue,beta)進行測試。
(4)如果不是，再判斷得到的值value大於bestvalue，就説明value是一個更好的行動，應該用它來代替原來的bestvalue。
(5)如果得到的值value小於bestvalue，説明這種策略還不如以前的策略，不同再分析。
在這個算法中比較難以理解的是第(3)步，因為按照最初的思想(3)和(4)兩步應該是可以統一的,既在新分析的value大於bestvalue時就表示有更好的值，只要替換原來的最佳值就可以了，為什麼還需要分為兩種情況考慮呢，原因就在於極小窗口。其實(3)和(4)是在兩種情況下采取的策略:(4)對應於極小窗口搜索，當value大於bestvalue時，value同時也大於bestvalue+1，這是因為估值函數中不存在最小估計為1之間的差別；對於(3)則是對應於一般的窗口搜索，它説明另一棵子樹中有更好的策略，但是我們並不清楚這個策略的具體值是多少，所以我們需要在(value,beta)中繼續找尋更好的行動。這也是這個算法難以理解的地方。下面給出偽代碼的實現:
intPrinciPalVariation(int nPly,int alpha,int beta)
{
if(Gameover)
return evaluation();//勝負已分,返回估值
if(depth==0)//葉子節點
return evaluation();//調用估值函數,返回估值
MakeMove(m);//測試第一個節點
best=-PrincipalVariation(nPly-l,-beta,-alpha) //計算第一個節點的值
UnMakeMove(m);//分析後復原原來的局面
fore(each possbiel move m)//對每一種可能的行動進行測試(從第二個節點)
{
if(best<beta)//是否不能進行beta剪枝
{
MakeMove(m);//虛擬採取這個行動
value=-Principalvariation(nply-l,-alpha-l,-alpha);//極小窗口測試
if(value>alpha && value<beta)//估值過低,重新完整估值
best=-PrineipalVariation(nPly-l,-beta,-value);
else if(value>best)//命中
best=value;
unMakeMove(m)://恢復行動
}
}
return best;//返回最大值
}
- 參考資料
-
- 1. 博弈樹搜索算法的研究及改進 ．中國知網．2006[引用日期2016-03-26]
- 詞條統計
-
- 瀏覽次數：次
- 編輯次數：2次歷史版本
- 最近更新： 阿妧云