基于Ｃ＋＋的圍棋定式管理系統(tǒng)

【摘要】 圍棋有五種基本定式，將圍棋定式與計(jì)算機(jī)技術(shù)結(jié)合以后，查詢定式、學(xué)習(xí)定式將不再是麻煩事。文章介紹了基于C++技術(shù)的圍棋定式管理系統(tǒng)制作原理并詳細(xì)說明了制作該系統(tǒng)所用到的基本算法。

【關(guān)鍵詞】 圍棋定式；二叉樹；前序遍歷

【中圖分類號】 G891.3

【文獻(xiàn)標(biāo)識碼】 B

【文章編號】 1005-1074(2008)08-0058-02

圍棋定式就是在圍棋活動(dòng)中長久以來逐漸形成的各種進(jìn)攻或防守的模式。圍棋的基本定式有五種：小目定式、目外定式、高目定式、星定式、三三定式。采用面向?qū)ο蠓椒ň帉憞宥ㄊ焦芾硐到y(tǒng)是很有實(shí)用性的，初學(xué)者學(xué)習(xí)圍棋時(shí)輔以該系統(tǒng)學(xué)習(xí)一系列的定式、布局和攻防，不斷地進(jìn)行對戰(zhàn)，在實(shí)戰(zhàn)中增加對定式、布局的理解，強(qiáng)化攻防轉(zhuǎn)換的能力，從而使自己的圍棋水平更上一層樓。

1 圍棋棋子的顯示

每一個(gè)圍棋定式都是由一個(gè)個(gè)的下棋步驟組成的，每一個(gè)下棋步驟在棋盤中顯示。那么我們就應(yīng)該先研究如何將棋盤以及棋子在計(jì)算機(jī)中顯示出來。圍棋棋盤的形狀為正方形或略呈長方形的平面圖，現(xiàn)在的棋盤為平面上畫橫豎各19條平行線，構(gòu)成361個(gè)交叉點(diǎn)。棋盤上可分為9個(gè)部分，分別稱為：左上角、左下角、右上角、右下角、上邊、下邊、左邊、右邊和中腹。棋盤上共有九個(gè)黑點(diǎn)稱作“星”，棋心的黑點(diǎn)稱作“天元”。_［1]

繪制可以利用C++ Builder強(qiáng)大的圖形編程功能進(jìn)行繪制。繪制圍棋棋盤時(shí)要用到的組件有TImage，其中用到TCanvas對象。繪制棋盤時(shí)只要通過循環(huán)就可以畫出橫豎各十九條平行線的棋盤。

還應(yīng)該考慮的一個(gè)問題是如何在用戶點(diǎn)擊棋盤時(shí)在點(diǎn)擊處顯示出一個(gè)棋子。棋子分為白色與黑色兩種，利用TCanvas的畫圖功能同樣可以畫出棋子。棋盤的范圍有限，繪制棋子時(shí)應(yīng)該先判斷點(diǎn)擊的位置是否在棋盤的范圍內(nèi)，若在棋盤范圍內(nèi)則調(diào)用畫圖函數(shù)畫出棋子；若超出棋盤范圍，則不顯示。_［4］

2 主要算法分析

2.1 建立二叉樹實(shí)現(xiàn)定式的存儲

上圖是三三定式的一部分結(jié)構(gòu)圖。白1尖沖三三，是對三三的一種對策.利用三三位置偏低盡量的壓扁它是一種取勢的下法。黑方走后，輪到白方走。那么我們把黑方在棋盤上的坐標(biāo)位置當(dāng)作樹的根，那么根據(jù)三三定式，白方有可能走的位置就是A、B、C、D、E。1長，也是出頭的要點(diǎn)。如果在A位擋，就會被黑毫不猶豫的在1位扳。被黑扳起來的話，黑的出路寬闊，根據(jù)地也有了。倒是白的頭被捂著，前面和左面和下面的出路都沒有了，只有右邊的出路還沒有根據(jù)地，這樣的棋很被動(dòng)，很容易遭殺。所以，白1長必然，當(dāng)然也有在C位跳的棋.長更堅(jiān)實(shí)有利瞄著B位的拐頭封鎖和A位的擋。_［1]

