渴望搜尋算法（Aspiration Search），這種算法是基於Fail-soft alpha-beta的搜尋算法。在最外部調用時與基本的Alpha-Beta不同。
基本介紹
- 中文名：“渴望搜尋”算法
- 外文名：Aspiration Search Algorithm
算法過程描述,偽代碼描述,類C偽代碼,具體分析,範例描述,
算法過程描述
我們在使用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的效率差異。圖1（頭檔案）是頭檔案AspirationSearch.h，渴望搜尋引擎的定義。我們從頭檔案中可以看出，這個引擎是從Fail-soft alpha-beta搜尋引擎繼承來的。渴望搜尋是通過調用CFAlphaBeta類中的FalphaBeta搜尋中實現的。
圖1 頭檔案
圖2（實現部分）是CaspirationSearch的實現部分，由於是從CFAlphabeta類派生而來，使用了基類的FalphaBeta，所以非常簡單，只實現了SearchAGoodMove函式。
圖2 實現部分.1
圖2 實現部分.2
新生成的類CaspirationSearch加入New Game的搜尋引擎列表，運行範例程式進行實驗，可以發現4層以上的搜尋當中，渴望搜尋的速度還是明顯的快於Alpha-Beta搜尋的速度。
