在計算機博弈程式中，通常採用是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;//返回估值}上面代碼中的FAlphaBeta是設計用來返回估值的那個函式.
極小視窗搜尋
算法思路
第二種減少視窗範圍的思想被稱為空視窗搜尋或極小視窗搜尋。因為從上面的算法我們可以看到，視窗越小那么可能減去的枝會越多,那么當視窗是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;//返回最大值}從代碼中可以看出，一開始測試的條件“best<beat”是用來保證不能進行beat剪枝的，然後才會有空視窗探測的問題。