這相當(dāng)于樹的父節(jié)點(diǎn)為1，1的孩子節(jié)點(diǎn)為A、B、C、D、E。將圍棋中任何一個(gè)定式按步驟展開，我們會發(fā)現(xiàn)定式中每一步都是有序的，且每一步需要保存的信息為該步在棋盤中的坐標(biāo)位置，整個(gè)定式展開與數(shù)據(jù)結(jié)構(gòu)中樹的遍歷很相似。

將一種定式在圍棋棋盤上記錄下來相當(dāng)于建立一棵二叉樹。將樹用孩子兄弟表示法進(jìn)行存儲，有利于對各種操作的實(shí)現(xiàn)。一個(gè)二叉樹的結(jié)點(diǎn)至少保存三種信息：數(shù)據(jù)元素、左孩子位置、右孩子位置，對應(yīng)地，鏈?zhǔn)酱鎯Χ鏄涞慕Y(jié)點(diǎn)至少包含三個(gè)域：數(shù)據(jù)域、左、右指針域。

我們用如下結(jié)構(gòu)體來記錄棋子的信息。

typedef struct btnode

{float x1，y1;

AnsiString jieshou，dir;

AnsiString colour;

struct btnode *lchild，*rchild;

}bitnode，*bitree;

其中x1，y1為圍棋棋子在棋盤中的坐標(biāo)，jieshou為圍棋定式中每一步的解說，dir為建立孩子兄弟表示法時(shí)每一個(gè)節(jié)點(diǎn)的方向，若為l，則為左孩子；若為r，則為右孩子，孩子兄弟表示法中，左為左孩子，右為右兄弟；colour記錄的是棋子的顏色。

利用二叉樹前序遍歷的結(jié)果可以非常方便地生成給定的二叉樹，具體做法是：將第一個(gè)輸入的結(jié)點(diǎn)作為二叉樹的根結(jié)點(diǎn)，后繼輸入的結(jié)點(diǎn)序列是二叉樹左子樹前序遍歷的結(jié)果，由它們生成二叉樹的左子樹；再接下來輸入的結(jié)點(diǎn)序列為二叉樹右子樹前序遍歷的結(jié)果，應(yīng)該由它們生成二叉樹的右子樹；而由二叉樹左子樹前序遍歷的結(jié)果生成二叉樹的左子樹和由二叉樹右子樹前序遍歷的結(jié)果生成二叉樹的右子樹的過程均與由整棵二叉樹的前序遍歷結(jié)果生成該二叉樹的過程完全相同，只是所處理的對象范圍不同，于是完全可以使用遞歸方式加以實(shí)現(xiàn)。_［5]

建立二叉樹可以采用遞歸或者非遞歸的方法，在該程序中采用遞歸的方法，函數(shù)名為ins_node，函數(shù)的主要代碼分析如下：_［2]

ins_node(bitree s，bitree t，String dir) //s、t為二叉樹節(jié)點(diǎn)類型變量

