五子棋的核心算法

1、五子棋的核心算法工具軟件 編程開發(fā) >> 心得算法 >> 正文 2004年2月18日 星期三 五子棋的核心算法 五子棋是一種受大眾廣泛喜愛的游戲，其規(guī)則簡單，變化多端，非常富有趣味性和消遣性。這里設(shè)計和實現(xiàn)了一個人機對下的五子棋程序，采用了博弈樹的方法，應(yīng)用了剪枝和最大最小樹原理進行搜索發(fā)現(xiàn)最好的下子位置。介紹五子棋程序的數(shù)據(jù)結(jié)構(gòu)、評分規(guī)則、勝負判斷方法和搜索算法過程。 一、相關(guān)的數(shù)據(jù)結(jié)構(gòu) 關(guān)于盤面情況的表示，以鏈表形式表示當(dāng)前盤面的情況，目的是可以允許用戶進行悔棋、回退等操作。 CList StepList; 其中Step結(jié)構(gòu)的表示為： struct Step int

2、 m; /m,n表示兩個坐標值 int n; char side; /side表示下子方 ; 以數(shù)組形式保存當(dāng)前盤面的情況， 目的是為了在顯示當(dāng)前盤面情況時使用： char FiveAreaFIVE_MAX_LINEFIVE_MAX_LINE; 其中FIVE_MAX_LINE表示盤面最大的行數(shù)。 同時由于需要在遞歸搜索的過程中考慮時間和空間有效性，只找出就當(dāng)前情況來說相對比較好的幾個盤面，而不是對所有的可下子的位置都進行搜索，這里用變量CountList來表示當(dāng)前搜索中可以選擇的所有新的盤面情況對象的集合： CList CountList; 其中類CBoardSituiton為: class

3、CBoardSituation CList StepList; /每一步的列表 char FiveAreaFIVE_MAX_LINEFIVE_MAX_LINE; struct Step machineStep; /機器所下的那一步 double value; /該種盤面狀態(tài)所得到的分數(shù) 二、評分規(guī)則 對于下子的重要性評分，需要從六個位置來考慮當(dāng)前棋局的情況，分別為：-,¦,/,/, 實際上需要考慮在這六個位置上某一方所形成的子的布局的情況，對于在還沒有子的地方落子以后的當(dāng)前局面的評分，主要是為了說明在這個地方下子的重要性程度，設(shè)定了一個簡單的規(guī)則來表示當(dāng)前棋面對機器方的分

4、數(shù)。 基本的規(guī)則如下： 判斷是否能成5, 如果是機器方的話給予100000分，如果是人方的話給予100000 分； 判斷是否能成活4或者是雙死4或者是死4活3，如果是機器方的話給予10000分，如果是人方的話給予10000分； 判斷是否已成雙活3，如果是機器方的話給予5000分，如果是人方的話給予5000 分； 判斷是否成死3活3，如果是機器方的話給予1000分，如果是人方的話給予1000 分； 判斷是否能成死4，如果是機器方的話給予500分，如果是人方的話給予500分； 判斷是否能成單活3，如果是機器方的話給予200分，如果是人方的話給予200分； 判斷是否已成雙活2，如果是機器方的話給予1

5、00分，如果是人方的話給予100分； 判斷是否能成死3，如果是機器方的話給予50分，如果是人方的話給予50分； 判斷是否能成雙活2，如果是機器方的話給予10分，如果是人方的話給予10分； 判斷是否能成活2，如果是機器方的話給予5分，如果是人方的話給予5分； 判斷是否能成死2，如果是機器方的話給予3分，如果是人方的話給予3分。 實際上對當(dāng)前的局面按照上面的規(guī)則的順序進行比較，如果滿足某一條規(guī)則的話，就給該局面打分并保存，然后退出規(guī)則的匹配。注意這里的規(guī)則是根據(jù)一般的下棋規(guī)律的一個總結(jié)，在實際運行的時候，用戶可以添加規(guī)則和對評分機制加以修正。 三、勝負判斷 實際上，是根據(jù)當(dāng)前最后一個落子的情況來判

6、斷勝負的。實際上需要從四個位置判斷，以該子為出發(fā)點的水平，豎直和兩條分別為 45度角和135度角的線，目的是看在這四個方向是否最后落子的一方構(gòu)成連續(xù)五個的棋子，如果是的話，就表示該盤棋局已經(jīng)分出勝負。具體見下面的圖示： 四、搜索算法實現(xiàn)描述 注意下面的核心的算法中的變量currentBoardSituation，表示當(dāng)前機器最新的盤面情況, CountList表示第一層子節(jié)點可以選擇的較好的盤面的集合。核心的算法如下： void MainDealFunction() value=MAXINT; /對初始根節(jié)點的value賦值 CalSeveralGoodPlace(currentBoardSi

7、tuation,CountList); /該函數(shù)是根據(jù)當(dāng)前的盤面情況來比較得到比較好的可以考慮的幾個盤面的情況，可以根據(jù)實際的得分情況選取分數(shù)比較高的幾個盤面，也就是說在第一層節(jié)點選擇的時候采用貪婪算法，直接找出相對分數(shù)比較高的幾個形成第一層節(jié)點，目的是為了提高搜索速度和防止堆棧溢出。 pos=CountList.GetHeadPosition(); CBoardSituation pBoard; for(i=0;ivalue=Search(pBoard,min,value,0); Value=Select(value,pBoard>value,max); /取value和pBoard&

8、gt;value中大的賦給根節(jié)點 for(i=0;ivalue) /找出那一個得到最高分的盤面 currentBoardSituation=pBoard; PlayerMode=min; /當(dāng)前下子方改為人 Break; 其中對于Search函數(shù)的表示如下：實際上核心的算法是一個剪枝過程，其中在這個搜索過程中相關(guān)的四個參數(shù)為：（1）當(dāng)前棋局情況；（2）當(dāng)前的下子方，可以是機器(max)或者是人(min)；（3）父節(jié)點的值oldValue；（4）當(dāng)前的搜索深度depth。 double Search(CBoardSituation board,int mode,double oldvalue,i

9、nt depth) CList m_DeepList; if(deptholdvalue)= TRUE) if(mode=max) value=select(value,search(successor Board,min,value,depth1),max); else value=select(value,search(successor Board,max,value,depth1),min); return value; else if ( goal(board)<>0) /這里goal(board)<>0表示已經(jīng)可以分出勝負 return goal(board); else return evlation(board); 注意這里的goal(board)函數(shù)是用來判斷當(dāng)前盤面是否可以分出勝負，而evlation(board)是對當(dāng)前的盤面從機器的角度進行打分。 下面是Select函數(shù)的介紹，這個函數(shù)的主要目的是根據(jù) PlayerMode情況，即是機器還是用戶來返回節(jié)點的應(yīng)有的值。 double Select(double a,double b,int mode) if(a>b mode=max)&brvbar;&brvbar; (a< b mode=min) r