智能五子棋博弈算法研究

摘要：人工智能是一門正在迅速發展的新興的綜合性很強的邊緣科學。博弈是人工智能的主要研究領域之一，他涉及人工智能中的推理技術、搜索方法和決策規劃。本文將這些技術用于五子棋中。設計了一個智能五子棋系統，實現人和計算機兩方進行博弈。

關鍵詞：五子棋 人工智能 搜索

人工智能是一門綜合性很強的邊緣科學，它研究如何使計算機去做那些過去只能靠人的智力才能做的工作。而博弈是人工智能研究的一個重要分支，它不僅存在于游戲、下棋之中，也存在于政治、經濟、軍事和生物競爭中。

五子棋是起源于中國古代的傳統黑白棋種之一。現代五子棋日文稱之為“連珠”，英譯為“Ren-ju”，英文稱之為“Gobang”或“FIR”（Five in a Row的縮寫），亦有“連五子”、“五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。與其他棋類相比，五子棋每一層搜索節點數量龐大，因此盤面預測的計算量是非常大的，比如對于五子棋的中盤走法中，如果要預測四步的局面數的話可以達到一百萬。

本文是對五子棋算法的設計原理和實現方法進行探討和研究，主要包括數據結構、搜索算法和優劣評價函數組成，主要的特點包括快速的數據結構設計實現、以及高效率的搜索算法和盡可能的模擬人類的智能。

1、棋局的數據結構表示

我們知道五子棋的走法中有優先和禁手，如連四肯定是沒有三四優先，而如果是黑方出現三三（包括“四、三、三”）、四四（包括“四、四、三”），而黑方只能以四三取勝，如果黑方走出禁手則是輸；五連與禁手同時形成，先五為勝，等等的規矩。但是電腦畢竟不是人類，可以類人但是卻不可以自己思考，那么就需要給電腦一個它可以明白的評判標準。

下面，我列出基本的棋型優先順序：

造一個二<……<造四個二<沖三<……<沖兩個二和一個三<沖雙三<沖四<沖四三。

之所以這么設置是由于五子棋的下法所致，只要構成5顆一線就贏了，所以說一條線上構成的越多那么就有優勢，當然就是棋數越多，分越多。

那么為了讓電腦明確的知道是不是應該落子，就給它一個標準：分值。用程序語言表示：

enum Value {FAILED=-99999，SKIP=20，LENG=10，TWO =100，THREE =1000， IF0UR =10000，FOUR =50000，SF0UR=70000，WIN=100000}；

如果某一點導致失敗，則分值為FAILED，由于它足夠小，所以無論任何棋型與它的組合都小于0，SKIP之所以給它20分，是為了避免電腦出現無棋可下的情況，LENG是有可能發生長連的點，這有可能導致禁手，TWO、THREE、FOUR、WIN 觀名知意，TFOUR 和SFOUR分別是弱四和強四。強四的點比普通的沖四重要的多，比如一個活四，意味著即將判出勝負。弱四是為了提供更大的靈活。也許有某種沖四并不一定比沖三重要，我在這里并沒有使用，以后可以擴充。

2、五子棋算法介紹及初步實現

2.1 五子棋博弈樹中的極大極小搜索和α-β剪枝

為了使談論更有條理性[5]，將博弈的雙方分別命名為MAX和MIN。而搜索的任務是為MAX找最佳的移動。假設MAX先移動（此時暫時不考慮五子棋的禁手等規則），然后2個博弈者輪流移動。因此，深度為偶數的節點，對應于MAX下一步移動的位置，稱為MAX節點；深度為奇數的節點對應于MIN下一步移動的位置，稱為MIN節點（博弈樹的頂節點深度為0）。k層包括深度為2k和2k+1的節點。通常用層數表示博弈樹的搜索深度。他可以表示出向前預測的MAX和MIN交替運動的回合數。

