1、基于極大極小分析法的井字棋對弈任務(wù)分析：首先，我們要知道，“井字棋”游戲（又叫“三子棋”），是一款十分經(jīng)典的益智小游戲，想必很多玩家都有玩過?！熬制濉钡钠灞P很簡單，是一個33的格子，很像中國文字中的“井”字，所以得名“井字棋”?！熬制濉庇螒虻囊?guī)則與“五子棋”十分類似，“五子棋”的規(guī)則是一方首先五子連成一線就勝利；“井字棋”是一方首先三子連成一線就勝利。 游戲時一方是電腦，另一方是玩家。所以，這類游戲在開始時有兩種方式：一種是玩家先走；另一種是電腦先走。這是我們要考慮的第一個問題。 其次，由于與玩家對戰(zhàn)的是計算機，所以我們要編寫一個過程，它可以使程序模擬人的思維與人下棋（其實就是“人工智能”

2、的體現(xiàn)），這個過程也是本游戲的關(guān)鍵。此外，我們還要編寫兩個過程，其一用來時刻判斷棋盤中是否有三個棋子連成一線；其二用來判斷如果有三個棋子連成一線，是哪一方連成一線的，即判斷哪一方獲勝。如圖所示為井字棋的一個格局,而格局之間的關(guān)系是由比賽規(guī)則決定的.通常,這個關(guān)系不是線性的,因為從一個棋盤格局可以派生出幾個格局.例如圖左側(cè)所示的格局可以派生出5歌格局.例如圖右側(cè)所示,而從每一個新的格局又可派生出4個可能出現(xiàn)的格局.因此,若將從對弈開始到結(jié)束的過程中所有可能出現(xiàn)的格局都畫在一張圖上，則可以得到一顆倒長的”樹”.圖1 對弈問題中格局之間的關(guān)系設(shè)計思路設(shè)有九個空格，由MAX，MIN二人對弈，輪到誰走棋

3、誰就往空格上放一只自己的棋子，誰先使自己的棋子構(gòu)成“三子成一線”(同一行或列或?qū)蔷€全是某人的棋子)，誰就取得了勝利。 用叉號表示MAX，用圓圈代表MIN。 為了不致于生成太大的博弈樹，假設(shè)每次僅擴展兩層。估價函數(shù)定義如下： 設(shè)棋局為P，估價函數(shù)為e(P)。 (1) 若P對任何一方來說都不是獲勝的位置，則e(P)=e(那些仍為MAX空著的完全的行、列或?qū)蔷€的總數(shù))-e(那些仍為MIN空著的完全的行、列或?qū)蔷€的總數(shù)。(2) 若P是MAX必勝的棋局，則e(P)+。 (3) 若P是B必勝的棋局，則e(P)-。要注意利用棋盤位置的對稱性,在生成后繼節(jié)點的位置時，下列博弈結(jié)局都是相同的棋局(在博弈中

4、，一宇棋的分枝系數(shù)比較小起初是由于對稱性，而后是由于棋盤上未布子的空格減少所致)。 現(xiàn)在我們假設(shè)MAX走了這一步，而MIN的回步是直接在X上方的空格里放上一個圓圈(對MAX來說這是一步壞棋，他一定沒有采用好的搜索策略)。下一步，MAX又在新的格局下搜索兩層. 現(xiàn)在圖中MAX有兩個可能“最好的”優(yōu)先走步，假設(shè)MAX走了圖上指明的那一步。而MIN為了避免立即敗北被迫走了另一步，從而產(chǎn)生如下棋局：MAX再次搜索. 在這棵樹中某些端節(jié)點(例如其中一個標記著A)代表MIN獲勝，因此它們的估值為。當這些估值被倒推回去時，可看到MAX的最好的也是唯一能使他避免立即失敗的一個走步。現(xiàn)在，MIN可以看出MAX必

