基于某极大极小分析报告法地井字棋对弈

《基于某极大极小分析报告法地井字棋对弈》由会员分享，可在线阅读，更多相关《基于某极大极小分析报告法地井字棋对弈（11页珍藏版）》请在装配图网上搜索。

1、word基于极大极小分析法的井字棋对弈任务分析：首先，我们要知道，“井字棋游戏又叫“三子棋，是一款十分经典的益智小游戏，想必很多玩家都有玩过。“井字棋的棋盘很简单，是一个33的格子，很像中国文字中的“井字，所以得名“井字棋。“井字棋游戏的规如此与“五子棋十分类似，“五子棋的规如此是一方首先五子连成一线就胜利；“井字棋是一方首先三子连成一线就胜利。 游戏时一方是电脑，另一方是玩家。所以，这类游戏在开始时有两种方式：一种是玩家先走；另一种是电脑先走。这是我们要考虑的第一个问题。 其次，由于与玩家对战的是计算机，所以我们要编写一个过程，它可以使程序模拟人的思维与人下棋其实就是“人工智能的表现，这个过

2、程也是本游戏的关键。此外，我们还要编写两个过程，其一用来时刻判断棋盘中是否有三个棋子连成一线；其二用来判断如果有三个棋子连成一线，是哪一方连成一线的，即判断哪一方获胜。如下列图为井字棋的一个格局,而格局之间的关系是由比赛规如此决定的.通常,这个关系不是线性的,因为从一个棋盘格局可以派生出几个格局.例如图左侧所示的格局可以派生出5歌格局.例如图右侧所示,而从每一个新的格局又可派生出4个可能出现的格局.因此,假如将从对弈开始到完毕的过程中所有可能出现的格局都画在一图上，如此可以得到一颗倒长的树.图1 对弈问题中格局之间的关系设计思路设有九个空格，由MAX，MIN二人对弈，轮到谁走棋谁就往空格上放一

