張佳佳

摘要：該文設(shè)計和實(shí)現(xiàn)了一個五子棋對戰(zhàn)平臺。五子棋源于中國，發(fā)展于日本，在其它地區(qū)，如歐洲和前蘇聯(lián)，也廣受歡迎。五子棋容易上手，老少皆宜，它能增強(qiáng)思維能力，提高智力，而且隨時隨地都可以進(jìn)行游戲。該系統(tǒng)的設(shè)計遵循世界五子棋聯(lián)賽的通用協(xié)議，可以方便地導(dǎo)入算法引擎，不僅可以實(shí)現(xiàn)雙人對弈，也可以實(shí)現(xiàn)人機(jī)對弈、計算機(jī)對弈、網(wǎng)絡(luò)對弈。

關(guān)鍵詞:五子棋；人機(jī)對弈；算法引擎

中圖分類號：TP391文獻(xiàn)標(biāo)識碼：A文章編號：1009-3044(2012)22-5409-03

Design and Implementation of a Gobang Playing Platform

ZHANG Jia-jia

(Beijing Language and Culture University, Beijing 100083,China)

Abstract: This Paper designed and implemented a gobang computer game platform. gobang originated in China and developed in Japan, and is also popular in the former soviet and several European countries. It not only can enhance ones thinking capability, but its adaptability allowed it played virtually everywhere by virtually everyone. The systems design complies with the general protocol of Worlds Gobang Cup, making it easy to import 3rd-party engines. Through this platform，human-human，human-computer，computer-computer play are supported，face to face or through network.

Key words: gobang; man-machine playing; algorithm engine

五子棋是一種兩人對弈的純策略型棋類游戲，是起源于中國古代的傳統(tǒng)黑白棋種之一。發(fā)展于日本，流行于歐美。容易上手，老少皆宜，而且趣味橫生，引人入勝；不僅能增強(qiáng)思維能力，提高智力，而且富含哲理，有助于修身養(yǎng)性。該文在Windows7操作系統(tǒng)中使用VC2005設(shè)計和實(shí)現(xiàn)了一個五子棋對戰(zhàn)平臺。系統(tǒng)的設(shè)計遵循世界五子棋聯(lián)賽的通用協(xié)議，可以方便地導(dǎo)入算法引擎，不僅可以實(shí)現(xiàn)雙人對弈，也可以實(shí)現(xiàn)人機(jī)對弈、計算機(jī)對弈、網(wǎng)絡(luò)對弈。

1系統(tǒng)設(shè)計

1.1總體流程

本系統(tǒng)有著良好的用戶體能，根據(jù)人們下棋的習(xí)慣，設(shè)計出五子棋程序的總體流程。程序開始后，首先選擇模式(兩人對戰(zhàn)、人機(jī)對戰(zhàn)、機(jī)器博弈、網(wǎng)絡(luò)對戰(zhàn))，然后根據(jù)模式設(shè)置其它選項(xiàng)。如人機(jī)對戰(zhàn)需設(shè)置算法引擎以及約定哪方先下；機(jī)器博弈需設(shè)定對弈雙方所使用的算法引擎；網(wǎng)絡(luò)對弈如使用算法引擎，需事先設(shè)定，并由一方通過socket主動連接另一方，收到對方“同意”的答復(fù)后，方可進(jìn)行對弈。

1.2關(guān)鍵算法

1.2.1五子棋規(guī)則介紹

五子棋是雙方之間進(jìn)行的競技活動，專用棋盤為15*15，五連子的方向?yàn)闄M、豎、斜；任一方在棋盤上形成橫向、豎向、斜向的連續(xù)的相同顏色的五個（含五個以上）棋子的一方為勝；在棋盤上以對局雙方均不可能形成五連為和棋。黑白雙方一次落子，由黑先下，由于先下一方在局面上占優(yōu)，五子棋規(guī)則分為禁手和無禁手兩種。

禁手規(guī)則：禁手是針對先行的黑棋而言，以限制黑棋的先行優(yōu)勢為目的。對局中如果黑棋違反禁手規(guī)則將被判負(fù)。以中國五子棋競賽規(guī)則為例，有三三禁手（黑棋一子落下時同時形成兩個或兩個以上的活三，此子必須為兩個活三共同的構(gòu)成子）、四四禁手（黑棋一子落下同時形成兩個以上的沖四或活四）、長連禁手（黑棋一子落下形成一個或一個以上的長連）。

無禁手指不對黑棋的先行優(yōu)勢做任何限制。

1.2.2電腦下棋流程

電腦下棋和人腦下棋在原理上是一致的。一方面，他在輪詢等待棋局信息，如對方下子、悔棋、對方認(rèn)輸、結(jié)束比賽等，類似于等待裁判指令；同時，它在不斷地思考，計算下一步的最佳策略。因此，對這兩個同時進(jìn)行的任務(wù)需要有兩個線程，并需要內(nèi)核對象來協(xié)調(diào)線程同步及互斥。如圖1所示。

