六子棋智能博弈系統(tǒng)的研究與實(shí)現(xiàn)

摘要:六子棋作為一個(gè)新興的游戲，已在棋類計(jì)算機(jī)智能博弈領(lǐng)域占有重要的位置，其為保證競(jìng)賽公平性而采取的一步兩子的規(guī)則對(duì)計(jì)算機(jī)博弈的效率是很大的考驗(yàn)。為此，在實(shí)現(xiàn)六子棋博弈系統(tǒng)狀態(tài)表示、搜索策略和評(píng)估函數(shù)幾大核心框架的基礎(chǔ)上，提出“路”的概念，簡(jiǎn)化評(píng)估函數(shù)類型，有效提高博弈性能。

關(guān)鍵詞:人工智能;博弈樹;六子棋;

中圖分類號(hào):TP181文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):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

在人工智能領(lǐng)域始終將棋類的機(jī)器博弈作為常用的研究平臺(tái)之一[1]。以棋類游戲?yàn)檠芯亢万?yàn)證平臺(tái)，各種搜索算法、智能方法在計(jì)算機(jī)博弈中都可以得到廣泛的應(yīng)用。1997年，“深藍(lán)”小組研究開(kāi)發(fā)出“更深的藍(lán)”，以3.5比2.5擊敗了國(guó)際級(jí)大師卡斯帕羅夫，成為人工智能發(fā)展的一個(gè)里程碑。至今為止，計(jì)算機(jī)博弈在五子棋、象棋、國(guó)際象棋甚至圍棋上都取得了卓越的成就。

1 六子棋簡(jiǎn)介

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

六子棋計(jì)算機(jī)博弈可以分解為四個(gè)核心部分:狀態(tài)表示、走法生成、搜索引擎、評(píng)估函數(shù)。其中狀態(tài)表示和走法生成是所有棋類游戲的基礎(chǔ)，而搜索引擎很評(píng)估函數(shù)是使六子棋具有“思考”能力的關(guān)鍵。

2 狀態(tài)表示

要實(shí)現(xiàn)計(jì)算機(jī)模擬六子棋的博弈過(guò)程，就需要對(duì)之的博弈狀態(tài)進(jìn)行分解描述。本文將六子棋機(jī)器博弈進(jìn)程分別表示為三種離散數(shù)據(jù)結(jié)構(gòu):棋局狀態(tài)，棋子狀態(tài)和棋形描述。由于六子棋源于五子棋，在棋局和棋子狀態(tài)的描述上和五子棋及圍棋類似，所以下文主要針對(duì)六子棋的棋形進(jìn)行闡述。

2.1 棋形描述

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

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

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

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

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

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

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

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

2.2 “路”的思想

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

當(dāng)博弈開(kāi)始并下棋子時(shí)，用兩個(gè)哈稀表來(lái)分別存儲(chǔ)棋盤上已下棋子和待搜索點(diǎn)的信息，對(duì)于有棋子的用哈稀表中的鍵值key，分別表示棋盤上棋子的坐標(biāo)和棋子對(duì)象，這樣特定的key就對(duì)應(yīng)一個(gè)value值。對(duì)于待搜索點(diǎn)(Evealutepoint)，將最外層的已下棋子的點(diǎn)(UsedPoint)向外擴(kuò)展5個(gè)點(diǎn)，從而所得到未下棋子點(diǎn)的集合，并存放到一個(gè)哈希表中。這樣的表示就可以比較方便地找到棋盤上面的棋子狀態(tài)，實(shí)際上只要遍歷哈稀表，而不是遍歷整個(gè)棋盤，從而極大地節(jié)約時(shí)間。

3 搜索策略

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

3.1 極大極小值搜索算法

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

1) 設(shè)博弈的雙方中一方為MAX，另一方為MIN。然后為其中的一方(例如MAX)尋找一個(gè)最優(yōu)行動(dòng)方案。

2) 為了找到當(dāng)前的最優(yōu)行動(dòng)方案，需要對(duì)各個(gè)可能的方案所產(chǎn)生的后果進(jìn)行比較，具體地說(shuō)，就是要考慮每一方案實(shí)施后對(duì)方可能采取的所有行動(dòng)，并計(jì)算可能的得分。

3) 為計(jì)算得分，需要根據(jù)問(wèn)題的特性信息定義一個(gè)估價(jià)函數(shù)，用來(lái)估算當(dāng)前博弈樹端節(jié)點(diǎn)的得分。此時(shí)估算出來(lái)的得分稱為靜態(tài)估值。