5、然在他的下一走步中獲勝，因此，MIN只好認輸。流程圖設(shè)計步驟(1) 選定博弈算法； (2) 建立一個簡單的應(yīng)用程序（如字符界面程序）來測試算法； (3) 選定圖形界面中要實現(xiàn)的其他功能; (4) 實現(xiàn)圖形界面的井字棋程序。算法測試程序功能的函數(shù)：(1) 可能勝利的方法： struct CHESS_MAN(2)顯示棋盤邊框: void disp_chess_board(void) (3) 打印棋盤函數(shù)： void init_chess_board(void) (4) 用戶輸入落子位置函數(shù): int enter_chess_man (5) 判斷函數(shù): int chk_winner(int play

6、er) (6)評估函數(shù)值計算函數(shù)： int get_best_chess (判斷哪一方獲勝包含在5和6中)總程序：#include stdio.h #include malloc.h #define SIZE 3 #ifndef FALSE #define FALSE 0 #endif #ifndef TRUE #define TRUE 1 #endif #define NONE 0 #define PLAYER_A 1 #define PLAYER_B 2 #define WARNNING 255 #define COMPETITOR 200 #define WINNER -1 char c

7、hessboardSIZESIZE; struct CHESS_MAN int row; int col; ; /*PLAYER可能勝利的方法*/ int get_value(int player) int i,j,ret=0; int row,col,inc; int bNONE=FALSE; /*檢查所有行*/ for(i=0;iSIZE;i+) row=SIZE; bNONE=FALSE; for(j=0;jSIZE;j+) if(chessboardij=player) row-; /*如果該位置有player的棋子占據(jù)*/ if(chessboardij=NONE) bNONE=TR

8、UE; /*如果該位置還沒有棋子占據(jù)，則返回bNONE為TRUE*/ if(row=1&bNONE=TRUE) return WARNNING; /*電腦:該行中有一個空位且有對手下的2個旗子,則可能會輸?shù)粼摼?，返回WARNNING值）*/ else if(row=SIZE) ret+; /*電腦:該行中沒有player的棋子，ret+1*/ /*檢查所有列*/ for(i=0;iSIZE;i+) col=SIZE; bNONE=FALSE; for(j=0;jSIZE;j+) if(chessboardji=player) col-; /*如果該位置有player的棋子占據(jù)*/ if(che

9、ssboardji=NONE) bNONE=TRUE; /*如果該位置還沒有棋子占據(jù)，則返回bNONE為TRUE*/ if(col=1&bNONE=TRUE) return WARNNING; /*電腦:該列中有一個空位且有對手下的2個旗子,則可能會輸?shù)粼摼?，返回WARNNING值*/ else if(col=SIZE) ret+; /*電腦:該列中沒有player的棋子，ret+1*/ /*檢查左對角線*/ inc=SIZE; bNONE=FALSE; for(i=0,j=0;iSIZE;i+,j+) if(chessboardij=player) inc-; /*如果該位置有player的

10、棋子占據(jù)*/ if(chessboardij=NONE) bNONE=TRUE; /*如果該位置還沒有棋子占據(jù)，則返回bNONE為TRUE*/ if(inc=1&bNONE=TRUE) return WARNNING; /*電腦:左對角線中有一個空位且有對手下的2個旗子,可能會輸?shù)粼摼郑祷豔ARNNING值*/ else if(inc=SIZE) ret+; /*電腦:左對角線中沒有player的棋子，ret+1*/*檢查右對角線*/ inc=SIZE; bNONE=FALSE; for(i=0,j=SIZE-1;iSIZE;i+,j-) if(chessboardij=player) in

11、c-; /*如果該位置有player的棋子占據(jù)*/ if(chessboardij=NONE) bNONE=TRUE; /*如果該位置還沒有棋子占據(jù)，則返回bNONE為TRUE*/ if(inc=1&bNONE=TRUE) return WARNNING; /*電腦:右對角線中有一個空位且有對手下的2個旗子,可能會輸?shù)粼摼?，返回WARNNING值*/ else if(inc=SIZE) ret+; /*電腦:右對角線中沒有player的棋子，ret+1*/ return ret; ; /*顯示棋盤圖形邊框*/ void disp_chess_board(void) int i,j; /*顯示棋

12、盤最頂層邊框*/ for(i=0;iSIZE*4+1;i+) printf(-); printf(n); /*顯示3層棋盤格落子情況及其左、右和下邊框*/ for(i=0;iSIZE;i+) printf(|); for(j=0;jSIZE;j+) if(chessboardij=PLAYER_A) printf( o |); /*如果是PLAYER_A落子則用o表示棋子*/ else if(chessboardij=PLAYER_B) printf( x |); /*如果是PLAYER_B落子則用x表示棋子*/ else printf( |); printf(n); /*輸出該層下邊框*/

