方菲　李龍澍

摘要：棋類游戲是博弈的規(guī)則和思想的完美體現(xiàn)，很多算法技術(shù)都可以運(yùn)用在棋類游戲中。五子棋相比其他棋類，規(guī)則更簡單易學(xué)，適合用于博弈算法的研究。一個五子棋博弈平臺的搭建，有利于不同博弈算法之間的比較研究以及改進(jìn)。該文首先介紹了五子棋博弈平臺的設(shè)計。該平臺是包括一個服務(wù)器和兩個客戶端的三層C/S架構(gòu)平臺，主要用于五子棋博弈算法之間的對弈。其次，該文以遺傳算法及搜索樹算法的對弈為例，展示了該平臺的應(yīng)用。

關(guān)鍵詞：五子棋；博弈算法；三層C/S架構(gòu)

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2014）09-2292-05

Abstract： Chess game is the perfect embodiment of the rules and thought of the game playing algorithm. Many algorithms can be used in it. Since its rules are much easier compared to the other chess games， Gobang is more suitable for the study of game playing algorithm. First of all ， my paper shows how this Gobang game platform ， which contains a server and two client based on the three-layer C/S architecture ， was designed . Then， since its mainly used for the comparison of Gobang game algorithms ， Genetic algorithms and search tree algorithm were used as examples to show how this platform works.

Key words： gobang；game playing algorithm；three-layer clent/severachitecture

人工智能作為一門正在迅速發(fā)展的新興的綜合性很強(qiáng)的邊緣科學(xué)，與生物工程、空間技術(shù)一起被并稱為當(dāng)今世界三大尖端技術(shù)。它的中心任務(wù)是研究如何使用計算機(jī)去做那些過去只能靠人的智力做的工作。機(jī)器博弈是人工智能的一個重要研究分支也是研究熱點之一。簡單來說，機(jī)器博弈就是讓計算機(jī)像人一樣從事需要高度智能的博弈活動。它為人工智能提供了一個很好的試驗場所[1]。棋類游戲是博弈的規(guī)則和思想的完美體現(xiàn)，很多算法技術(shù)都可以運(yùn)用在棋類游戲中。五子棋相比其他棋類，如象棋、圍棋，規(guī)則更簡單易學(xué)，適合用于博弈算法的研究。該文出于學(xué)術(shù)目的詳細(xì)介紹了五子棋博弈平臺的設(shè)計與實現(xiàn)，并在測試部分對遺傳算法和博弈樹算法兩個算法在五子棋博弈中的應(yīng)用進(jìn)行了比較。從兩者的比較可以看出，使用本平臺可以直觀地比較兩個五子棋博弈算法各方面的好壞差異，對五子棋博弈算法的學(xué)術(shù)研究具有很好地指導(dǎo)意義。

1 平臺設(shè)計

本平臺主要為兩個五子棋博弈算法提供博弈平臺，是一個包含一個服務(wù)器和兩個客戶

端的三層C/S架構(gòu)平臺。服務(wù)器端監(jiān)聽客戶端，處理客戶端發(fā)送的請求。兩個客戶端上運(yùn)行客戶端決策程序，發(fā)送指令給服務(wù)器，服務(wù)器根據(jù)五子棋規(guī)則進(jìn)行判斷，控制雙方進(jìn)行比賽，要求服務(wù)器端和客戶端都可以觀看比賽過程。

1.1 架構(gòu)設(shè)計

三層C/S結(jié)構(gòu)是將應(yīng)用功能分成表示層、業(yè)務(wù)邏輯層和數(shù)據(jù)訪問層層三部分。其解決方案是：對這三層進(jìn)行明確分割，并在邏輯上使其獨立。區(qū)分層次的目的即為了“高內(nèi)聚，低耦合”的思想。原來的數(shù)據(jù)層作為DBMS已經(jīng)獨立出來，所以關(guān)鍵是要將表示層和業(yè)務(wù)邏輯層分離成各自獨立的程序，并且還要使這兩層間的接口簡潔明了。三層架構(gòu)軟件模型如圖1所示：

其中，表示層是應(yīng)用的用戶接口部分，它擔(dān)負(fù)著用戶與應(yīng)用間的對話功能。它用于檢查用戶從鍵盤等輸入的數(shù)據(jù)，顯示應(yīng)用輸出的數(shù)據(jù)。業(yè)務(wù)邏輯層相當(dāng)于應(yīng)用的本體，它是將具體的業(yè)務(wù)處理邏輯地編入程序中。數(shù)據(jù)訪問層則負(fù)責(zé)管理對數(shù)據(jù)庫數(shù)據(jù)的讀寫。這種架構(gòu)的系統(tǒng)基本工作流程如圖2所示：

