六子棋智能博弈系統的研究與實現

摘要:六子棋作為一個新興的游戲，已在棋類計算機智能博弈領域占有重要的位置，其為保證競賽公平性而采取的一步兩子的規則對計算機博弈的效率是很大的考驗。為此，在實現六子棋博弈系統狀態表示、搜索策略和評估函數幾大核心框架的基礎上，提出“路”的概念，簡化評估函數類型，有效提高博弈性能。

關鍵詞:人工智能;博弈樹;六子棋;

中圖分類號:TP181文獻標識碼:A文章編號:1009-3044(2009)25-7198-03

The Research and Implementation of Connect6 Intelligent Chess Game System

HUANG Ji-Ping， ZHANG Dong， MIAO Hua

(School of Computer Science and Engineering， Chongqing University of Technology， Chongqing 4000504， China)

Abstract: As a new game， Connect6 has held an important position in the field of Computer chess game intelligence. It's a big problem to the efficiency of Computer Game， because Connect6 puts two chessman in one step to ensure that the game is fair. So， based on the implementation of main components of Connect6 game: description of state， search engine and evaluation function， this paper makes a new conception: \"road\"， which simplifies the evaluation functions and effectively improve game performance.

Key words: artificial intelligence; game tree; connect6; genetic algorithms

在人工智能領域始終將棋類的機器博弈作為常用的研究平臺之一[1]。以棋類游戲為研究和驗證平臺，各種搜索算法、智能方法在計算機博弈中都可以得到廣泛的應用。1997年，“深藍”小組研究開發出“更深的藍”，以3.5比2.5擊敗了國際級大師卡斯帕羅夫，成為人工智能發展的一個里程碑。至今為止，計算機博弈在五子棋、象棋、國際象棋甚至圍棋上都取得了卓越的成就。

1 六子棋簡介

六子棋(Connect6)是由臺灣交通大學吳毅成教授所發明的一種新游戲，由五子棋改良而來，相比較而言，它具有規則簡單、變化復雜、游戲公平三個很好的特性。在六子棋里，除了持黑的第一手下一子外，黑白雙方輪流各下兩子，最后連成六子者勝。由于各方每次下完一手后，盤面都比對方多一子，因此賽局可自然達成平衡的狀態，使得公平性大為提升。而五子棋、象棋等，先手常常具有一些優勢。同時由于一次兩子，組合變化莫測，其復雜度已被評估為僅次于圍棋和日本象棋，遠高于五子棋，與象棋相當或略高。

六子棋計算機博弈可以分解為四個核心部分:狀態表示、走法生成、搜索引擎、評估函數。其中狀態表示和走法生成是所有棋類游戲的基礎，而搜索引擎很評估函數是使六子棋具有“思考”能力的關鍵。

2 狀態表示

要實現計算機模擬六子棋的博弈過程，就需要對之的博弈狀態進行分解描述。本文將六子棋機器博弈進程分別表示為三種離散數據結構:棋局狀態，棋子狀態和棋形描述。由于六子棋源于五子棋，在棋局和棋子狀態的描述上和五子棋及圍棋類似，所以下文主要針對六子棋的棋形進行闡述。

2.1 棋形描述

棋形就是棋局的一種狀態描述，是描述棋盤上不同棋子的分布狀態。采用狀態矩陣可以比較清楚地描述某個時刻，機器博弈進程中棋局狀態和棋子狀態的變化，如何有意識地控制這個變化發展方向，并使得朝有利于己方贏棋的方向發展，是機器博弈進程中，計算機需要解決的核心問題。

本文采用了其中15種棋形:連六(獲勝)、長連(獲勝)、活五、眠五、死五、活四、眠四、死四、活三、眠三、朦朧三、死三、活二、眠二、死二，并將這些棋形的描述放入決策支持系統的知識庫，形成了計算機博弈決策系統推理的基礎，下面對其中重要的改進解釋如下:

① 六連，C6:在棋盤的縱向、橫向或斜向的任意一條線上，形成的連續相連的6顆同色棋子。

② 活五，C5:在同一直線上的5顆同色棋子，符合“對方必須用兩手棋才能”的條件。

③ 活四，C4:在同一直線上的4顆同色棋子，符合“對方必須用兩手棋才能擋住”的條件。

④ 眠四，S4:在同一直線上的4顆同色棋子，符合“對方用一手棋就能擋住”的條件。

⑤ 死四，D4:在同一直線上的4顆同色棋子，它們已無法形成六連或長連。

⑥ 朦三，S3:在同一直線上的3顆同色棋子，符合“再下一手棋只能形成眠四，但如果再下兩手棋的話就能形成活五”的條件。

2.2 “路”的思想

