基于極大極小分析法的井字棋對(duì)弈

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

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

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

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

5、然在他的下一走步中獲勝，因此，MIN只好認(rèn)輸。流程圖設(shè)計(jì)步驟(1) 選定博弈算法； (2) 建立一個(gè)簡(jiǎn)單的應(yīng)用程序（如字符界面程序）來(lái)測(cè)試算法； (3) 選定圖形界面中要實(shí)現(xiàn)的其他功能; (4) 實(shí)現(xiàn)圖形界面的井字棋程序。算法測(cè)試程序功能的函數(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)評(píng)估函數(shù)值計(jì)算函數(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; /*如果該位置還沒(méi)有棋子占據(jù)，則返回bNONE為TRUE*/ if(row=1&bNONE=TRUE) return WARNNING; /*電腦:該行中有一個(gè)空位且有對(duì)手下的2個(gè)旗子,則可能會(huì)輸?shù)粼摼?，返回WARNNING值）*/ else if(row=SIZE) ret+; /*電腦:該行中沒(méi)有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; /*如果該位置還沒(méi)有棋子占據(jù)，則返回bNONE為TRUE*/ if(col=1&bNONE=TRUE) return WARNNING; /*電腦:該列中有一個(gè)空位且有對(duì)手下的2個(gè)旗子,則可能會(huì)輸?shù)粼摼?，返回WARNNING值*/ else if(col=SIZE) ret+; /*電腦:該列中沒(méi)有player的棋子，ret+1*/ /*檢查左對(duì)角線*/ inc=SIZE; bNONE=FALSE; for(i=0,j=0;iSIZE;i+,j+) if(chessboardij=player) inc-; /*如果該位置有player的

10、棋子占據(jù)*/ if(chessboardij=NONE) bNONE=TRUE; /*如果該位置還沒(méi)有棋子占據(jù)，則返回bNONE為TRUE*/ if(inc=1&bNONE=TRUE) return WARNNING; /*電腦:左對(duì)角線中有一個(gè)空位且有對(duì)手下的2個(gè)旗子,可能會(huì)輸?shù)粼摼?，返回WARNNING值*/ else if(inc=SIZE) ret+; /*電腦:左對(duì)角線中沒(méi)有player的棋子，ret+1*/*檢查右對(duì)角線*/ 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; /*如果該位置還沒(méi)有棋子占據(jù)，則返回bNONE為TRUE*/ if(inc=1&bNONE=TRUE) return WARNNING; /*電腦:右對(duì)角線中有一個(gè)空位且有對(duì)手下的2個(gè)旗子,可能會(huì)輸?shù)粼摼?，返回WARNNING值*/ else if(inc=SIZE) ret+; /*電腦:右對(duì)角線中沒(méi)有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; /*輸入位置超出棋盤坐標(biāo)，不能落子*/ if(chessboardrowcol!=NONE) return FALSE; /*輸入當(dāng)該位置已有棋子占據(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; /*占滿左對(duì)角線*/

15、 inc=TRUE; j=0; for(i=0;iSIZE;i+) if(chessboardii+j!=player) inc=FALSE; if(inc=TRUE) return TRUE; /*占滿右對(duì)角線*/ inc=TRUE; j=SIZE-1; for(i=0;iSIZE;i+) if(chessboardij-i!=player) inc=FALSE; if(inc=TRUE) return TRUE; /*還沒(méi)有一方勝利*/ 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; /*玩家落子位置錯(cuò)誤，棋盤為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) /*輪到玩家下棋時(shí)，顯示玩家坐標(biāo)輸入提示*/ do printf( 請(qǐng)輸入您落子的位置 : n); printf( 行坐標(biāo)為: ); scanf(%d,&row); printf( 列坐標(biāo)為: ); scanf(%d,&col); if(enter_chess_man(row-1,col-1,player)=TRUE) /*玩家落子正確，棋盤坐標(biāo)顯示，并結(jié)束該循環(huán)*/ printf

20、( 您落子的位置是 %d%dn,row,col); break; else printf( 您輸入的棋盤坐標(biāo)錯(cuò)誤，請(qǐng)重新輸入n); /*玩家落子坐標(biāo)錯(cuò)誤提示*/ while(TRUE); else /*電腦選擇最佳位置下棋并顯示落子的棋盤坐標(biāo)提示*/ 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); /*顯示當(dāng)前棋盤落子狀況*/ disp_chess_board(); /*判斷勝負(fù)后，顯示該棋局的勝利者提示*/ 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