由圖3可以看出，三層C/S架構(gòu)具有以下優(yōu)點：

1） 擴(kuò)展性強(qiáng)。不同層負(fù)責(zé)不同的層面，可以很容易的用新的實現(xiàn)來替換原有層次的實現(xiàn)。

2） 開發(fā)人員可以只關(guān)注整個結(jié)構(gòu)中的其中某一層，項目結(jié)構(gòu)更清楚，分工更明確，有利于后期的維護(hù)和升級。

3） 低耦合。大大降低了層與層之間的依賴。

4） 可復(fù)用性強(qiáng)。

5） 安全性高。用戶端只能通過邏輯層來訪問數(shù)據(jù)層，減少了入口點，把很多危險的系統(tǒng)功能都屏蔽了。

可以看出，該架構(gòu)很適合五子棋博弈平臺的開發(fā)，因此，設(shè)計本系統(tǒng)架構(gòu)如圖3所示：

2.2 詳細(xì)設(shè)計

2.2.1 系統(tǒng)層次劃分

根據(jù)博弈平臺的三層C/S架構(gòu)，設(shè)計系統(tǒng)層次如圖4所示：

其中，界面層相當(dāng)于表示層，主要負(fù)責(zé)顯示初始棋盤和棋盤的后續(xù)更新；由于本博弈平臺不存在數(shù)據(jù)庫部分，因此剩下部分均對應(yīng)業(yè)務(wù)邏輯層。其中，控制層負(fù)責(zé)接受各種信息并交由策略層（或規(guī)則層）進(jìn)行必要的判斷處理，然后把處理后的各種信息的更新通知通信層；通信層負(fù)責(zé)通過網(wǎng)絡(luò)實現(xiàn)各種信息的交互；Client端的策略層主要由五子棋博弈算法組成，用于通過當(dāng)前棋盤狀態(tài)計算得出下棋點；Server端的規(guī)則層存放五子棋的各種規(guī)則。

為了達(dá)到更好的靈活性，策略層和規(guī)則層都留有接口，可以實現(xiàn)策略和規(guī)則的替換。策略的替換便于各種不同博弈算法的比較；規(guī)則的替換則可以把五子棋博弈系統(tǒng)變化成其它游戲的博弈平臺。

2.2.2 系統(tǒng)功能設(shè)計

2.2.2.1 服務(wù)器端功能設(shè)計

A.Server通信層

該層要完成以下功能：

a.建立與Client的通信

b.監(jiān)聽ClientA，隨時接收在控制時間內(nèi)ClientA發(fā)來的消息；等待ClientA超時時，向Server控制層發(fā)送異常消息。

c.將Server的數(shù)據(jù)發(fā)送給ClientA（或者ClientB）。

B.Server規(guī)則層

該層就是存放一些五子棋走棋的規(guī)則，在上面五子棋規(guī)則中已經(jīng)說明。

C.Server控制層

a.接收Server通信層發(fā)來的消息。

b.根據(jù)Server的規(guī)則層的規(guī)則處理Server通信層發(fā)來的消息。

c.向Server通信層和界面層發(fā)送處理后的消息。

d.控制ClientA和ClientB的同步。

D.Server界面層

a.接收Server控制層傳來的數(shù)據(jù)。

b.顯示棋子坐標(biāo)和勝負(fù)。

c.顯示Client負(fù)時的形成原因。

2.2.2.2 客戶端功能設(shè)計

A.Client通信層（以CLientA為例）

a.建立與Server的連接；

b.將每次從Server接收的消息傳給Client控制層；

c.發(fā)送策略決策的數(shù)據(jù)包到Server通信層。

B.Client 控制層

a.接收Client通信層的消息；

b.有一個棋盤的狀態(tài)，對消息進(jìn)行解析后更新棋盤狀態(tài)；

c.將這個棋盤狀態(tài)的更改信息通知Client的界面層和決策層。

C.Client策略層

a.接收Client通信層發(fā)來的當(dāng)前棋盤矩陣狀態(tài)。

b.根據(jù)自己的策略和當(dāng)前棋盤矩陣狀態(tài)，必須在限定時間（與Server監(jiān)聽時間相同）內(nèi)形成下一步棋子行走坐標(biāo)。

c.判斷自己是否是黑方，若是，還要根據(jù)禁手規(guī)則形成下一步棋子行走坐標(biāo)。

D.Client界面層

a.接收Client通信層傳來的數(shù)據(jù)。

b.顯示Client行走的坐標(biāo)和勝負(fù)信息。

2.2.3 系統(tǒng)流程圖

根據(jù)博弈平臺的功能，設(shè)計系統(tǒng)流程圖如圖5所示。

2.2.4 平臺實現(xiàn)

