五子棋核心算法研究


五子棋是一種受大眾廣泛喜愛(ài)的游戲，其規(guī)則簡(jiǎn)單，變化多端，非常富有趣味性和消遣性。這里設(shè)計(jì)和實(shí)現(xiàn)了一個(gè)人機(jī)對(duì)下的五子棋程序，采用了博弈樹(shù)的方法，應(yīng)用了剪枝和最大最小樹(shù)原理進(jìn)行搜索發(fā)現(xiàn)最好的下子位置。介紹五子棋程序的數(shù)據(jù)結(jié)構(gòu)、評(píng)分規(guī)則、勝負(fù)判斷方法和搜索算法過(guò)程。 

一、相關(guān)的數(shù)據(jù)結(jié)構(gòu) 
    關(guān)于盤(pán)面情況的表示，以鏈表形式表示當(dāng)前盤(pán)面的情況，目的是可以允許用戶進(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)前盤(pán)面的情況， 
目的是為了在顯示當(dāng)前盤(pán)面情況時(shí)使用： 
  char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; 

    其中FIVE_MAX_LINE表示盤(pán)面最大的行數(shù)。 

    同時(shí)由于需要在遞歸搜索的過(guò)程中考慮時(shí)間和空間有效性，只找出就當(dāng)前情況來(lái)說(shuō)相對(duì)比較好的幾個(gè)盤(pán)面，而不是對(duì)所有的可下子的位置都進(jìn)行搜索，這里用變量CountList來(lái)表示當(dāng)前搜索中可以選擇的所有新的盤(pán)面情況對(duì)象的集合： 

  CList CountList; 
    其中類CBoardSituiton為: 
  class CBoardSituation 
  { 
  CList  StepList; //每一步的列表 
  char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; 
  struct Step machineStep;    //機(jī)器所下的那一步 
  double value;  //該種盤(pán)面狀態(tài)所得到的分?jǐn)?shù) 
} 

二、評(píng)分規(guī)則 
    對(duì)于下子的重要性評(píng)分，需要從六個(gè)位置來(lái)考慮當(dāng)前棋局的情況，分別為：-,¦,/,\,//,\\ 


    實(shí)際上需要考慮在這六個(gè)位置上某一方所形成的子的布局的情況，對(duì)于在還沒(méi)有子的地方落子以后的當(dāng)前局面的評(píng)分，主要是為了說(shuō)明在這個(gè)地方下子的重要性程度，設(shè)定了一個(gè)簡(jiǎn)單的規(guī)則來(lái)表示當(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è)落子的情況來(lái)判斷勝負(fù)的。實(shí)際上需要從四個(gè)位置判斷，以該子為出發(fā)點(diǎn)的水平，豎直和兩條分別為 45度角和135度角的線，目的是看在這四個(gè)方向是否最后落子的一方構(gòu)成連續(xù)五個(gè)的棋子，如果是的話，就表示該盤(pán)棋局已經(jīng)分出勝負(fù)。具體見(jiàn)下面的圖示： 


四、搜索算法實(shí)現(xiàn)描述 
    注意下面的核心的算法中的變量currentBoardSituation，表示當(dāng)前機(jī)器最新的盤(pán)面情況, CountList表示第一層子節(jié)點(diǎn)可以選擇的較好的盤(pán)面的集合。核心的算法如下： 
void MainDealFunction() 
{ 
  value=－MAXINT; //對(duì)初始根節(jié)點(diǎn)的value賦值 
CalSeveralGoodPlace(currentBoardSituation,CountList); 
//該函數(shù)是根據(jù)當(dāng)前的盤(pán)面情況來(lái)比較得到比較好的可以考慮的幾個(gè)盤(pán)面的情況，可以根據(jù)實(shí)際的得分情況選取分?jǐn)?shù)比較高的幾個(gè)盤(pán)面，也就是說(shuō)在第一層節(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è)得到最高分的盤(pán)面 
  { 
    currentBoardSituation=pBoard; 
    PlayerMode=min; //當(dāng)前下子方改為人 
    Break; 
  } 
} 

    其中對(duì)于Search函數(shù)的表示如下：實(shí)際上核心的算法是一個(gè)剪枝過(guò)程，其中在這個(gè)搜索過(guò)程中相關(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ù)是用來(lái)判斷當(dāng)前盤(pán)面是否可以分出勝負(fù)，而evlation(board)是對(duì)當(dāng)前的盤(pán)面從機(jī)器的角度進(jìn)行打分。 

    下面是Select函數(shù)的介紹，這個(gè)函數(shù)的主要目的是根據(jù) PlayerMode情況，即是機(jī)器還是用戶來(lái)返回節(jié)點(diǎn)的應(yīng)有的值。 

double Select(double a,double b,int mode) 
{ 
  if(a>b ＆＆ mode==max)&brvbar;&brvbar; (a< b ＆＆ mode==min) 
return a; 
  else 
return b; 
} 

五、小結(jié) 
    和國(guó)內(nèi)許多只是采用規(guī)則或者只是采用簡(jiǎn)單遞歸而沒(méi)有剪枝的那些程序相比，在智力上和時(shí)間有效性上都要好于這些程序。同時(shí)所討論的方法和設(shè)計(jì)過(guò)程為用戶設(shè)計(jì)其他的游戲（如象棋和圍棋等）提供了一個(gè)參考