事實上，六子棋中每一種棋形都有很多的表現形式。同時如果有幾種棋形交叉時判斷起來就更加復雜。如何判斷棋形就成為計算機系統難點，如果模板設置錯誤或棋形統計不完全，將嚴重的影響博弈系統的棋力。因此本文提出“路”的概念。所謂 “路”就是在棋盤上連續6個點能夠連成一條直線，則稱為1“路”。六子棋棋盤是19×19的棋盤，計算可得一共有924“路”。這樣每條“路”上就只有6個點，這樣就使得棋形的判斷和統計非常簡單了。例如，在某“路”里已經存在4顆棋子，此時就無需去判定它到底是活四、眠四，還是眠四棋形，從而極大減少了計算量。

當博弈開始并下棋子時，用兩個哈稀表來分別存儲棋盤上已下棋子和待搜索點的信息，對于有棋子的用哈稀表中的鍵值key，分別表示棋盤上棋子的坐標和棋子對象，這樣特定的key就對應一個value值。對于待搜索點(Evealutepoint)，將最外層的已下棋子的點(UsedPoint)向外擴展5個點，從而所得到未下棋子點的集合，并存放到一個哈希表中。這樣的表示就可以比較方便地找到棋盤上面的棋子狀態，實際上只要遍歷哈稀表，而不是遍歷整個棋盤，從而極大地節約時間。

3 搜索策略

在二人博弈問題中，為了從眾多可供選擇的行動方案中選出一個對自己最為有利的行動方案，需要對當前的情況以及將要發生的情況進行分析，通過搜索算法從中選出最優的著法。在博弈問題中，每個棋局可供選擇的行動方案有很多。因此，將生成十分龐大的博弈樹，如果試圖通過直到終局的與或樹搜索而得到最好的一步棋，這是不可能實現的。例如，30步的六子棋完整的博弈樹，可以計算出大約有10140個節點，假設每個博弈樹枝的長度為30，大約有335個判斷分支點，那么從起點到終點大約有2335條路徑，即使按照每條路徑耗時1/10000秒，也大約需要耗時2335/214≌2321(秒) 2298(年)。顯然，要遍歷所有分枝、接點，目前的任何計算機都無法完成這個搜索任務。因此，必須尋求合適搜索算法，以完成該項搜索任務。下面將介紹一些這樣的搜索算法。

3.1 極大極小值搜索算法

極小極大搜索法是最常使用的搜索方法，其基本思想是:

1) 設博弈的雙方中一方為MAX，另一方為MIN。然后為其中的一方(例如MAX)尋找一個最優行動方案。

2) 為了找到當前的最優行動方案，需要對各個可能的方案所產生的后果進行比較，具體地說，就是要考慮每一方案實施后對方可能采取的所有行動，并計算可能的得分。

3) 為計算得分，需要根據問題的特性信息定義一個估價函數，用來估算當前博弈樹端節點的得分。此時估算出來的得分稱為靜態估值。

4) 當端節點的估值計算出來后，再推算出父節點的得分，推算的方法是:對“或”節點，選其子節點中一個最大的得分作為父節點的得分，這是為了使自己在可供選擇的方案中選一個對自己最有利的方案;對“與”節點，選其子節點中一個最小的得分作為父節點的得分，這是為了立足于最壞的情況。這樣計算出的父節點的得分稱為倒推值。

5) 如果一個行動方案能獲得較大的倒推值，則它就是當前最好的行動方案。

在博弈問題中，面對龐大的博弈樹，試圖利用完整的博弈樹來進行極小極大分析是困難的。可行的辦法是只生成一定深度的博弈樹，然后進行極小極大搜索，找出當前最好的行動方案。在此之后，再在已選定的分支上擴展一定深度，再選最好的行動方案。如此進行下去，直到取得勝敗結果為止，至于每次生成博弈樹的深度，當然是越大越好，但由于受到計算機存儲空間的限制，只好根據實際情況而定。

3.2 Alpha—Beta算法

Alpha-Beta剪枝搜索是一種基于剪枝(Alpha-Beta cut-off)的深度優先搜索(depth-first search)。將走棋方定為MAX方，因為它選擇著法時總是對其子節點的評估值取極大值，即選擇對自己最為有利的著法;將應對方定為MIN方，因為它走棋時需要對其子節點的評估值取極小值，即選擇對走棋方最為不利的、最有鉗制作用的著法。

Alpha剪枝:在對博弈樹采取深度優先的搜索策略時，從左路分枝的葉節點倒推得到某一層MAX節點的值，可表示到此為止得以“落實”的著法最佳值，記為Alpha。顯然此Alpha值可作為MAX方著法指標的下界。在搜索此MAX節點的其它子節點，即探討另一著法時，如果發現一個回合(2步棋)之后評估值變差，即孫節點評估值低于下界Alpha值，則便可以剪掉此枝(以該子節點為根的子樹)，即不再考慮此“軟著”的延伸。此類剪枝稱為Alpha剪枝。下圖給出了搜索和剪枝過程，最后得到如粗箭頭所示的最佳路徑片斷。