用整個棋盤估值的函數h（n）為靜態估值函數。設想當前棋局S為輪到計算機方下棋（用方框表示），任選一空點作為計算機方的下棋位置（可有若干種選擇），接著考慮在此情況下游戲者一方下棋的棋局（用圓圈表示）；從某一個圓圈棋局出發，任選一空點作為游戲者一方的落子處（又有若干種選擇）。再次形成計算機方下棋的方框棋局；依此類推，這樣可形成一棵以S為根結點的博弈樹，該樹以圓圈棋局為第2層子結點，以方框棋局為第3層子結點等等。如果繼續向前搜索，可形成多層子結點，現在以向前搜索3層子結點為例來說明極大極小值的過程。對第3層子結點的某一棋局n，求出其估計值h（n），假設有一博弈樹已形成，如圖1所示[2]，h（n）的值由各結點旁的數值給出。

根據極小極大化分析法，先計算第3層子結點h（n）值，然后第2層子結點的估計值取他的各后繼子結點的極小值，根結點的估計值取他的各子結點的極大值。這個取得最大估計值的子結點即為從S出發的計算機方的最佳落子方案。棋盤上某一行、某一列或某一對角線為一路，這里使用的棋盤為19行19列，因此，行和列方向上共有19+19=38路；從左下到右上方向的對角線有37路，同樣，從左上到右下方向的對角線也有37路。但對于五子棋來說必須在一條直線上有連續五個棋子才能贏。因此，在對角線上就可以減少8路。所以，整個棋盤路的總數為：38+（37-8）+（37-8）=96路。對某一棋局n[14-15]，第i路得分：

h（i）=h（i）t-hm（i）[1]。

我們不用把每個節點都搜索一遍也可獲得和極大極小搜索同樣結果的走步，不搜索分支節點而舍棄該分支的過程叫剪枝。常用的剪枝方法是α-β剪枝算法。

在極大極小搜索的過程中，存在著一定程度的數據冗余。如下圖2所示左半部的一棵極大極小樹的片斷，節點下面為該節點的值，設A 為極大值節點，節點B的值為18，節點D 的值為16，由此可以判斷節點C的值將小于等于16（取極小值）；而節點A的值為節點Max（B，C），是18，也就是說不再需要估節點C的其他子節點如E、F的值就可以得出父節點A 的值了。這樣將節點D 的后繼兄弟節點減去稱為Alpha剪枝（α剪枝）。如圖2：

同樣道理在圖3右半部一棵極大極小樹的片段中，設A為極小值節點，節點B的估值為8，節點D的估值為l8，由此可以判斷節點C的值將大于等于18（取極大值）；而節點A 的值為Min（B，c），是8。也就是說不再需要求節點C的其他子節點如E、F值就可以得出父節點A 的值了。這樣將節點D的后繼兄弟節點剪去稱為Beta剪枝（β剪枝）。如圖3：

將Alpha剪枝和Beta剪枝加入極大極小搜索，就得到α-β搜索算法。

現在假設五子棋問題深度為3的搜索樹給出α-β剪枝算法，用類C語言對其進行描述：

設電腦為Max，人為Min，初始時α為-∞，β為+∞；函數Evalue（ ）返回對當前局面的估值

在p處下黑子；

if（已到達搜索的最后一層） return Evalue（ ）；

如果Max（point p，α，β）函數，則返回對Max結點最有利的走步的局勢靜態估值函數值。反之Min （point p， α， β）函數，則返回對Min結點最有利的局勢靜態估值函數值。兩種互為遞歸調用，可以動態改變搜索深度。

2.2 優化估值函數

通過以上的研究可以看出，在博弈的程序中電腦的行為都是以估值函數為依據的，所以說估值函數在很大的程度上是決定了電腦的棋力高低。我們可以采用遺傳算法來改進靜態估值。

遺傳算法的優點：

（1）由于搜索算法是從問題的解開始的，而不是一組參數。所以被局部震蕩干擾導致求最優解失敗的可能性大大減小。

（2）此算法能將搜索重點集中于性能高的部分，能較快地求出最佳的參數。