4) 當(dāng)端節(jié)點(diǎn)的估值計(jì)算出來(lái)后，再推算出父節(jié)點(diǎn)的得分，推算的方法是:對(duì)“或”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個(gè)對(duì)自己最有利的方案;對(duì)“與”節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為倒推值。

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

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

3.2 Alpha—Beta算法

Alpha-Beta剪枝搜索是一種基于剪枝(Alpha-Beta cut-off)的深度優(yōu)先搜索(depth-first search)。將走棋方定為MAX方，因?yàn)樗x擇著法時(shí)總是對(duì)其子節(jié)點(diǎn)的評(píng)估值取極大值，即選擇對(duì)自己最為有利的著法;將應(yīng)對(duì)方定為MIN方，因?yàn)樗咂鍟r(shí)需要對(duì)其子節(jié)點(diǎn)的評(píng)估值取極小值，即選擇對(duì)走棋方最為不利的、最有鉗制作用的著法。

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

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

Alpha-Beta剪枝算法的效率與子節(jié)點(diǎn)擴(kuò)展的先后順序相關(guān)。為了得到最好的節(jié)點(diǎn)擴(kuò)展順序，許多搜索算法在著法(節(jié)點(diǎn)擴(kuò)展的分枝)排序上給予特別的關(guān)注。比如在著法生成(節(jié)點(diǎn)擴(kuò)展)時(shí)，先生成吃子著法，尤其先生成吃分值高的“大子”著法，因?yàn)橛纱水a(chǎn)生著法更有可能是最佳的.圍繞著法排序，已經(jīng)出現(xiàn)許多優(yōu)秀的搜索算法與舉措。如:同形表法、吃子走法的SEE排序、殺手走法、未吃子走法的歷史啟發(fā)排序、類比法等。當(dāng)然這些只適用于象棋類型的多種棋子的游戲。

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

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

if (depth == 0) {

return Evaluate(); }

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

while (MovesLeft()) {

MakeNextMove();

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

UnmakeMove();

if (val >= beta)

{return beta; }

if (val > alpha)

{ alpha = val; }}

return alpha; }

4 確定評(píng)估值

六子棋的棋形估值涉及的因素多，是一個(gè)非線性規(guī)劃問(wèn)題。例如，活三、活四、眠三、眠四等，通過(guò)統(tǒng)計(jì)方法、經(jīng)驗(yàn)值來(lái)比較，盡管符合大多數(shù)棋類游戲的估值特點(diǎn)，但是將會(huì)產(chǎn)生新問(wèn)題，由于棋形的變化多種多樣，很多時(shí)候因?yàn)槠逍谓y(tǒng)計(jì)不全而導(dǎo)致估值有錯(cuò)，進(jìn)而輸?shù)袅吮荣悺?duì)棋局局面判斷、估值主要就是通過(guò)統(tǒng)計(jì)方法和搜索棋形來(lái)完成的，是預(yù)先給每種棋形設(shè)定一個(gè)經(jīng)驗(yàn)值，經(jīng)過(guò)統(tǒng)計(jì)得到如果在某個(gè)位置行棋落子后，棋局局面的估值將產(chǎn)生什么變化來(lái)決定的。因此，此時(shí)的估值與搜索是相互影響和相互促進(jìn)的，好的估值能夠促進(jìn)有效的搜索剪枝，這樣能大大減少需要搜索的點(diǎn)，節(jié)約搜索時(shí)間。而且，搜索時(shí)能夠有好的搜索順序，結(jié)合估值的準(zhǔn)確性，能最大程度的減少搜索點(diǎn)，在有效的時(shí)間范圍內(nèi)，最后確定的要走的點(diǎn)就更加準(zhǔn)確。但是，估值與搜索是非常難于協(xié)調(diào)配合的，實(shí)際效果并不如意。

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

5 結(jié)束語(yǔ)

本文介紹了實(shí)現(xiàn)六子棋智能博弈系統(tǒng)的幾個(gè)核心部分:狀態(tài)表示、搜索算法和估值函數(shù)。Alpha-Beta剪枝算法提升了系統(tǒng)搜索的效率，結(jié)合針對(duì)六子棋特點(diǎn)設(shè)計(jì)的估值函數(shù)，使機(jī)器具有較強(qiáng)的”思考”能力。而本文提出的“路”的思想又使得估值函數(shù)類型大大減少，進(jìn)一步提高搜索效率，對(duì)提升六子棋的棋力具有較好的作用。

參考文獻(xiàn):

[1] 徐心和，王驕.中國(guó)象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析[J].小型微型計(jì)算機(jī)系統(tǒng)，2006，27(6):961-969.

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

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

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

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

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

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

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