問題分析設計目錄

• • 棋盤顯示和標記以及棋盤的設計
  • 搜索樹葉子節點設計
  • 搜索樹設計
  • 節點靜態估值計算
  • 完整代碼
  • 總結

棋盤顯示和標記以及棋盤的設計

用int一維數組表示一字棋的棋盤位置，0~8，數組位置i即棋盤位置，數組元素的值表示該位置的下棋情況。0表示未下棋，1表示用戶選手下棋，2表示電腦下棋。比如
chessman[6] = 1; 表示第六個位置下了用戶選手的棋。

//一字棋棋盤 一共9個格子 typedef struct{int chessman[9]; }ChessBoard;

搜索樹葉子節點設計

定義一個BiTNode節點，只表示搜索樹的葉子節點，里面存放了一個棋盤，這個棋盤是棋局中某一步棋的情況，里面包括了電腦可能下棋的位置和用戶選手可能做的下一步棋的位置。Value值是該節點的靜態估值，當該節點形成后，可以計算靜態估值。

//搜索樹節點的定義 typedef struct BiTNode{ChessBoard chessboard; //chessboard 一個棋盤以及所有棋子落子的情況 int CoordinateAI; //這一步棋子的位置 ChessMan[]0~8 int CoordinatePlayer; //這一步是選手可能落下棋子的位置 int Value; //節點的估價值 }BiTNode; BiTNode Head; //頭結點 //BiTNode *TreeBoard;#define MAX 100#define MIN -100#define DOGFALL 50 //平局

搜索樹設計

本次設計我沒有用到數據結構中嚴格意義上的樹，設計時覺得有點麻煩，沒有用二叉樹表示，但我又有自己的想法實現邏輯上的搜索樹，并且這棵搜索樹做兩層就夠了，這個想法目前只適用于一字棋。搜索樹用節點二維數組表示。
Max節點的估價值用一維數組aFatherValue[9]表示。

BiTNode a[9][9]; //極大極小搜索樹用數組表示 int aFatherValue[9]; //Max節點的估價函數值，選取該節點所有孩子節點的最小估價函數賦值

搜索樹表示如圖所示：

節點靜態估值計算

在一盤棋中，又八種可能連成一線的的結果。在博弈當中的任何一方都考慮完他們八種情況的結局有幾種是可能實現的就行了。橫豎各三種，斜著兩種一共八種。計算設計如下所示。用二維數組judge[8][[3]]列出八種情況對應的位置值，然后按著順序遍歷一組一組遍歷八組就行了。當一組位置中的三個位置只要有一處是存在對手中的棋子，則這一組就不可能用自己的棋子連成三點一線。

//判斷某一方可能獲勝結果的個數 int checkValue(int x, int y, ChessBoard *chessboard){int value = 0;int judge[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};int coordinate ;for(int i=0; i<=7; i++){int j = 0;;for(j=0; j<=2; j++){coordinate = judge[i][j];//判斷8個勝利的可能是否有對手的棋子，如果有，則可判定這個結果不可能勝算 if(chessboard->chessman[coordinate] == x ){ break;} }if(j>2){value++;} }return value; }

因為只需要電腦的考慮，所以用電腦的減去用戶選手可能勝利的個數，就能得到靜態估值。在計算節點的靜態估價值函數中，如果對手的棋連成了三點一線，則直接返回Min，如果是電腦的棋連成線，則返回Max。

//計算節點的靜態估價值 int EvaluationFunction(ChessBoard *chessboard){ // ChessBoard *p = &chessboard; int EvaluationAI = checkValue(1,2,chessboard); //AI的勝算 int EvaluationPlayer = checkValue(2,1,chessboard); //對手的勝算 int Evaluation = EvaluationAI - EvaluationPlayer;int judge[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};int coordinate ;int valueX;int valueY;for(int i=0; i<=7; i++){valueX = 0;valueY = 0;for(int j=0; j<=2;j++){coordinate = judge[i][j];if(chessboard->chessman[coordinate] == 1){valueX++;}if(chessboard->chessman[coordinate] == 2){valueY++;}}if(valueX == 3){return MIN;}if(valueY == 3){return MAX;}}return Evaluation; }

完整代碼