根據(jù)以上設(shè)計，用C#語言實現(xiàn)該平臺。五子棋博弈平臺的交互過程總結(jié)如下：

A.服務(wù)器開啟服務(wù)，等待客戶端連接。

B.一方客戶端連接服務(wù)器，若連接成功，則更改此方客戶端的連接狀態(tài)為已連接，同時服務(wù)器控制層新建一個線程A，將當(dāng)前客戶端數(shù)目加1。

C.另一方客戶端連接服務(wù)器，若連接成功，則更改此方客戶端的連接狀態(tài)為已連接，同時服務(wù)器控制層新建一個線程B，將當(dāng)前客戶端數(shù)目加1。

D.此時服務(wù)器控制層判斷當(dāng)前已連接的客戶端數(shù)目是否為2，若是，則服務(wù)器給A，B發(fā)送一個可以開始游戲的信息，此信息中包含棋子的顏色，A為黑色，B為白色。服務(wù)器要等待雙方客戶端都點擊開始游戲后才發(fā)送一個信息給所有客戶端，客戶端控制層解析此信息后才能運(yùn)行策略，發(fā)送坐標(biāo)信息。

E.客戶端控制層發(fā)送策略決定的坐標(biāo)前，要檢查_myTurn的值，若為true，則可以發(fā)送，發(fā)送坐標(biāo)后，要把_myTurn改為false。此后，只有當(dāng)服務(wù)器發(fā)送給該客戶端的信息是坐標(biāo)時，才可以把_myTurn的值更改為true。

F.服務(wù)器接收到某客戶端發(fā)來的坐標(biāo)信息后，將其交給規(guī)則庫中的規(guī)則去檢測，如果全部通過，說明該客戶端發(fā)來的走棋坐標(biāo)是合法的，控制層就要更改State對象的Panel數(shù)組對應(yīng)的坐標(biāo)值為該客戶端棋子顏色對應(yīng)的數(shù)值。并發(fā)送給該客戶端一個OK信息，表示該走棋合法，同時要把此坐標(biāo)發(fā)送給另一個客戶端，讓其作出相應(yīng)的決策。這樣依次循環(huán)，進(jìn)行博弈。

G.若根據(jù)規(guī)則判斷該步走法的坐標(biāo)不合法，則控制層可以發(fā)送該方輸信息，另一方贏信息。

H.若該步走后已形成5子連珠，則服務(wù)器控制層要發(fā)送該方贏信息，另一方輸信息。

3 平臺應(yīng)用

本平臺的主要作用提現(xiàn)在對五子棋博弈算法的研究中。下面在本平臺上用遺傳算法[2]、[3]分別與傳統(tǒng)博弈樹算法（下稱算法1）和網(wǎng)絡(luò)上流行的另一五子棋博弈算法（下稱算法2），進(jìn)行博弈，應(yīng)用結(jié)果如下。

3.1 實驗結(jié)果對比

1）各算法落子時間比較

各算法走一步需要的平均時間如表1所示，其中i為遺傳算法收斂條件中的參數(shù)，其意義為：如果連續(xù)i代適應(yīng)度函數(shù)值都不再增加或連續(xù)i代求出的落子點都不再變化，則算法收斂。

2）每局平均落子數(shù)比較

遺傳算法與算法1、算法2對弈時每局平均落子數(shù)如表2所示：

3）勝率比較

遺傳算法與算法1、算法2對弈時勝率比較如表3所示：

4）實驗結(jié)果截圖

4 結(jié)束語

通過以上分析可以看出，本平臺在五子棋博弈算法的研究比較中具有很大的意義。首先，本平臺應(yīng)用簡單，不同的五子棋博弈算法可以輕松導(dǎo)入應(yīng)用在該平臺上。使用者不用過多關(guān)注平臺的搭建，只用將注意力集中在算法上即可。其次，通過這些算法在平臺上的多次運(yùn)行，可以簡單分析出博弈算法實際運(yùn)行時的各種參數(shù)，以此評判算法的優(yōu)劣。最重要的是，算法設(shè)計者可以依據(jù)所得算法參數(shù)有針對性的對算法進(jìn)行改進(jìn)。

參考文獻(xiàn)：

[1] 人工智能——復(fù)雜問題求解的結(jié)構(gòu)和策略[M].史忠植，譯.北京：機(jī)械工業(yè)出版社，2004：101-131.

[2] 王小平，曹立明.遺傳算法：理論、應(yīng)用于軟件實現(xiàn)[M].西安：西安交通大學(xué)出版社，2002.

[3] 馬占欣，李亞，陸玉晶.用遺傳算法解決博弈問題[J].河南科學(xué)，2007，25（2）：273-277.