13、for(j=0;jSIZE*4+1;j+) printf(-); printf(n); return; ; /*棋盤初始狀況*/ void init_chess_board(void) int i,j; for(i=0;iSIZE;i+) for(j=0;j=SIZE|col=SIZE) return FALSE; /*輸入位置超出棋盤坐標，不能落子*/ if(chessboardrowcol!=NONE) return FALSE; /*輸入當該位置已有棋子占據(jù)，不能落子*/ chessboardrowcol=player; /*玩家落子*/ return TRUE; ; /*判斷勝利狀況*

14、/ int chk_winner(int player) int i,j; int col,row,inc; /*占滿一行*/ for(i=0;iSIZE;i+) row=TRUE; for(j=0;jSIZE;j+) if(chessboardij!=player) row=FALSE; if(row=TRUE) return TRUE; /*占滿一列*/ for(i=0;iSIZE;i+) col=FALSE; for(j=0;jSIZE;j+) if(chessboardji!=player) col=FALSE; if(col=TRUE) return TRUE; /*占滿左對角線*/

15、 inc=TRUE; j=0; for(i=0;iSIZE;i+) if(chessboardii+j!=player) inc=FALSE; if(inc=TRUE) return TRUE; /*占滿右對角線*/ inc=TRUE; j=SIZE-1; for(i=0;iSIZE;i+) if(chessboardij-i!=player) inc=FALSE; if(inc=TRUE) return TRUE; /*還沒有一方勝利*/ return FALSE; /*最佳的一步棋*/ int get_best_chess(struct CHESS_MAN *best_chess, int

16、 player, int other) int chess_value9; struct CHESS_MAN chess9; int i,j,cur=0; for(i=0;iSIZE;i+) for(j=0;jSIZE;j+) chesscur.row=i; chesscur+.col=j; for(i=0;i9;i+) if(enter_chess_man(chessi.row,chessi.col,player)=TRUE) chess_valuei=get_value(other); /*/ if(chk_winner(player)=TRUE) chess_valuei=WINNER;

17、 /*玩家未勝利，則chess_valuei為WINNER*/ chessboardchessi.rowchessi.col=NONE; /*玩家落子位置錯誤，棋盤為0*/ else chess_valuei=COMPETITOR; /* 玩家落子位置正確，*/ /*選擇值為最低的chess_value*/ cur=0; for(i=0;ichess_valuei) cur=i; /*/ best_chess-row=chesscur.row; best_chess-col=chesscur.col; return chess_valuecur; ; /*檢查是否還有未落子的棋格*/ int

18、chk_full(void) int i,j; for(i=0;iSIZE;i+) for(j=0;jSIZE;j+) if(chessboardij=NONE) return FALSE; return TRUE; ; int main(void) int i; struct CHESS_MAN best_chess; int player=PLAYER_A; /*玩家先手*/ int competitor=PLAYER_B; /*電腦后手*/ int bEND=FALSE; /*初始bEND的值*/ int row,col; /*玩家輸入所下棋子的位置*/ init_chess_board

19、(); /*初始棋盤數(shù)據(jù)*/ disp_chess_board(); /*繪制棋盤邊框*/ while(bEND=FALSE) /*若bEND為FALSE，則判定棋局結(jié)束*/ if(player=PLAYER_A) /*輪到玩家下棋時，顯示玩家坐標輸入提示*/ do printf( 請輸入您落子的位置 : n); printf( 行坐標為: ); scanf(%d,&row); printf( 列坐標為: ); scanf(%d,&col); if(enter_chess_man(row-1,col-1,player)=TRUE) /*玩家落子正確，棋盤坐標顯示，并結(jié)束該循環(huán)*/ printf

20、( 您落子的位置是 %d%dn,row,col); break; else printf( 您輸入的棋盤坐標錯誤，請重新輸入n); /*玩家落子坐標錯誤提示*/ while(TRUE); else /*電腦選擇最佳位置下棋并顯示落子的棋盤坐標提示*/ get_best_chess(&best_chess,player,competitor); enter_chess_man(best_chess.row,best_chess.col,player); printf( 電腦落子的位置是%d%dn,best_chess.row+1,best_chess.col+1); /*顯示當前棋盤落子狀況*/ disp_chess_board(); /*判斷勝負后，顯示該棋局的勝利者提示*/ bEND=TRUE; if(chk_winner(player) printf( 勝利者是Player %d.n,player); else if(chk_winner(competitor) printf( 勝利者是Player %d.n,competitor); else if(chk_full() printf( 平局.n); else bEND=FALSE; competitor=player; if(player=PLAYER_A) player=PLAY