五子棋是一種受大眾廣泛喜愛的游戲，其規(guī)則簡單，變化多端，非常富有趣味性和消遣性。這里設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)人機(jī)對(duì)下的五子棋程序，采用了博弈樹的方法，應(yīng)用了剪枝和最大最小樹原理進(jìn)行搜索發(fā)現(xiàn)最好的下子位置。介紹五子棋程序的數(shù)據(jù)結(jié)構(gòu)、評(píng)分規(guī)則、勝負(fù)判斷方法和搜索算法過程。
一、相關(guān)的數(shù)據(jù)結(jié)構(gòu)
關(guān)于盤面情況的表示，以鏈表形式表示當(dāng)前盤面的情況，目的是可以允許用戶進(jìn)行悔棋、回退等操作。
CList StepList;
其中Step結(jié)構(gòu)的表示為：
struct Step
{
int m; //m,n表示兩個(gè)坐標(biāo)值
int n;
char side; //side表示下子方
};
以數(shù)組形式保存當(dāng)前盤面的情況，
目的是為了在顯示當(dāng)前盤面情況時(shí)使用：
char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
其中FIVE_MAX_LINE表示盤面最大的行數(shù)。
同時(shí)由于需要在遞歸搜索的過程中考慮時(shí)間和空間有效性，只找出就當(dāng)前情況來說相對(duì)比較好的幾個(gè)盤面，而不是對(duì)所有的可下子的位置都進(jìn)行搜索，這里用變量CountList來表示當(dāng)前搜索中可以選擇的所有新的盤面情況對(duì)象的集合：
CList CountList;
其中類CBoardSituiton為:
class CBoardSituation
{
CList StepList; //每一步的列表
char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];
struct Step machineStep; //機(jī)器所下的那一步
double value; //該種盤面狀態(tài)所得到的分?jǐn)?shù)
}
二、評(píng)分規(guī)則
對(duì)于下子的重要性評(píng)分，需要從六個(gè)位置來考慮當(dāng)前棋局的情況，分別為：-,|,/,\,//,\\
實(shí)際上需要考慮在這六個(gè)位置上某一方所形成的子的布局的情況，對(duì)于在還沒有子的地方落子以后的當(dāng)前局面的評(píng)分，主要是為了說明在這個(gè)地方下子的重要性程度，設(shè)定了一個(gè)簡單的規(guī)則來表示當(dāng)前棋面對(duì)機(jī)器方的分?jǐn)?shù)。
基本的規(guī)則如下：
判斷是否能成5, 如果是機(jī)器方的話給予100000分，如果是人方的話給予－100000 分；
判斷是否能成活4或者是雙死4或者是死4活3，如果是機(jī)器方的話給予10000分，如果是人方的話給予－10000分；
判斷是否已成雙活3，如果是機(jī)器方的話給予5000分，如果是人方的話給予－5000 分；
判斷是否成死3活3，如果是機(jī)器方的話給予1000分，如果是人方的話給予－1000 分；
判斷是否能成死4，如果是機(jī)器方的話給予500分，如果是人方的話給予－500分；
判斷是否能成單活3，如果是機(jī)器方的話給予200分，如果是人方的話給予－200分；
判斷是否已成雙活2，如果是機(jī)器方的話給予100分，如果是人方的話給予－100分；
判斷是否能成死3，如果是機(jī)器方的話給予50分，如果是人方的話給予－50分；
判斷是否能成雙活2，如果是機(jī)器方的話給予10分，如果是人方的話給予－10分；
判斷是否能成活2，如果是機(jī)器方的話給予5分，如果是人方的話給予－5分；
判斷是否能成死2，如果是機(jī)器方的話給予3分，如果是人方的話給予－3分。
實(shí)際上對(duì)當(dāng)前的局面按照上面的規(guī)則的順序進(jìn)行比較，如果滿足某一條規(guī)則的話，就給該局面打分并保存，然后退出規(guī)則的匹配。注意這里的規(guī)則是根據(jù)一般的下棋規(guī)律的一個(gè)總結(jié)，在實(shí)際運(yùn)行的時(shí)候，用戶可以添加規(guī)則和對(duì)評(píng)分機(jī)制加以修正。
三、勝負(fù)判斷
實(shí)際上，是根據(jù)當(dāng)前最后一個(gè)落子的情況來判斷勝負(fù)的。實(shí)際上需要從四個(gè)位置判斷，以該子為出發(fā)點(diǎn)的水平，豎直和兩條分別為 45度角和135度角的線，目的是看在這四個(gè)方向是否最后落子的一方構(gòu)成連續(xù)五個(gè)的棋子，如果是的話，就表示該盤棋局已經(jīng)分出勝負(fù)。具體見下面的圖示：
四、搜索算法實(shí)現(xiàn)描述
注意下面的核心的算法中的變量currentBoardSituation，表示當(dāng)前機(jī)器最新的盤面情況, CountList表示第一層子節(jié)點(diǎn)可以選擇的較好的盤面的集合。核心的算法如下：
void MainDealFunction()
{
value=－MAXINT; //對(duì)初始根節(jié)點(diǎn)的value賦值
CalSeveralGoodPlace(currentBoardSituation,CountList);
//該函數(shù)是根據(jù)當(dāng)前的盤面情況來比較得到比較好的可以考慮的幾個(gè)盤面的情況，可以根據(jù)實(shí)際的得分情況選取分?jǐn)?shù)比較高的幾個(gè)盤面，也就是說在第一層節(jié)點(diǎn)選擇的時(shí)候采用貪婪算法，直接找出相對(duì)分?jǐn)?shù)比較高的幾個(gè)形成第一層節(jié)點(diǎn)，目的是為了提高搜索速度和防止堆棧溢出。
pos=CountList.GetHeadPosition();
CBoardSituation＊ pBoard;
for(i=0;ivalue=Search(pBoard,min,value,0);
Value=Select(value,pBoard－>value,max);
//取value和pBoard－>value中大的賦給根節(jié)點(diǎn)
}
for(i=0;ivalue)
//找出那一個(gè)得到最高分的盤面
{
currentBoardSituation=pBoard;
PlayerMode=min; //當(dāng)前下子方改為人
Break;
}
}
其中對(duì)于Search函數(shù)的表示如下：實(shí)際上核心的算法是一個(gè)剪枝過程，其中在這個(gè)搜索過程中相關(guān)的四個(gè)參數(shù)為：（1）當(dāng)前棋局情況；（2）當(dāng)前的下子方，可以是機(jī)器(max)或者是人(min)；（3）父節(jié)點(diǎn)的值oldValue；（4）當(dāng)前的搜索深度depth。
double Search(CBoardSituation＆
board,int mode,double oldvalue,int depth)
{
CList m_DeepList;
if(deptholdvalue))== TRUE)
{
if(mode==max)
value=select(value,search(successor
Board,min,value,depth＋1),max);
else
value=select(value,search(successor
Board,max,value,depth＋1),min);
}
return value;
}
else
{
if ( goal(board)<>0)
//這里goal(board)<>0表示已經(jīng)可以分出勝負(fù)
return goal(board);
else
return evlation(board);
}
}
注意這里的goal(board)函數(shù)是用來判斷當(dāng)前盤面是否可以分出勝負(fù)，而evlation(board)是對(duì)當(dāng)前的盤面從機(jī)器的角度進(jìn)行打分。
下面是Select函數(shù)的介紹，這個(gè)函數(shù)的主要目的是根據(jù) PlayerMode情況，即是機(jī)器還是用戶來返回節(jié)點(diǎn)的應(yīng)有的值。
double Select(double a,double b,int mode)
{
if(a>b ＆＆ mode==max)|| (a< b ＆＆ mode==min)
return a;
else
return b;
}
五、小結(jié)
在Windows操作系統(tǒng)下，用VC＋＋實(shí)現(xiàn)了這個(gè)人機(jī)對(duì)戰(zhàn)的五子棋程序。和國內(nèi)許多只是采用規(guī)則或者只是采用簡單遞歸而沒有剪枝的那些程序相比，在智力上和時(shí)間有效性上都要好于這些程序。同時(shí)所討論的方法和設(shè)計(jì)過程為用戶設(shè)計(jì)其他的游戲（如象棋和圍棋等）提供了一個(gè)參考