#include<stdio.h> #include<windows.h>//棋子 x,y是棋子的坐標位置，value是判斷該坐標是否落有棋子 0表示沒有落棋 1表示X自己下的棋 2表示〇AI下的棋 //一字棋棋盤 一共9個格子 typedef struct{int chessman[9]; }ChessBoard; //搜索樹節點的定義 typedef struct BiTNode{ChessBoard chessboard; //chessboard 一個棋盤以及所有棋子落子的情況 int CoordinateAI; //這一步棋子的位置 ChessMan[]0~8 int CoordinatePlayer; //這一步是選手可能落下棋子的位置 int Value; //節點的估價值 }BiTNode; BiTNode Head; //頭結點 //BiTNode *TreeBoard;#define MAX 100#define MIN -100#define DOGFALL 50 //平局 void initialBoard(ChessBoard *chessboard); //初始化一個棋盤，對一字棋棋盤的每個格子規定坐標int EvaluationFunction(ChessBoard *chessboard); //計算節點的靜態估價值 int checkValue(int x,int y, ChessBoard *chessboard); //判斷某一方可能獲勝結果的個數 void PlayChess(int x, int play, ChessBoard *chessboard); //下棋 int PlayAI(ChessBoard *chessboard); //AI考慮下棋 void DrawBoard(ChessBoard *chessboard); //繪畫棋盤,給用戶顯示 int PlayAI(ChessBoard *chessboard); //電腦考慮下棋 int judgeBoard(ChessBoard *chessboard); 當某一方下棋后，判斷結果 int main(){int first = 0;int play; int playNum = 0; //記錄運行步數 如果大于9，說明平局 printf("歡迎來到一字棋游戲；x代表你下的棋，〇代表電腦下的棋 該棋盤9個棋子的位置對應坐標如下：\n");printf("-------------------\n") ;printf("| 0 | 1 | 2 |\n\n");printf("| 3 | 4 | 5 |\n\n");printf("| 6 | 7 | 8 |\n");printf("-------------------\n\n");printf("當你和機器對弈時，請輸入你下的棋子位置對應的坐標，比如想下在最中間的位置就輸入4\n");printf("現在請選擇這局一字棋游戲誰先走第一步，請輸入0或1，0代表機器先下 1代表你先下\n");scanf("%d",&first);ChessBoard playChessBoard; //整局游戲的一盤棋，同時也可當作頭結點 ChessBoard *playBoard = &playChessBoard; //棋盤指針 initialBoard(playBoard); //傳指針 if(first == 1){printf("-------------------\n") ;printf("| 0 | 1 | 2 |\n\n");printf("| 3 | 4 | 5 |\n\n");printf("| 6 | 7 | 8 |\n");printf("-------------------\n\n");printf("請輸入你下棋的位置：");scanf("%d",&play);PlayChess(1,play, playBoard); //用戶選手下棋 DrawBoard(playBoard);playNum++;}else{int AI = PlayAI(playBoard); //AI考慮下棋 printf("電腦下棋的位置: %d\n",AI); PlayChess(2,AI, playBoard); //電腦選手下棋 playNum++;DrawBoard(playBoard); //顯示給用戶下棋 printf("請你做下一步棋：");scanf("%d",&play);}int playNext = 1; //定義一個整形數據，決定下一步誰下棋 1表示用戶選手下棋 2表示電腦下棋 if(first == 1){playNext = 2;}int finalResult = 0;while(playNum<9){if(playNext == 2){ int AI = PlayAI(playBoard);PlayChess(2,AI, playBoard); //電腦下棋 printf("電腦下棋的位置: %d\n",AI);DrawBoard(playBoard);finalResult = judgeBoard(playBoard);if(playNum != 8 && finalResult!= 2){printf("請你做下一步棋：");scanf("%d",&play);} playNext = 1; }else if(playNext == 1){PlayChess(1,play, playBoard); //用戶選手下棋 DrawBoard(playBoard);playNext = 2; //下一步電腦下棋 }finalResult = judgeBoard(playBoard);if(finalResult == 1){printf("你贏了!\n");break;}if(finalResult == 2){printf("電腦贏了！");break;}playNum++;}if(playNum == 9){printf("結果平局\n");}printf("游戲結束！");return 0; } //初始化一個棋盤，對一字棋棋盤的每個格子規定坐標 void initialBoard(ChessBoard *chessboard){for(int i=0; i<=8; i++){ //將棋盤的所有棋子標為0，表示為未落子 // *chessboard.chessman[i] = 0; chessboard->chessman[i] = 0;} } //計算節點的靜態估價值 int EvaluationFunction(ChessBoard *chessboard){ // ChessBoard *p = &chessboard; int EvaluationAI = checkValue(1,2,chessboard); //AI的勝算 int EvaluationPlayer = checkValue(2,1,chessboard); //對手的勝算 int Evaluation = EvaluationAI - EvaluationPlayer;int judge[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};int coordinate ;int valueX;int valueY;for(int i=0; i<=7; i++){valueX = 0;valueY = 0;for(int j=0; j<=2;j++){coordinate = judge[i][j];if(chessboard->chessman[coordinate] == 1){valueX++;}if(chessboard->chessman[coordinate] == 2){valueY++;}}if(valueX == 3){return MIN;}if(valueY == 3){return MAX;}}return Evaluation; }//判斷某一方可能獲勝結果的個數 int checkValue(int x, int y, ChessBoard *chessboard){int value = 0;int judge[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};int coordinate ;for(int i=0; i<=7; i++){int j = 0;;for(j=0; j<=2; j++){coordinate = judge[i][j];//判斷8個勝利的可能是否有對手的棋子，如果有，則可判定這個結果不可能勝算 if(chessboard->chessman[coordinate] == x ){ break;} }if(j>2){value++;} }return value; }//下棋 void PlayChess(int x, int play, ChessBoard *chessboard){chessboard->chessman[play] = x; }//繪畫棋盤,給用戶顯示 void DrawBoard(ChessBoard *chessboard){int i;int num = 0;printf("-------------------\n");for(i=0; i<=8; i++){if(chessboard->chessman[i] == 1){printf("| X ");}else if(chessboard->chessman[i] == 2){printf("| 〇 ");}else{printf("| %d ",i);}num++;if(num%3 == 0){printf("|\n\n");}}printf("-------------------\n\n"); } //AI考慮下棋 int PlayAI(ChessBoard *chessboard){for(int i=0; i<=8; i++){//給頭結點棋盤賦值 當前結點棋盤的棋子保持情況 Head.chessboard.chessman[i] = chessboard->chessman[i]; } int aFatherValue[9]; //Max節點的估價函數值，選取該節點所有孩子節點的最小估價函數賦值 for(int i=0;i<=8;i++){aFatherValue[i] = MIN; //初始化 } BiTNode a[9][9]; //極大極小搜索樹用數組表示 for(int i=0; i<=8; i++){ //這個for循環是遍歷頭結點的所有子節點，即max結點 for(int j=0; j<=8; j++){ //這個for循環是將max結點的所有子節點對局詳情棋盤復寫 for(int k=0; k<=8; k++){a[i][j].chessboard.chessman[k] = Head.chessboard.chessman[k]; //將當前對局的棋保存在結點棋盤里 }a[i][j].Value =MAX; //該節點估價函數賦值為MIN 初始為最大 a[i][j].CoordinateAI = -1;a[i][j].CoordinatePlayer = -1;} } //搜索樹生成，并用極大極小值求出頭結點的估價函數 求出電腦選手下棋的位置 int min = MAX;for(int i=0; i<=8; i++){if(Head.chessboard.chessman[i] == 0){min = MAX;for(int j=0; j<=8; j++){a[i][j].CoordinateAI = i;a[i][j].chessboard.chessman[i] = 2; //電腦可能下的棋 if(a[i][j].chessboard.chessman[j] == 0){a[i][j].CoordinatePlayer = j; //選手可能下的位置 a[i][j].chessboard.chessman[j] = 1; //選手可能下的棋 ChessBoard *p = &a[i][j].chessboard; //定義一個指針 用來（求估價函數 ）判斷結果 a[i][j].Value = EvaluationFunction(p); //求估價函數 求估價函數值還是需要傳指針 if(a[i][j].Value <= min){ //求出max結點的估價函數值 min = a[i][j].Value; }} } aFatherValue[i] = min; //給有葉子節點的max節點賦值 求其所有葉子節點中最小的賦值 // printf("電腦下%d位置的max節點值為%d\n\n\n\n",i,aFatherValue[i]); // printf(aFatherValue[i]); }}int max = MIN;for(int i=0; i<=8; i++){if(Head.chessboard.chessman[i] == 0){if(aFatherValue[i] > max){max = aFatherValue[i];Head.CoordinateAI = i; //給頭結點中電腦應下的位置做標記 有利于返回結果 }} }return Head.CoordinateAI; }//當某一方下棋后，判斷結果 int judgeBoard(ChessBoard *chessboard){int Co;int judge[8][3] = {{0,1,2},{3,4,5},{6,7,8},{0,3,6},{1,4,7},{2,5,8},{0,4,8},{2,4,6}};int x = 1;int y = 2;int valueX = 0;int valueY = 0;for(int i=0; i<=7; i++){valueX =0;valueY = 0;for(int j=0; j<=2; j++){Co = judge[i][j];if(chessboard->chessman[Co] == 1){valueX++;}if(chessboard->chessman[Co] == 2){valueY++;}}if(valueX == 3){return x;}if(valueY == 3){return y;}}return 0; }

總結

我的一字棋游戲實現落棋輸入沒有進行限制，用戶違規下棋了沒有進行相應的阻止和提示。這是本程序缺點中的一個。棋盤顯示不是我個人原創的，但算法的實現是自己設計的。本次算法沒有考慮是棋盤對稱問題，我是把所有落子的情況都考慮了，最原始的搜索樹是固定大小的。就是一個二維數組，把有棋的位置不做考慮。當游戲進行到后面時，邏輯上的搜索樹是越來越小的。我寫的搜索樹在邏輯上是極大極小搜素樹的，但是樹的實際存儲空間是同樣大小的。在編程方面，模塊化結構設計非常好用，本次寫程序出現bug時，繪畫棋盤DrawBoard（）函數就能發揮非常大的用處了。

總結

以上是生活随笔為你收集整理的用C语言实现简单的一字棋游戏的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。