游戲開始時，事件1初始無信號，事件2初始有信號，思考進(jìn)程無限等待事件1的狀態(tài)。當(dāng)對戰(zhàn)平臺發(fā)出開始游戲、重新游戲或者對方已下子的指令時，置思考狀態(tài)為0，把事件1置為有信號，把事件2置為無信號。思考線程輪詢到事件1為有信號狀態(tài)，開始思考，思考結(jié)束后再把事件2置為有信號；當(dāng)對戰(zhàn)平臺發(fā)出結(jié)束游戲，重新開始等指令時，置思考狀態(tài)為1，無限等待事件2，也即等待思考線程完成思考。

線程同步核心函數(shù)的原型：

DWORD WINAPI

WaitForSingleObject(

HANDLE hHandle,

DWORD dwMilliseconds

);

CreateEvent(

LPSECURITY_ATTRIBUTES lpEventAttributes,

BOOL bManualReset,

BOOL bInitialState,

LPCSTR lpName

);

bManualReset：

圖1電腦下棋流程

指定將事件對象創(chuàng)建成手動復(fù)原還是自動復(fù)原。如果是TRUE，那么必須用ResetEvent函數(shù)來手工將事件的狀態(tài)復(fù)原到無信號狀態(tài)。如果設(shè)置為FALSE，當(dāng)事件被一個等待線程釋放以后，系統(tǒng)將會自動將事件狀態(tài)復(fù)原為無信號狀態(tài)。

bInitialState：

指定事件對象的初始狀態(tài)。如果為TRUE，初始狀態(tài)為有信號狀態(tài)；否則為無信號狀態(tài)。

1.2.3博弈算法

計算機(jī)博弈模仿人類下棋，傳統(tǒng)的算法是采用博弈樹。兩人對弈，A有很多落子選擇，B也有很多對應(yīng)下法，如果把所有的走法列出來，就構(gòu)成了一顆樹，即為搜索樹，也稱博弈樹。樹的根節(jié)點(diǎn)為先手的第一步走法，下面的走法構(gòu)成了樹的子節(jié)點(diǎn)，直至棋局結(jié)束。五子棋的標(biāo)準(zhǔn)棋盤是15×15，但搜索空間也是一個巨大的數(shù)字。博弈算法的任務(wù)是從這些以幾何級數(shù)上升的子節(jié)點(diǎn)中尋找一個最有的節(jié)點(diǎn)，從而贏得游戲。整個算法分為搜索和估值，估值也即對所有可能落子位置進(jìn)行一個評價，選擇評價最高的位置作為最終落子位置。常見的算有Alpha-Beta剪枝算法、著法排序、空著裁剪、哈希表置換等算法。由于本系統(tǒng)的重點(diǎn)在于設(shè)計對戰(zhàn)平臺，博弈算法設(shè)計較為簡單但足以代表人工博弈的思想。

本系統(tǒng)的估值函數(shù)分為單點(diǎn)估值函數(shù)和全局估值函數(shù)。單點(diǎn)估值函數(shù)的基本思想是對最當(dāng)前的靜態(tài)局面進(jìn)行評估，遍歷棋盤，對棋盤上的每一個非空位置進(jìn)行四個方向的分析（水平、垂直、左對角以及右對角），統(tǒng)計每種棋型的數(shù)量（五連、活四、沖四、活三、眠三、活二、眠二），對不同的棋型進(jìn)行不同的權(quán)重，最后還有個位置分?jǐn)?shù)的加權(quán)（既要考慮空點(diǎn)對于己方的價值，也要考慮到對于對方的價值），這樣就獲得了棋盤上空點(diǎn)的估值。單點(diǎn)估值函數(shù)只能估算單個空白位置的價值，但全局估值函數(shù)可以估算所有的空白位置的總價值，進(jìn)而評估整個棋局。對于當(dāng)前棋局，將所有空白位置對下棋方的有利和不利程度總和相關(guān)即可得出全局估價值。

1.2.4悔棋流程

悔棋是棋類游戲里必不可少的功能。在對弈中，如果對方悔棋，對戰(zhàn)平臺會發(fā)出“undo”命令，此時應(yīng)取消定時器，如果引擎正在讀取指令，則通知其停止，并暫停思考。接下來進(jìn)行“undo”操作。如果已下總步數(shù)小于2，則直接退出，因?yàn)榭偣仓幌铝艘徊狡?，無需悔棋。否則，先加亮顯示最后一步棋，移除并重畫屏幕。然后，更新相關(guān)數(shù)據(jù)結(jié)構(gòu)，如將保存雙方下子的鏈表尾部結(jié)點(diǎn)摘除，更新雙方的超時時間等。

1.3關(guān)鍵數(shù)據(jù)結(jié)構(gòu)

棋類游戲最核心的數(shù)據(jù)結(jié)構(gòu)是棋盤，棋盤表示的高效與否決定了棋類游戲的性能。棋盤數(shù)據(jù)結(jié)構(gòu)的設(shè)計應(yīng)該根據(jù)棋的種類以及系統(tǒng)的設(shè)計目標(biāo)而定。下面考察棋盤的幾種常見數(shù)據(jù)結(jié)構(gòu)表示。

