VC完成五子棋游戲的一個算法示例

VC完成五子棋游戲的一個算法示例。本站提示廣大學習愛好者：（VC完成五子棋游戲的一個算法示例）文章只能為提供參考，不一定能成為您想要的結果。以下是VC完成五子棋游戲的一個算法示例正文

本文講述了VC完成五子棋游戲的一個算法示例，該算法采取極年夜極小剪枝博弈算法，感興致的讀者可以對法式中不完美的部門停止修正與完美。

該設計重要包含：數據構造、估值函數、輸贏斷定、搜刮算法

法式運轉界面以下：

詳細完成步調以下：

1、數據構造

//記載每步棋，可以樹立鏈表用來停止悔棋、撤退退卻(本法式沒有完成)
struct Step
{
 int x,y; //棋子坐標
 int ball; //表現下子方{BLACK,WHITE}
};
//記載棋盤情形，用於搜刮進程
class CBoardSituation
{
 public:
 int nArrBoard[15][15]; //棋盤情形
 struct Step machineStep; //AI所下的那一步
 long value; //盤面所打的分數
};
//以後棋盤，用於棋盤顯示
int nArrBoard[15][15];

2、估值函數

剖析以後棋盤上诟谇兩邊棋型：五連、活4、沖4、雙活3、單活3、眠3、活2、眠二，然後依據五子棋規矩給棋盤打分，
詳細分值可以依據經歷本身肯定。本法式中：五連=9999(極值)，活四=9990，沖四=9980，雙活三=9970，多活三加2000，
單活三加200，每一個眠三加10，每一個活二加4，每一個眠二加1。個中打分時還要依據以後下棋方情形停止打分。

3、輸贏斷定

這個比擬簡略，依據最初落子情形從程度、垂直、左斜、右斜四個偏向檢討能否存在五個持續棋子便可。

4、搜刮算法

算法采取極年夜極小值博弈算法，它的重要思惟為：猜測後N步下棋情形，對猜測的後N個棋盤停止打分。輪到本身下棋時選分值最年夜的，輪到對方下時選分值最小的。選出我們以為最優的作為下一步走法。本法式算法根本思惟以下(算法說話表現)：

void DFAI()
{
 long value=-MAXINT; //對初始根節點的value賦值
 CBoardSituation currentBoard;
 //獲得以後機械新棋面情形
 for(int i=0;i<15;i++)
 for(int j=0;j<15;j++)
  currentBoard.nArrBoard[i][j]=nArrBoard[i][j];
 currentBoard.machineStep.ball=ComputerBall;
 currentBoard.machineStep.x=gnRow;
 currentBoard.machineStep.y=gnColumn;
 currentBoard.value=Eveluate(currentBoard.nArrBoard,BLACK);
 //拔取幾個最好的下法（貪心法）-->CountList;
 GetSeveralGoodPlace(¤tBoard,WHITE);
 CountList.RemoveAll();
 POSITION pos=templist.GetHeadPosition();
 for(int j=0;j {
 CountList.AddTail(templist.GetNext(pos));
 }
 pos=CountList.GetHeadPosition();
 CBoardSituation *pBoard;
 //對這些盤面做進一步深度搜刮
 for(i=0;i {
 pBoard= &(CountList.GetNext(pos));
 pBoard->value=Search(pBoard,BLACK,value,0);
 value=Select(value,pBoard->value,WHITE); //找出最年夜的分值
 }
 //回到鏈表頭
 pos=CountList.GetHeadPosition();
 for(i=0;i {
 pBoard= &(CountList.GetNext(pos));
 if (value==pBoard->value) //找出獲得最高分的盤面
 {
  value=pBoard->value;
  gnRow=pBoard->machineStep.x;
  gnColumn=pBoard->machineStep.y;
  bPlayerDo=TRUE; //以後下子方改成人
  break;
 }
 }
 //其他處置
}
個中Search()函數以下：
//算法搜刮函數
long Search(CBoardSituation *board,int mode,long &oldvalue, int depth)
{
 CList m_DeepList;
 long value;
 if(depthnArrBoard,mode))<8000)
 {
 value=(mode==WHITE)?-MAXINT:MAXINT;
 //選擇幾個最好的搜刮目的
 GetSeveralGoodPlace(board,mode);
 POSITION pos=templist.GetHeadPosition();
 for(int j=0;j {
  m_DeepList.AddTail(templist.GetNext(pos));
 }
 pos=m_DeepList.GetHeadPosition();
 CBoardSituation successorBoard;
 for(int i=0;i {
  successorBoard= m_DeepList.GetNext(pos);
  //能否停止持續深度搜刮(剪枝):極年夜極小值法
  if((mode==WHITE && value<=oldvalue) || (mode==BLACK && value>=oldvalue))
  {
  if(mode==WHITE)
   value=Select(value,Search(&successorBoard,BLACK,value,depth+1),WHITE);
  else//mode==BLACK
   value=Select(value,Search(&successorBoard,WHITE,value,depth+1),BLACK);
  }
 }
 return value;
 }
 else//搜刮停止前提
 {
 return Eveluate(board->nArrBoard,mode);//棋面打分
 }
 return 0;
}