算法過程描述
我們在使用Alpha-Beta搜尋開始時調用如下語句:
alphabeta(depth,-INFINITY,INFINITY);
INFINITY是一個非常大的數,也就是偽代碼中的無窮大。這樣,一切可能的值都在-INFINITY~INFINITY這個範圍之中,在向下搜尋的過程中,alpha和beta的範圍不斷縮小,並因此而引發更多的剪枝,從而使搜尋效率提高。
如果我們在一開始就將-INFINITY和INFINITY換成一對小值,會如何呢?
這樣做實際上在根節點處就給出了小範圍的alpha和beta,讓剪枝在靠近根節點處就開始了。但是我們無法判定,搜尋的結果將在怎樣的一對alpha和beta之間。除非alpha和beta是負無窮和正無窮。
假定我們猜測搜尋的結果在x附近,那我們可以令alpha=x-window(window是要搜尋範圍的大小的一半),beta=x+window,調用Value=FAlphabeta(depth,x-window,x+window)來搜尋結果。特別是當window很小的時候,搜尋的效率會比較高,因為有了更多的剪枝。
可能得到的結果有三種:
①返回的值Value落在(x-window,x+window)區間內。這種情況下,我們知道要找的值就在猜測的範圍內,可以直接使用導致此值得BestMove。
②返回的值Value大於或者等於x+window。在這種情況下,我們知道要找的值大於等於x+window,但是不知道它的精確值是多少。所以這種情形被稱為fail high,此時無疑需要重新給定範圍,再次搜尋才能找到所要的走法。由於已知要找的值位於value到正無窮之間,通常在重新搜尋時會令根結點處的alpha=value,beta=INFINITY,也就是調用FAlphabeta(depth,value,INFINITY);
③返回的值Value小於或者等於x-window。在這種情況下,我們也知道實際的值小於等於x-window,但是不知道它的精確值是多少。所以這種情形被稱為fail low。此時也需要重新給定範圍,再次搜尋才能找到所要的走法。由於已知要找的值位於負無窮到value之間,通常在重新搜尋時會令根節點處的alpha=-INFINITY,beta=value,也就是調用FAlphabeta(depth,-INFINITY,value)。
上面所述方法就是渴望搜尋算法。
偽代碼描述
類C偽代碼
int alpha=X-WINDOW;
int beta=X+WINDOW;
for(;;)
{
score=FAlphabeta(depth,alpha,beta);
if(score<=alpha)
alpha=-WIN;
else if(score>=beta)
beta=WIN;
else break;
}
偽代碼里的FAlphabeta即指調用Fail-soft alpha-beta搜尋。
具體分析
雖然當第一次猜測命中的時候,搜尋的時間大大縮短了,但由於會出現2種失敗的情形,引發的重新搜尋會使搜尋時間上的優勢喪失。顯然,如何猜的準一些是渴望搜尋提高效率的重要問題。
比較普遍的做法是記錄上一次搜尋得到的值,作為當前這一次的X,因為兩次搜尋在相當多的時候結果是接近的。也可以先進行一次深度為depth-1的搜尋,將返回值作為深度搜尋為depth的搜尋的X。一般情況下深度為depth-1的搜尋花費的時間僅為深度為depth的搜尋時間的1/15到1/5。
對於渴望搜尋的效率,各種資料上反映不一。相當多的評論者認為,由於渴望搜尋的窄窗引發了更多的剪枝,因而能夠大幅度提高搜尋效率。但J.Schaeffer在其論文中則提出,在實際的博弈環境中,他的實驗表明,渴望搜尋僅在層次較深的情形下略微優於Alpha-Beta搜尋。也就是說,在實驗室里認為構造的博弈樹,同實際的博弈環境下的效率有很大差異。
範例描述
該範例僅是一個搜尋核心類。可以從中比較渴望搜尋同Alpha-Beta的效率差異。下圖(頭檔案)是頭檔案AspirationSearch.h,渴望搜尋引擎的定義。我們從頭檔案中可以看出,這個引擎是從Fail-soft alpha-beta搜尋引擎繼承來的。渴望搜尋是通過調用CFAlphaBeta類中的FalphaBeta搜尋中實現的。
下圖(實現部分)是CaspirationSearch的實現部分,由於是從CFAlphabeta類派生而來,使用了基類的FalphaBeta,所以非常簡單,只實現了SearchAGoodMove函式。
新生成的類CaspirationSearch加入New Game的搜尋引擎列表,運行範例程式進行實驗,可以發現4層以上的搜尋當中,渴望搜尋的速度還是明顯的快於Alpha-Beta搜尋的速度。