機器博弈及其搜索算法的研究

摘要：機器博弈是人工智能一個傳統的研究領域。該文從機器博弈的基本理論談起，介紹了機器博弈理論和機器博弈系統的一般構成，尤其闡述了現今已存在的各種機器博弈搜索算法及其優缺點。

關鍵詞：博弈系統 ；博弈搜索算法；極大極小值算法；Alpha-beta剪枝算法

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)24-1269-03

Research of Machine Gambling and Searching Algorithm

ZHANG Zhen， GU Zhi-hua

(College of Computer Science， Wuhan University of Technology， Wuhan 430063， China)

Abstract: Machine gambling is a traditional research field of artificial intelligence. This article ，begins with the elementary theory of the machine gambling， introduces the machine gambling theory and the general constitution of the machine gambling system ，especially elaborates all kinds of searching algorithm of machine gambling and its advantages and disadvantages.

Key words: gambling system; gambling searching algorithm; minimax algorithm; alpha-beta pruning algorithm

1 引言

博弈一向被認為是富有挑戰行的智力游戲，有著難以言語的魅力。博弈雖然自古就是人與人的對弈，但自從有了計算機以后，人們就有了用計算機下棋的想法，早在上世紀五十年代，就出現了若干博弈程序。最近的一次是1999年IBM的“深藍”戰勝了國際象棋世界冠軍卡斯帕羅夫，驚動了世界。機器博弈的核心技術是博弈搜索算法，它與估值及規則（走法）構成一個完整的系統。

2 機器博弈的基本思想

機器博弈的核心思想并不復雜，實際上就是對博弈樹節點的估值過程和對博弈樹搜索過程的結合。在博弈的任何一個中間階段，站在博弈雙方其中一方的立場上，可以構想一個博弈樹。這個博弈樹的根節點是當前時刻的棋局，它的兒子節點是假設再行棋一步以后的各種棋局，孫子節點是從兒子節點的棋局再行棋一步的各種棋局，以此類推，構造整棵博弈樹，直到可以分出勝負的棋局。整棵的博弈樹非常龐大，且不同的棋類有所不同，分支因子大的如圍棋的博弈樹顯然要比分支因子小的如國際象棋的博弈樹要大得多。博弈程序的任務就是對博弈樹進行搜索找出當前最優的一步行棋。對博弈樹進行極大極小搜索，可以達到這一目的。極大極小搜索，是因為博弈雙方所要達到的目的相反，一方要尋找的利益恰是一方失去的利益，所以博弈的一方總是希望下一走是兒子節點中取值最大者，而另一方恰恰相反。這便形成了極大極小過程。在這個過程中，最為重要的是搜索算法，高效的搜索算法可以保證用盡量少的時間和空間損耗來達到尋找高價值的走步。但是真的想要博弈程序棋力提高，還必須有一個好的局面評價機制，即估值算法作后盾。就是說，用這個估值算法評價的局面價值必須是客觀的、正確的，可以確鑿的評價局面的優劣以及優劣的程度。

3 機器博弈系統

根據機器博弈的基本思想，可以確定一個機器博弈系統的一般構成。首先是知識表示的問題，選用一種合適的方法記錄棋局。這時需要考慮在這種知識表示的數據結構之上將要進行的各種操作，知識表示應該使最經常進行的操作花費的時間和空間代價最小。其次，根據不同的棋類的不同規則集，要有一個相應的走法產生機制。它的作用是用來產生整棵博弈樹，即處于博弈樹的任何一個節點位置上，應該能夠運用該機制產生這個節點的所有兒子節點，也就是接下來的所有合法走步。除了以上兩個模塊以外，就是博弈核心的搜索技術和與之配合的估值技術了。這四個部分相互配合運轉起來，就可以實現機器博弈。

4 基本搜索算法

4.1 極大極小值算法

