張佳佳

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

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

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

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

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

1.1總體流程

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

1.2關(guān)鍵算法

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

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

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

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

1.2.2電腦下棋流程

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

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

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

DWORD WINAPI

WaitForSingleObject(

HANDLE hHandle,

DWORD dwMilliseconds

);

CreateEvent(

LPSECURITY_ATTRIBUTES lpEventAttributes,

BOOL bManualReset,

BOOL bInitialState,

LPCSTR lpName

);

bManualReset：

圖1電腦下棋流程

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

bInitialState：

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

1.2.3博弈算法

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

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

1.2.4悔棋流程

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

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

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

1.3.1二維數(shù)組

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

1.3.2鏈表

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

1.3.3位棋盤

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

結(jié)合以上分析以及五子棋的特點(diǎn)，該文使用折中方案，除了評(píng)價(jià)局面的函數(shù)使用位棋盤以外，其它地方均使用鏈表表示棋盤。在鏈表更新的時(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é)束語

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

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

參考文獻(xiàn)：

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

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

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

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

[5]石柱,何新貴.優(yōu)序法在軟件評(píng)價(jià)中的應(yīng)用[J].計(jì)算機(jī)工程與設(shè)計(jì),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.