遺傳算法的優化估值參數的過程：首先是①隨機產生幾組參數作為初始種群；接著②對種群的參數進行收斂判斷，收斂則③輸出優化結果并且評估過程結束，否則就④執行復制操作產生一組新參數；然后⑤取0、1之間的隨機數，讓隨機數和交叉概率進行比較；若大于⑥則執行交叉操作改變新參數，若小于就不用執行這一步；⑦接著取0、1之間的隨機數，隨機數和變異概率進行比較，若⑧大于就執行變異操作改變新參數，小于就不執行這一步；接著是⑨把較差的一組參數從種群中去除；接著跳回第二步判斷是否已經收斂，如此循環就能將搜索重點集中于性能高的部分，能較快地求出最佳的參數。畫圖4表示如下：

2.3 禁手特征計算

五子棋中還有項規則就是是禁手的判斷，在上邊已經給出了3顆棋子的時候的分值為1000。如果是雙三則需要乘以2，即2000。電腦在分值表中將會判斷雙三點比一個三的點更為重要。這在電腦進行全局判斷的時候也是正確的，可是如果電腦執黑子，這一點是不能落子的，否則將導致失敗。但是電腦不能真的會自己去判斷，只有認為的給他一個判斷的標準，處理的方法是：在累加分值的時候增加一個判斷語句，如果正好形成雙三，那么這一點不加入分值表同時判斷此點落棋將判為負，其他禁手按同樣的方法處理。

3、結論及展望未來

3.1總結

本文介紹了應用人工智能設計五子棋的總體方法。用極大極小值的過程以及啟發式搜索的方法，采用靜態估值函數對各節點的代價進行估計，應用遺傳算法對估計的值進行了優化，克服了人為主觀因素的片面性。對博弈的研究具有一定的借鑒意義。在實際五子棋系統的設計中。應用本方法只向前搜索了三步，就可以取得很好的效果。也可以增加搜索的深度來提高系統的判斷能力，但是是以犧牲電腦的運算速度為前提的，畢竟加深搜索的話就需要更大的運算量。此外，也可以通過增加機器學習，比如電腦對棋局進行記憶，在對手落子之前對棋局和之前記憶的棋局進行比較，先判斷出更優的走法，就可以進一步提高系統的智能。

3.2 未來展望

隨著Intel HP（超線程技術）的實現和將來多處理器PC機的普及.對于數據計算量大的人機對弈問題必然要求應用并行的思想去處理。超快搜索速度和必要的復盤“反思”必然帶給下棋電腦更多智慧。

參考文獻：

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

[2]閻平凡.人工神經網絡與模擬進化計算[M].北京：清華大學出版社，2002

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

[4]Nils J Nilsson，鄭扣根，莊越挺譯.Artificial Intelligence A New Synthesis[M].北京：機械工業出版社，2000

[5]陳爾紹.傳感器實用裝置制作集錦[M].北京：人民郵電出版社，1999

[6]鄧天炎，李愛華，尹正主編.離散數學教程[M].徐州：中國礦業大學出版社，2002

[7]潘金貴，顧鐵成，曾儉等編譯.現代計算機常用數據結構和算法[M].南京：南京大學出版社，1994

[8]王小平.遺傳算法-理論應用與軟件實現[M].西安：西安交通大學出版社，1998

[9]王永慶.人工智能原理與方法[M].西安：西安交通大學出版社，1998

[10]林堯瑞，馬少平.人工智能導論[M].北京：清華出版社，1989

[11]田盛豐，黃厚寬.人工智能與知識工程[M].北京：中國鐵道出版社，1999

[12]陸汝鈐.人工智能[M].北京：科學出版社，1995

[13]王鐫.博弈樹搜索的算法改進[J].福建電腦.2004，（2）

[14]蔣加伏，陳藹樣，唐賢英.基于知識推理的博弈樹搜索算法[J].計算機工程與應用，2004，（1）

[15]Nilsson NJ.人工智能[M].北京：機械工業出版社，2000