Beta剪枝:同理，由左路分枝的葉節點倒推得到某一層MIN節點的值，可表示到此為止對方著法的鉗制值，記為Beta。顯然此Beta值可作為MAX方可能實現著法指標的上界。在搜索該MIN節點的其它子節點，即探討另外著法時，如果發現一個回合之后鉗制局面減弱，即孫節點評估值高于上界Beta值，則便可以剪掉此枝，即不再考慮此“軟著”的延伸。此類剪枝稱為Beta剪枝。下圖給出了搜索和剪枝過程，最后得到如粗箭頭所示的最佳路徑片斷。

Alpha-Beta剪枝算法的效率與子節點擴展的先后順序相關。為了得到最好的節點擴展順序，許多搜索算法在著法(節點擴展的分枝)排序上給予特別的關注。比如在著法生成(節點擴展)時，先生成吃子著法，尤其先生成吃分值高的“大子”著法，因為由此產生著法更有可能是最佳的.圍繞著法排序，已經出現許多優秀的搜索算法與舉措。如:同形表法、吃子走法的SEE排序、殺手走法、未吃子走法的歷史啟發排序、類比法等。當然這些只適用于象棋類型的多種棋子的游戲。

Alpha-Beta剪枝算法偽代碼描述如下:

int AlphaBeta(int depth， int alpha， int beta) {

if (depth == 0) {

return Evaluate(); }

GenerateLegalMoves(); //產生所有的可能走法

while (MovesLeft()) {

MakeNextMove();

val = -AlphaBeta(depth - 1， -beta， -alpha);

UnmakeMove();

if (val >= beta)

{return beta; }

if (val > alpha)

{ alpha = val; }}

return alpha; }

4 確定評估值

六子棋的棋形估值涉及的因素多，是一個非線性規劃問題。例如，活三、活四、眠三、眠四等，通過統計方法、經驗值來比較，盡管符合大多數棋類游戲的估值特點，但是將會產生新問題，由于棋形的變化多種多樣，很多時候因為棋形統計不全而導致估值有錯，進而輸掉了比賽。對棋局局面判斷、估值主要就是通過統計方法和搜索棋形來完成的，是預先給每種棋形設定一個經驗值，經過統計得到如果在某個位置行棋落子后，棋局局面的估值將產生什么變化來決定的。因此，此時的估值與搜索是相互影響和相互促進的，好的估值能夠促進有效的搜索剪枝，這樣能大大減少需要搜索的點，節約搜索時間。而且，搜索時能夠有好的搜索順序，結合估值的準確性，能最大程度的減少搜索點，在有效的時間范圍內，最后確定的要走的點就更加準確。但是，估值與搜索是非常難于協調配合的，實際效果并不如意。

針對六子棋機器博弈的特點，本文采用“路”和“迫著”思想，將19×19的棋盤劃分為924“路”，根據“路”來估值，計算出棋盤的狀態值。這樣就只需要計算924“路”中的棋子顆數即可，根據棋子的顆數給出估值，從而使得估值范圍大大縮小，就能明顯地提高計算速度。新系統的估值不再進行棋形的判定，僅僅計算“路”中已有的同色棋子的顆數，然后找到“路”相對應的值。假設在某點走子后，計算棋盤局面的狀態變化值，通過對比搜索出最優值所對應的行棋走子組合——“著法”。在本文博弈系統的估值中，需要注意兩點:一是如果同一“路”中存在不同色的棋子，則該“路”就失去了利用價值或威脅，需要拋棄;二是在估值前，假設在某點走子時，某條“路”出現了6個同色的棋子，則勝敗已分，系統將自動結束比賽。

5 結束語

本文介紹了實現六子棋智能博弈系統的幾個核心部分:狀態表示、搜索算法和估值函數。Alpha-Beta剪枝算法提升了系統搜索的效率，結合針對六子棋特點設計的估值函數，使機器具有較強的”思考”能力。而本文提出的“路”的思想又使得估值函數類型大大減少，進一步提高搜索效率，對提升六子棋的棋力具有較好的作用。

參考文獻:

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

[2] 王小春.PC游戲編程[M].重慶:重慶大學出版社， 2002:1-27.

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

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

[5] 瞿錫泉，白振興，包建平.棋類博弈算法的改進[J].現代電子技術，2005(01):96-99.

[6] 張海峰，白振興，張登福.五子棋中的博弈智能設計[J]，現代電子技術，2004，27(7):25-27.

[7] 王鐫.博弈樹搜索的算法改進[J].福建電腦，2004(2):27-28.

[8] 林堯瑞，馬少平.人工智能導論[M].北京:清華大學出版社，2002.