{AnsiString aa=IntToStr(j)+\"-(\"+FloatToStr(s->x1)+\"，\"+FloatToStr(s->y1)+\")是否為左孩\";

//aa為字符串類型變量

if(t＝＝NULL)//判斷節(jié)點(diǎn)是否為空

{ t=s; //為空則插入

if(Table1->TableName!=NULL) //表格名稱是否為空

{String command=\"insertinto\"+Table1->TableName+\"values('\"+FloatToStr(s->x1)+\"'，'\"+FloatToStr(s->y1)+\"'，'\"+t->jieshou+\"'，'\"+_dir+\"')\";

//將坐標(biāo)值等存入數(shù)據(jù)庫的表中

Query1->SQL->Text=command;

Query1->ExecSQL( );

} elseShowMessage(\"沒有建立該表!\");

}

else if(MessageDlg(aa ，mtInformation， TMsgDlgButtons() << mbYes<

//是否為左孩子

{ _dir=_dir+\"l\";

t->lchild=ins_node(s，t->lchild，_dir);

//遞歸建立左子樹

}

else

{_dir=_dir+\"r\";

t->rchild=ins_node(s，t->rchild，_dir);

//遞歸建立右子樹

}

return t;

}

2.2 遍歷二叉樹實(shí)現(xiàn)定式的輸出

建立在存儲結(jié)構(gòu)為樹形結(jié)構(gòu)的基礎(chǔ)上，對圍棋中每一個(gè)定式的顯示就相當(dāng)于對所存儲的二叉樹進(jìn)行遍歷。由于二叉樹是一種非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)可能有一個(gè)以上的直接后繼，因此，必須規(guī)定遍歷的規(guī)則，并按此規(guī)則遍歷二叉樹，最后得到二叉樹所有結(jié)點(diǎn)的一個(gè)線性序列。

二叉樹的遍歷有三種方法：前序遍歷、中序遍歷、后序遍歷。由于每一個(gè)定式的特點(diǎn)，我們可以采用前序遍歷的方法實(shí)現(xiàn)對圍棋定式的顯示。

_preorder( )函數(shù)的功能是通過遞歸調(diào)用對已經(jīng)建立的二叉樹進(jìn)行右子樹遍歷。參數(shù)root為二叉樹的根節(jié)點(diǎn)，biaoji是一個(gè)標(biāo)記值，整形變量，返回值為空。

遞歸算法是遍歷二叉樹常采用的算法，用遞歸寫的二叉樹遍歷程序簡潔且通俗易懂。_preorder( )函數(shù)先判斷當(dāng)前結(jié)點(diǎn)是否為空，若不為空，則設(shè)置要顯示的畫布顏色以及字體顏色，并輸出標(biāo)記符號，遞歸遍歷該結(jié)點(diǎn)的右子樹；若為空則退出。_［3]

該函數(shù)的流程圖見圖1。

_preorder(bitree root，int biaoji) //root為二叉樹的根節(jié)點(diǎn)

{

int k=0;

if(root!=NULL)

{Image1->Canvas->TextOutA(root->x1，root->y1，IntToStr(biaoji));

//根據(jù)遍歷樹的值在畫布上顯示標(biāo)記符號，即指明下一步該走哪一個(gè)位置

biaoji++;

_preorder(root->rchild，biaoji);

//遍歷右兄弟節(jié)點(diǎn)

}

}

本文將數(shù)據(jù)結(jié)構(gòu)中樹的算法應(yīng)用于圍棋定式管理系統(tǒng)，詳盡論述了開發(fā)圍棋定式管理系統(tǒng)各部分主要程序算法的具體思路和方法。應(yīng)用該系統(tǒng)可以隨時(shí)進(jìn)入研究模式自己再琢磨新的走法，研究時(shí)進(jìn)退自如，免除在傳統(tǒng)棋盤上反復(fù)移挪棋子之苦。圍棋是檢驗(yàn)人工智能發(fā)展水平的良好環(huán)境，如何提高圍棋程序的棋力是人工智能領(lǐng)域的一大難題。同時(shí)，開發(fā)出與人類棋手水平相當(dāng)?shù)膰宄绦蛞灿兄趯θ祟愓J(rèn)知能力的理解，計(jì)算機(jī)圍棋研究具有重要的理論意義和實(shí)用價(jià)值。

3 參考文獻(xiàn)

1 西 丁.圍棋基本定式100例[M].四川：署蓉棋藝出版社，1999

2 肖正南.C++ Builder 6編程實(shí)用指南[M].湖北：華中科技大學(xué)出版社，2004

3 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1997