基于极大极小分析法的井字棋对弈

基于极大极小分析法的井字棋对弈任务分析：首先，我们要知道，“井字棋”游戏（又叫“三子棋”），是一款十分经典的益智小游戏，想必很多玩家都有玩过。“井字棋”的棋盘很简单，是一个3×3的格子，很像中国文字中的“井”字，所以得名“井字棋”。“井字棋”游戏的规则与“五子棋”十分类似，“五子棋”的规则是一方首先五子连成一线就胜利；“井字棋”是一方首先三子连成一线就胜利。游戏时一方是电脑，另一方是玩家。所以，这类游戏在开始时有两种方式：一种是玩家先走；另一种是电脑先走。这是我们要考虑的第一个问题。其次，由于与玩家对战的是计算机，所以我们要编写一个过程，它可以使程序模拟人的思维与人下棋（其实就是“人工智能”的体现），这个过程也是本游戏的关键。此外，我们还要编写两个过程，其一用来时刻判断棋盘中是否有三个棋子连成一线；其二用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。如图所示为井字棋的一个格局,而格局之间的关系是由比赛规则决定的.通常,这个关系不是线性的,因为从一个棋盘格局可以派生出几个格局.例如图左侧所示的格局可以派生出5歌格局.例如图右侧所示,而从每一个新的格局又可派生出4个可能出现的格局.因此,若将从对弈开始到结束的过程中所有可能出现的格局都画在一张图上，则可以得到一颗倒长的”树”.图1对弈问题中格局之间的关系设计思路设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一只自己的棋子，谁先使自己的棋子构成“三子成一线”(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。用叉号表示MAX，用圆圈代表MIN。为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下：设棋局为P，估价函数为e(P)。(1)若P对任何一方来说都不是获胜的位置，则e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数。(2)若P是MAX必胜的棋局，则e(P)＝+∞。(3)若P是B必胜的棋局，则e(P)＝-∞。要注意利用棋盘位置的对称性,在生成后继节点的位置时，下列博弈结局都是相同的棋局(在博弈中，一宇棋的分枝系数比较小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。现在我们假设MAX走了这一步，而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层.现在图中MAX有两个可能“最好的”优先走步，假设MAX走了图上指明的那一步。而MIN为了避免立即败北被迫走了另一步，从而产生如下棋局：MAX再次搜索.在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜，因此它们的估值为—∞。当这些估值被倒推回去时，可看到MAX的最好的也是唯一能使他避免立即失败的一个走步。现在，MIN可以看出MAX必然在他的下一走步中获胜，因此，MIN只好认输。流程图设计步骤(1)选定博弈算法；(2)建立一个简单的应用程序（如字符界面程序）来测试算法；(3)选定图形界面中要实现的其他功能;(4)实现图形界面的井字棋程序。算法测试程序功能的函数：(1)可能胜利的方法：structCHESS_MAN(2)显示棋盘边框:voiddisp_chess_board(void)(3)打印棋盘函数：voidinit_chess_board(void)(4)用户输入落子位置函数:intenter_chess_man(5)判断函数:intchk_winner(intplayer)(6)评估函数值计算函数：intget_best_chess(判断哪一方获胜包含在5和6中)总程序：#includestdio.h#includemalloc.h#defineSIZE3#ifndefFALSE#defineFALSE0#endif#ifndefTRUE#defineTRUE1#endif#defineNONE0#definePLAYER_A1#definePLAYER_B2#defineWARNNING255#defineCOMPETITOR200#defineWINNER-1charchessboard[SIZE][SIZE];structCHESS_MAN{introw;intcol;};/*PLAYER可能胜利的方法*/intget_value(intplayer){inti,j,ret=0;introw,col,inc;intbNONE=FALSE;/*检查所有行*/for(i=0;iSIZE;i++){row=SIZE;bNONE=FALSE;for(j=0;jSIZE;j++){if(chessboard[i][j]==player)row--;/*如果该位置有player的棋子占据*/if(chessboard[i][j]==NONE)bNONE=TRUE;/*如果该位置还没有棋子占据，则返回bNONE为TRUE*/}if(row==1&&bNONE==TRUE)returnWARNNING;/*电脑:该行中有一个空位且有对手下的2个旗子,则可能会输掉该局，返回WARNNING值）*/elseif(row==SIZE)ret++;/*电脑:该行中没有player的棋子，ret+1*/}/*检查所有列*/for(i=0;iSIZE;i++){col=SIZE;bNONE=FALSE;for(j=0;jSIZE;j++){if(chessboard[j][i]==player)col--;/*如果该位置有player的棋子占据*/if(chessboard[j][i]==NONE)bNONE=TRUE;/*如果该位置还没有棋子占据，则返回bNONE为TRUE*/}if(col==1&&bNONE==TRUE)returnWARNNING;/*电脑:该列中有一个空位且有对手下的2个旗子,则可能会输掉该局，返回WARNNING值*/elseif(col==SIZE)ret++;/*电脑:该列中没有player的棋子，ret+1*/}/*检查左对角线*/inc=SIZE;bNONE=FALSE;for(i=0,j=0;iSIZE;i++,j++){if(chessboard[i][j]==player)inc--;/*如果该位置有player的棋子占据*/if(chessboard[i][j]==NONE)bNONE=TRUE;/*如果该位置还没有棋子占据，则返回bNONE为TRUE*/}if(inc==1&&bNONE==TRUE)returnWARNNING;/*电脑:左对角线中有一个空位且有对手下的2个旗子,可能会输掉该局，返回WARNNING值*/elseif(inc==SIZE)ret++;/*电脑:左对角线中没有player的棋子，ret+1*//*检查右对角线*/inc=SIZE;bNONE=FALSE;for(i=0,j=SIZE-1;iSIZE;i++,j--){if(chessboard[i][j]==player)inc--;/*如果该位置有player的棋子占据*/if(chessboard[i][j]==NONE)bNONE=TRUE;/*如果该位置还没有棋子占据，则返回bNONE为TRUE*/}if(inc==1&&bNONE==TRUE)returnWARNNING;/*电脑:右对角线中有一个空位且有对手下的2个旗子,可能会输掉该局，返回WARNNING值*/elseif(inc==SIZE)ret++;/*电脑:右对角线中没有player的棋子，ret+1*/returnret;};/*显示棋盘图形边框*/voiddisp_chess_board(void){inti,j;/*显示棋盘最顶层边框*/for(i=0;iSIZE*4+1;i++)printf(-);printf(\n);/*显示3层棋盘格落子情况及其左、右和下边框*/for(i=0;iSIZE;i++){printf(|);for(j=0;jSIZE;j++){if(chessboard[i][j]==PLAYER_A)printf(o|);/*如果是PLAYER_A落子则用o表示棋子*/elseif(chessboard[i][j]==PLAYER_B)printf(x|);/*如果是PLAYER_B落子则用x表示棋子*/elseprintf(|);}printf(\n);/*输出该层下边框*/for(j=0;jSIZE*4+1;j++)printf(-);printf(\n);}return;};/*棋盘初始状况*/voidinit_chess_board(void){inti,j;for(i=0;iSIZE;i++)for(j=0;jSIZE;j++)chessboard[i][j]=NONE;return;};/*玩家落子*/intenter_chess_man(introw,intcol,intplayer){if(row=SIZE||col=SIZE)returnFALSE;/*输入位置超出棋盘坐标，不能落子*/if(chessboard[row][col]!=NONE)returnFALSE;/*输入当该位置已有棋子占据，不能落子*/chessboard[row][col]=player;/*玩家落子*/returnTRUE;};/*判断胜利状况*/intchk_winner(intplayer){inti,j;intcol,row,inc;/*占满一行*/for(i=0;iSIZE;i++){row=TRUE;for(j=0;jSIZE;j++){if(chessboard[i][j]!=player)row=FALSE;}if(row==TRUE)returnTRUE;}/*占满一列*/for(i=0;iSIZE;i++){col=FALSE;for(j=0;jSIZE;j++){if(chessboard[j][i]!=player)col=FALSE;}if(col==TRUE)returnTRUE;}/*占满左对角线*/inc=TRUE;j=0;for(i=0;iSIZE;i++){if(chessboard[i][i+j]!=player)inc=FALSE;}if(inc==TRUE)returnTRUE;/*占满右对角线*/inc=TRUE;j=SIZE-1;for(i=0;iSIZE;i++){if(chessboard[i][j-i]!=player)inc=FALSE;}if(inc==TRUE)returnTRUE;/*还没有一方胜利*/returnFALSE;};/*最佳的一步棋*/intget_best_chess(structCHESS_MAN*best_chess,intplayer,intother){intchess_value[9];structCHESS_MANchess[9];inti,j,cur=0;for(i=0;iSIZE;i++){for(j=0;jSIZE;j++){chess[cur].row=i;chess[cur++].col=j;}}for(i=0;i9;i++){if(enter_chess_man(chess[i].row,chess[i].col,player)==TRUE){chess_value[i]=get_value(other);/**/if(chk_winner(player)==TRUE)chess_value[i]=WINNER;/*玩家未胜利，则chess_value[i]为WINNER*/chessboard[chess[i].row][chess[i].col]=NONE;/*玩家落子位置错误，棋盘为0*/}elsechess_value[i]=COMPETITOR;/*玩家落子位置正确，*/}/*选择值为最低的chess_value*/cur=0;for(i=0