假設有2個博弈者甲和乙(甲為計算機，乙為棋手)，在這個博弈事件中我們要為甲找到最佳的走步。現假設甲方先下，乙方后下，深度為奇數的節點為甲方下了一子之后的局面(即乙方選擇下法的局面)，稱之為極小節點;深度為偶數的節點為乙方下一子之后的局面(即甲方選擇下法的局面)，稱為極大節點;博弈樹的頂節點深度為0。一個最佳走步可以由一個極大極小化過程產生，甲方要從搜索樹中選擇擁有最大值的節點，因此，一個標有“甲”的節點的估計值可以由它的標有“乙”的子節點的最大值確定。另一方面，乙方從葉節點中選擇時，由于估計值越小對它越有利，因此必然選取估計值最小的節點(即最負的估計值)，因此，標有“乙”的節點估計值可由它的標有“甲”的子節點的最小值確定。綜上所述，可由博弈樹的葉節點出發向上一層層倒推，得到上一層的估計值，從而得出根節點的估計值，這樣就可以確定從根節點出發的最佳走步，稱之為極大極小值算法，其偽代碼如下：

double ji-da-ji-xiao(int depth)

{

int i;

double best， n;

if (比賽結束)

return evaluation ();

if (depth= =0)

return evaluation (); /*葉節點*/

if (甲方)

best = -1 000;

else

best =1 000; /*初始化當前最優值，假設1000為一個不可能達到的值*/

for (i=1;i<=w;i++)

{

n= ji-da-ji-xiao (depth-1);

if(n>best甲方)

best=n;

if(n

best=n;

}

return best;

}

4.2 Alpha-beta剪枝算法

在極大極小搜索的過程中，存在著一定程度的數據冗余，剔除這些冗余數據，是減小搜索空間的必然做法，所采用的方法就是1975年Monroe Newborn提出的Alpha-beta剪枝。把Alpha-beta剪枝應用到極大極小搜索或者負極大值搜索中就形成了alpha-beta搜索。其偽碼如下：

double Alpha-Beta (double alpha， double beta， int depth );

{

int i;

double n， best;

if (比賽結束)

return evaluation ();

if (depth= =0)

return evaluation (); /*葉結點*/

if (極大節點)

{

for(i=1; i<=w; i++)

{

n= Alpha-Beta (alpha ， beta ， depth-1);

if(best>alpha)

alpha = best;

}

return alpha;

}

else /*極小節點*/

{

for(i=1; i<=w; i++)

{

n= Alpha-Beta (alpha ， beta ， depth-1);

if(best

beta= best;

}

return beta;

}

}

5 Alpha-beta的增強算法

5.1 渴望搜索

在alpha-beta剪枝過程中，初始的的搜索窗口往往是從-∞（即初始的alpha值）到+∞（初始的beta值），在搜索進行中再不斷縮小窗口，加大剪枝效果。渴望搜索就是渴望從一開始就使用小的窗口，從而在搜索初起，就可以進行大量的剪枝。這個初始窗口的選定很重要，如果選擇準確，即所要尋找的走步就在這個窗口內，搜索便可以繼續進行。如果第一步搜索的返回值證明最佳走步大于beta值，就需要重新確定窗口。以原來的beta值為alpha值，以+∞為新的beta值重新搜索。相反如果第一步的返回值證明最佳走步小于alpha值，重新確定的窗口就是以-∞為alpha值，原來的alpha值為beta值了。可見第一次搜索猜測的窗口非常重要，如果猜測準確，搜索時間可以大大縮短，如果不準確，這一優勢就不明顯了。由于渴望搜索是一種基本的搜索方法，它在和后面敘述的遍歷深化結合使用的時候，就可以借助前一次深度為depth的搜索的結果來猜測當前深度為depth+1搜索的窗口了。

5.2 極小窗口搜索

極小窗口搜索，也被稱為是主變量導向搜索（Principal Variation Search），常常簡稱為PVS算法或者NegaScout算法。這個算法應用非常廣泛。它的出發點是和渴望搜索大致相同的，即用極小的窗口來限制剪枝范圍。它的過程是這樣的：在根節點處，假定第一個兒子節點為主變量，也就是假定它為最佳走步，對它進行完整窗口(a，b)的搜索并得到一個返回值v，對后面的兒子節點依次用極小窗口（也被稱為是零窗口）（v，v+1）來進行搜索，如果搜索返回值大于零窗口，則證明這一分支亦為主變量，對它進行窗口為（v+1，b）的搜索，可是如果返回值小于零窗口，這一分支就可以忽略，因為它的最佳走步還不如已有的走步。極小窗口搜索采用了極小的窗口，剪枝效率最高，并且只對主變量進行大窗口的搜索，所以大部分搜索動作是有效的，搜索產生的博弈樹也很小。

5.3 置換表

在搜索進行中，查詢所有的走步，經常會在相同的或者不同的路徑上遇到相同的棋局，這樣的子樹就沒有必要重復搜索，把子樹根節點的估值、子樹的最好走步和取得這個值的深度信息保存在一個稱為置換表的數據結構中，下次遇到時直接運用即可。但是，對不同的情況要區別對待。對于固定深度的搜索，如果前一次保存的子樹深度小于新節點要搜索的深度，還是要進行重新的搜索以保證所取得數據的準確程度。反之，如果置換表中保存的子樹信息表明，子樹的深度大于或者等于當前的新節點要求的搜索深度，它的信息就可以直接運用了。置換表增強如果和有效的alpha-beta搜索結合使用，結果就會使實際搜索的博弈樹小于最小樹。

5.4 遍歷深化

遍歷深化是因對博弈樹進行多次遍歷，又不斷加深其深度而得名，有人還把它稱為蠻力搜索。算法利用了alpha-beta算法對子節點排序敏感的特點。它希望通過淺層的遍歷給出節點的大致排序，把這個排序作為深層遍歷的啟發式信息。另外，算法用時間控制遍歷次數，時間一到，搜索立即停止，這也符合人類棋手的下棋特點。在關鍵的開局和殘局，由于分支較少，也可以進行較深層次的搜索。算法的過程是，對以當前棋局為根節點的博弈樹進行深度為二的遍歷，得出其兒子節點的優劣排序，接著再從根節點進行深度為三的遍歷，這一次優先搜索上次遍歷中得出的最優者，從而加大剪枝效果，以此類推，在進行第三次、第四次的遍歷，一直達到限定時間為止。由于這個算法的每次遍歷都從根節點開始，所以有人稱其為蠻力搜索，但實際上由于每次都可以優先搜索相對好的節點，導致剪枝效率增大，其實算法效率是很高的，目前這一算法也得到了廣泛的認可。

5.5 歷史啟發搜索

歷史啟發也是迎合alpha-beta搜索對節點排列順序敏感的特點來提高剪枝效率的，即對節點排序，從而優先搜索好的走法。所謂好的走法即可以引發剪枝的走法或者是其兄弟節點中最好的走法。一個這樣的走法，一經遇到，就給其歷史得分一個相應的增量，使其具有更高的優先被搜索的權利。殺手啟發實際上是歷史啟發的特例。它是把同一層中，引發剪枝最多的節點稱為殺手，當下次搜索時，搜索到同一層次，如果殺手走步是合法的話，就優先搜索殺手。

6 結束語

以上討論了博弈搜索算法的幾種算法，其中α-β剪枝算法比較成熟，是當前最常用的算法，在融合各種策略后具有很高的剪枝效率。如果能進一步改進數據結構和進行代碼優化以及使用開局、殘局庫可以使程序具有很高的效率智能。

參考文獻：

[1] 敖志剛.人工智能與專家系統導論[M].合肥:中國科技大學出版社，2002.

[2] Nilsson N.Artincial Intelligence:A new synthesis[M].北京:機械工業出版社，2000.

[3] 王小春．游戲編程（人機博弈）[M]．重慶：重慶大學出版社，2002.

[4] 蔡自興.人工智能及其應用[M].北京:清華大學出版社，1999.

[5] 徐心和，王驕.中國象棋計算機博弈關鍵技術分析[J].小型微型計算機系統，2006，27(6):961-969.