1.3.1二維數(shù)組

無論是五子棋、象棋或是圍棋，棋盤都是規(guī)則的長方形，任何一個位置都可以用橫縱坐標(biāo)來唯一確定。因此，用二維數(shù)組表示棋盤結(jié)構(gòu)，非常直觀。而且由于數(shù)組是直接存取的，這種表示方式存取比較高效。數(shù)組表示非常適合用于五子棋、圍棋等這類不區(qū)分棋子種類的棋類游戲。其特點(diǎn)是局面表現(xiàn)能力強(qiáng)，便于評價局面的好壞。但是對于象棋、國際象棋等有棋子類別區(qū)分的游戲，特定棋子的信息十分重要，如帥和后。每次都要掃描整個棋盤才能獲得特定棋子，比較耗時。

1.3.2鏈表

數(shù)組表示有一個很大的缺點(diǎn)是單個數(shù)組元素保存的信息太少，而且難以表現(xiàn)出二維棋盤每個棋盤位置與前后左右之間的關(guān)聯(lián)。這樣在系統(tǒng)進(jìn)行一些比較復(fù)雜的操作，如悔棋，十分低效。因?yàn)榛谄逍枰郎弦徊降南伦游恢?。鏈表可以很好地解決這些問題。鏈表可以依據(jù)用戶下子的順序來鏈接，這樣悔棋操作只需要摘掉鏈表尾部的結(jié)點(diǎn)就可以了。鏈表結(jié)點(diǎn)除了包含此位置的橫縱坐標(biāo)值，還可以包含其它信息，如該位置的棋子是我方還是對方的。

1.3.3位棋盤

位棋盤不同使用一個64位整形數(shù)來表示棋盤，適用于8*8的棋類游戲，如國際象棋和五子棋、圍棋等。一個使用圍棋盤的程序通常有一組位棋盤，這些位棋盤記錄棋盤的不同信息。位棋盤的變化由位運(yùn)算獲得。由于位操作的特性，位棋盤的運(yùn)算速度很快。和數(shù)組表示一樣，一個位棋盤無法表示附加信息，每個位只有兩個狀態(tài)，0或1。使用位棋盤，要么有多個位棋盤，要么結(jié)合其他數(shù)據(jù)結(jié)構(gòu)一起使用。

結(jié)合以上分析以及五子棋的特點(diǎn)，該文使用折中方案，除了評價局面的函數(shù)使用位棋盤以外，其它地方均使用鏈表表示棋盤。在鏈表更新的時候，相應(yīng)地更新位棋盤。

struct Tsquare

{

Tsymbol z;//0=nothing, 1=player1, 2=player2, 3=outside

Psquare nxt,pre;//linked list for undo, redo

int x,y;//coordinates ＜1..width, 1..height＞

int time;//total thinking time

Psquare winLineStart;//0 or beginning of a winning line

int winLineDir; //direction offset of a winning line

};

int bitboard[16];//standard board--15*15

2結(jié)束語

對于棋類玩家來說，殘局和棋譜的保存有重要的意義。而電腦對戰(zhàn)平臺記錄殘局和棋譜非常方便，只需將對戰(zhàn)狀態(tài)保存下來，需要讀殘局和棋譜的時候再導(dǎo)入即可。本系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)可以很方便地支持殘局和棋譜保存，這是改進(jìn)的第一個方向。另外，支持網(wǎng)絡(luò)對戰(zhàn)是改進(jìn)的另外一個方向。

人機(jī)對弈系統(tǒng)，核心部分是棋盤表示、走法規(guī)則（五子棋中走法規(guī)則簡單，空子即可走）、搜索算法、估值函數(shù)。該文設(shè)計和實(shí)現(xiàn)了一個基本的五子棋對戰(zhàn)平臺，介紹了主要算法和數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)了系統(tǒng)的基本框架，對棋類博弈系統(tǒng)的設(shè)計提供一個參考。另外，五子棋國際比賽規(guī)則較復(fù)雜，通過禁手來限制黑棋的先行優(yōu)勢，為了便于說明，本系統(tǒng)沒有加以考慮。

參考文獻(xiàn)：

[1]王曉春. PC游戲編程:人機(jī)博弈[M].重慶:重慶大學(xué)出版社,2002.

[2]姜勇.五子棋人機(jī)對戰(zhàn)系統(tǒng)設(shè)計[D].北京:電子科技大學(xué),2010.

[3]陸汝鈴.人工智能[M].北京:科學(xué)出版社,1995.

[4]朱全民,陳松喬.五子棋算法的研究與思考[J].計算技術(shù)與自動化,2006,25(2):72-74.

[5]石柱,何新貴.優(yōu)序法在軟件評價中的應(yīng)用[J].計算機(jī)工程與設(shè)計,2002,23(2):45-46.

[6] Allis L V.Searching for solutions in games and artificial intelligence[D].University of Limburg,Maastricht,The Netherlands,1994.