3、只自己的棋子，谁先使自己的棋子构成“三子成一线(同一行或列或对角线全是某人的棋子)，谁就取得了胜利。 用叉号表示MAX，用圆圈代表MIN。 为了不致于生成太大的博弈树，假设每次仅扩展两层。估价函数定义如下： 设棋局为P，估价函数为e(P)。(1) 假如P对任何一方来说都不是获胜的位置，如此e(P)=e(那些仍为MAX空着的完全的行、列或对角线的总数)-e(那些仍为MIN空着的完全的行、列或对角线的总数。(2) 假如P是MAX必胜的棋局，如此e(P)+。 (3) 假如P是B必胜的棋局，如此e(P)-。要注意利用棋盘位置的对称性,在生成后继节点的位置时，如下博弈结局都是一样的棋局(在博弈中，一宇棋

4、的分枝系数比拟小起初是由于对称性，而后是由于棋盘上未布子的空格减少所致)。 现在我们假设MAX走了这一步，而MIN的回步是直接在X上方的空格里放上一个圆圈(对MAX来说这是一步坏棋，他一定没有采用好的搜索策略)。下一步，MAX又在新的格局下搜索两层. 现在图中MAX有两个可能“最好的优先走步，假设MAX走了图上指明的那一步。而MIN为了防止立即败北被迫走了另一步，从而产生如下棋局：MAX再次搜索. 在这棵树中某些端节点(例如其中一个标记着A)代表MIN获胜，因此它们的估值为。当这些估值被倒推回去时，可看到MAX的最好的也是唯一能使他防止立即失败的一个走步。现在，MIN可以看出MAX必然在他的下

5、一走步中获胜，因此，MIN只好认输。流程图设计步骤(1) 选定博弈算法； (2) 建立一个简单的应用程序如字符界面程序来测试算法； (3) 选定图形界面中要实现的其他功能; (4) 实现图形界面的井字棋程序。算法测试程序功能的函数：(1) 可能胜利的方法： struct CHESS_MAN(2)显示棋盘边框: void disp_chess_board(void) (3) 打印棋盘函数： void init_chess_board(void) (4) 用户输入落子位置函数: int enter_chess_man (5) 判断函数: int chk_winner(int player) (6)

6、评估函数值计算函数： 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 PETITOR 200 #define WINNER -1 char chessboardS

7、IZESIZE; 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的棋子占据*/ if(chessboardij=NONE) bNONE=TRUE; /*如果该位

8、置还没有棋子占据，如此返回bNONE为TRUE*/ if(row=1&bNONE=TRUE) return WARNNING; /*电脑:该行中有一个空位且有对手下的2个旗子,如此可能会输掉该局，返回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的棋子占据*/ if(chessboardji

9、=NONE) bNONE=TRUE; /*如果该位置还没有棋子占据，如此返回bNONE为TRUE*/ if(col=1&bNONE=TRUE) return WARNNING; /*电脑:该列中有一个空位且有对手下的2个旗子,如此可能会输掉该局，返回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、if(chessboardij=NONE) bNONE=TRUE; /*如果该位置还没有棋子占据，如此返回bNONE为TRUE*/ if(inc=1&bNONE=TRUE) return WARNNING; /*电脑:左对角线中有一个空位且有对手下的2个旗子,可能会输掉该局，返回WARNNING值*/ else if(inc=SIZE) ret+; /*电脑:左对角线中没有player的棋子，ret+1*/*检查右对角线*/ inc=SIZE; bNONE=FALSE; for(i=0,j=SIZE-1;iSIZE;i+,j-) if(chessboardij=player) inc-; /*

11、如果该位置有player的棋子占据*/ if(chessboardij=NONE) bNONE=TRUE; /*如果该位置还没有棋子占据，如此返回bNONE为TRUE*/ if(inc=1&bNONE=TRUE) return WARNNING; /*电脑:右对角线中有一个空位且有对手下的2个旗子,可能会输掉该局，返回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); /*输出该层下边框*/ for

13、(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; /*输入当该位置已有棋子占据，不能落子*/ chessboardrowcol=player; /*玩家落子*/ return TRUE; ; /*判断胜利状况*/ i

14、nt 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; /*占满左对角线*/ in

15、c=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 pl

16、ayer, 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=PETITOR; /* 玩家落子位置正确，*/ /*选择值为最低的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 chk_f

18、ull(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 petitor=PLAYER_B; /*电脑后手*/ int bEND=FALSE; /*初始bEND的值*/ int row,col; /*玩家输入所下棋子的位置*/ init_chess_board(); /*初始

19、棋盘数据*/ disp_chess_board(); /*绘制棋盘边框*/ while(bEND=FALSE) /*假如bEND为FALSE，如此判定棋局完毕*/ 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) /*玩家落子正确，棋盘坐标显示，并完毕该循环*/ printf( 您落子的

20、位置是 %d%dn,row,col); break; else printf( 您输入的棋盘坐标错误，请重新输入n); /*玩家落子坐标错误提示*/ while(TRUE); else /*电脑选择最优位置下棋并显示落子的棋盘坐标提示*/ get_best_chess(&best_chess,player,petitor); enter_chess_man(best_chess.row,best_chess.col,player); printf( 电脑落子的位置是%d%dn,best_chess.row+1,best_chess.col+1); /*显示当前棋盘落子状况*/ disp_che

21、ss_board(); /*判断胜负后，显示该棋局的胜利者提示*/ bEND=TRUE; if(chk_winner(player) printf( 胜利者是Player %d.n,player); else if(chk_winner(petitor) printf( 胜利者是Player %d.n,petitor); else if(chk_full() printf( 平局.n); else bEND=FALSE; petitor=player; if(player=PLAYER_A) player=PLAYER_B; else player=PLAYER_A; ; printf(nn本

22、棋局完毕.nn); /*该局已完毕*/ return 0; ; 运行结果示例总结：在本程序中的井字棋程序使用了极大极小值算法，这种算法的思想是“考虑双方对弈假如干步之后，从可能的走法中选一步相对较好的走法来走，并且“在有限的搜索深度围进展求解。最大最小值算法的核心是将搜索树的层分为MAX层和MIN层，MAX层和MIN层交替相邻即，一个节点如果在MAX层，如此其子女节点在MIN层；如果在MIN层，如此其子女节点中的最大者，在MIN层的节点的评估函数值取其子女节点中的最小者。 此外，需要定义一个评估函数来计算叶节点的评估函数值，要注意将某方获胜的状态节点的评估函数值设为计算机能表示的最大数无穷大或

23、最小数无穷小以明确在该状态下有一方获胜。 最后，还要“在有限的搜索深度围进展求解，如果搜索深度太大，如此在状态数较多的情况下会使时间消耗或空间消耗达到无法忍受的程度。改良建议1本程序中的程序的博弈算法采用的是极大极小值算法，如果采用-剪枝算法，如此可以在一定程度上减少博弈树的节点数。假设一棵树的深度为d，且每个非叶节点的分支系数为b，如此在最优情况下，-剪枝算法生成深度为d的叶节点数大约相当于极大极小值算法所生成的深度为d/2的博弈树的节点数。也就是说，为了得到最优的一步，-剪枝算法只需要检测O(bd/2 )个节点，而不是极大极小值算法的O(bd )。从另一个角度看，在一样的代价下，-剪枝算法向前看走的步数是极大极小值算法向前看走的步数的两倍 2函数并不完美,有些时候会导致电脑下一些笨棋. 11 / 11