黑白棋程序设计实验报告C++版.doc

海南大学课程论文课程名称： 数据结构课程设计 题目名称： 黑白棋 学 院： 信息学院 专业班级： 姓名： 学号： 评阅意见评阅成绩 评阅教师： 2011年 12月 17 日目 录一、 黑白棋简介2二、程序设计思路及实现界面图3三、程序设计算法性能分析6四、实验总结6五、实验代码7一、 黑白棋简介黑白棋，又叫反棋(Reversi)、奥赛罗棋(Othello)，苹果棋，翻转棋。黑白棋的棋子和围棋类似。但它的下法与围棋的很不相同。黑白棋是由黑方和白方两人进行的益智游戏。棋盘为NN方格，黑白棋总共使用N2个棋子，每个棋子分正反两面，分别是黑色和白色。轮到一方下棋时，必须把棋下在与对方棋子相邻的空位上，要求所下的棋子和原有的已方棋子夹住对方的至少一个棋子(横竖斜夹均可)，然后把被夹住的子变成己方的颜色(也叫吃子)。下棋过程中，任何棋子既不会从棋盘上拿走，也不会从一个格子移到另一个格子,吃子时，不会发生连锁反应，吃进的棋子不能再夹吃其他的子。当双方都无棋可下，或者方格全部占满后，棋局结束，子多的一方为胜方。二、程序设计思路及游戏实现界面1、设计初始化棋盘函数2、复制棋盘函数3、显示棋盘函数4、选择下棋类型4、计算可落子的位置个数,及该位置落子后翻过的棋子的个数5、设置棋子的稳定性(计算得分的依据)，空白处除外6、评价棋手得分游戏开始选择类型和棋子：打印棋盘棋手开始下棋输入下棋的位置：游戏结束，统计棋数并分出胜负：一局结束后选择是否继续：三、性能分析人机对战中稳定性算法用了8层循环，所以程序的性能为O（N8）级别四、实验总结这个程序主要用来实现黑白棋的人人对战，程序中的人机对战的算法主要参考别的程序，而人人对战则相对简单所以以自己的能力就只实现了其中的人人对战部分，由于没有自学MFC，所以界面不是很友好，直接在doc环境下运行，但程序总的实现了黑白棋的基本功能，能够在doc下显示棋盘，判断棋手可下棋位置及最后判断出胜负。五、程序代码：#include using namespace std;int const MAX=10000;enum Color WHITE=-1,BLANK,BLACK/是否能落子 /黑子;class Choicepublic: int posX; int posY; int score;class Chessmanpublic: enum Color color; unsigned stable;/* 棋子的稳定性(08),若棋子为BLANK则表示该位置落子后可翻过的棋子个数. */;/即下此位置后对方的棋变为自己的棋子的数目class Chessboard/棋盘public:Chessman cell88;/定义棋盘中有8*8个格子 unsigned whiteNum;/白棋数目 unsigned blackNum;/黑棋数void initChessboard(Chessboard *board);void clone( Chessboard *boardDest,const Chessboard *boardSource);void view( Chessboard *board);int judge( Chessboard *board,enum Color player);int putChess( Chessboard *board,Choice *choice,enum Color player);void setStable( Chessboard *board);int evaluate(Chessboard *board,enum Color player);void Chessboard:initChessboard(Chessboard *board)/初始化棋盘/声明一个Chessboard结构体boardint i,j;board-whiteNum=2;board-blackNum=2;for(i=0;i8;i+)for(j=0;jcellij.color=BLANK;board-cellij.stable=0;board-cell33.color=board-cell44.color=BLACK;board-cell34.color=board-cell43.color=WHITE;/ 复制棋盘.void Chessboard:clone( Chessboard *boardDest,const Chessboard *boardSource) int i,j; boardDest-whiteNum=boardSource-whiteNum; boardDest-blackNum=boardSource-blackNum; for(i=0;i8;i+)for(j=0;jcellij.color=boardSource-cellij.color;boardDest-cellij.stable=boardSource-cellij.stable; /显示棋盘.void Chessboard:view( Chessboard *board) int i,j; coutn-;for(i=0;i8;i+)cout-i+1;coutn n;for(i=0;i8;i+)couti+1-;for(j=0;jcellij.color)case BLACK:cout;break;case WHITE:coutcellij.stable)cout +;elsecout ;break;default: /* 棋子颜色错误 */ cout* ;coutn n;cout白棋()个数为:whiteNum ;cout黑棋()个数为:blackNumendlendlcellij.stable) int Chessboard:judge( Chessboard *board,enum Color player) int i,j; unsigned num=0; for(i=0;i8;i+)for(j=0;jcellij.color=BLANK)int x,y;board-cellij.stable=0;for(x=-1;x=1;x+)for(y=-1;y=0 & i2=0 & j2celli2j2.color=(enum Color)-player)num2+;else if(board-celli2j2.color=player)board-cellij.stable+=player*num2;break;else if(board-celli2j2.color=BLANK)break;if(board-cellij.stable)num+;return num;/落子,翻子.int Chessboard:putChess( Chessboard *board,Choice *choice,enum Color player) int i=choice-posX,j=choice-posY; int x,y; if(board-cellij.color!=BLANK | board-cellij.stable=0 | player=BLANK) return -1; board-cellij.color=player; board-cellij.stable=0; if(player=WHITE) board-whiteNum+; else if(player=BLACK) board-blackNum+; for(x=-1;x=1;x+) for(y=-1;y=0 & i2=0 & j2celli2j2.color=(enum Color)-player)num+;else if(board-celli2j2.color=player)board-whiteNum+=(player*WHITE)*num;board-blackNum+=(player*BLACK)*num; for(i2-=x,j2-=y;num0;num-,i2-=x,j2-=y) board-celli2j2.color=player; board-celli2j2.stable=0; break;else if(board-celli2j2.color=BLANK)break; return 0;/* * 设置棋子的稳定性(计算得分的依据)，空白处除外. */void Chessboard:setStable( Chessboard *board) int i,j; for(i=0;i8;i+) for(j=0;jcellij.color!=BLANK) int x,y; board-cellij.stable=1; for(x=-1;x=1;x+) for(y=-1;y=0 & i2=0 & j2celli2j2.color!=board-cellij.color) flag-; break; for(i2=i-x,j2=j-y;i2=0 & i2=0 & j2celli2j2.color!=board-cellij.color) flag-; break; if(flag) /* 在某一条线上稳定 */ board-cellij.stable+; /* * 评价棋手得分. */int Chessboard:evaluate(Chessboard *board,enum Color player) int value=0; int i,j; setStable(board); for(i=0;i8;i+) for(j=0;jcellij.color)*(board-cellij.stable); value+=64*board-cell00.color; value+=64*board-cell07.color; value+=64*board-cell70.color; value+=64*board-cell77.color; value-=32*board-cell11.color; value-=32*board-cell16.color; value-=32*board-cell61.color; value-=32*board-cell66.color; return value*player; /考虑step步，选择最优方案.采用最大最小博弈和-剪裁算法 Choice * maximin( Chessboard *board,enum Color player,int step,int min,int max, Choice *choice) int i,j,k,num; Choice *allChoices; choice-score=-MAX; choice-posX=-1; choice-posY=-1; num=board-judge(board,player); if(num=0) /* 无处落子 */ if(board-judge(board,(enum Color)-player) /* 对方可以落子,让对方下.*/ Chessboard tempBoard; Choice nextChoice; Choice *pNextChoice=&nextChoice;board-clone(&tempBoard,board); pNextChoice=maximin(&tempBoard,(enum Color)-player,step-1,-max,-min,pNextChoice); choice-score=-pNextChoice-score; choice-posX=-1; choice-posY=-1; return choice; else /* 对方也无处落子,游戏结束. */ int value=WHITE*(board-whiteNum) + BLACK*(board-blackNum); if(player*value0) choice-score=MAX-1; else if(player*valuescore=-MAX+1; else choice-score=0; return choice; if(stepscore=board-evaluate(board,player); return choice; allChoices=( Choice *)malloc(sizeof( Choice)*num); k=0; for(i=0;i8;i+) for(j=0;jcellij.color=BLANK & board-cellij.stable) allChoicesk.score=-MAX; allChoicesk.posX=i; allChoicesk.posY=j; k+; for(i=0;i8;i+) for(j=0;j=2 & i=2 & jcellij.color=BLANK & board-cellij.stable) allChoicesk.score=-MAX; allChoicesk.posX=i; allChoicesk.posY=j; k+; for(i=0;i8;i+) for(j=0;j=1 & i=1 & jcellij.color=BLANK & board-cellij.stable) allChoicesk.score=-MAX; allChoicesk.posX=i; allChoicesk.posY=j; k+; for(k=0;kclone(&tempBoard,board); board-putChess(&tempBoard,&thisChoice,player); pNextChoice=maximin(&tempBoard,(enum Color)-player,step-1,-max,-min,pNextChoice); thisChoice.score=-pNextChoice-score; if(thisChoice.scoremin & thisChoice.scorescore=thisChoice.score; choice-posX=thisChoice.posX; choice-posY=thisChoice.posY; else if(thisChoice.score=max) /* 好的超乎预计 */ choice-score=thisChoice.score; choice-posX=thisChoice.posX; choice-posY=thisChoice.posY; break; /* 不如已知最优值 */ free(allChoices); return choice;int main(void)/主函数 Chessboard board; Chessboard *pBoard=&board; enum Color player=BLANK,nowPlayer=BLACK;/声明两个enum枚举变量player，nowplayer Choice choice; Choice *pChoice=&choice; int dif=-1,step=4,success=0; char restart= ; start:/ player=BLANK;/ nowPlayer=BLACK; dif=-1; step=4; restart= ; int b; coutb; if(b=1)/人人对战/while(player!=WHITE & player!=BLACK)coutn请选择执黑棋()(1),或执白棋()(-1)t执黑棋先下:n;scanf(%d,&player);/if(player!=WHITE & player!=BLACK)cout黑白设置错误.n;board.initChessboard(pBoard);/初始化棋盘/ while(step64) /* 棋盘上未下满64子 */char *nowPlayerName=;if(nowPlayer=BLACK)nowPlayerName=黑棋();else if(nowPlayer=WHITE)nowPlayerName=白棋();if(board.judge(pBoard,nowPlayer)=0)if(board.judge(pBoard,(enum Color)-nowPlayer)=0)break; /* 双方都不能落子,游戏结束 */coutnowPlayerNamen无子可下.n;elseint i,j; board.view(pBoard); if(nowPlayer=player) /* 轮到人下 */while(1)coutnowPlayerName请输入棋子坐标(i,j):n;couti;i-;coutj;j-; pChoice-posX=i;pChoice-posY=j; if(i7 | j7 | pBoard-cellij.color!=BLANK | pBoard-cellij.stable=0)coutnowPlayerName不能在i+1,j+1落子.;board.view(pBoard);elsebreak;else/另外一个人下while(1)coutnowPlayerName请输入棋子坐标(i,j):n;couti;i-;coutj;j-; pChoice-posX=i;pChoice-posY=j; if(i7 | j7 | pBoard-cellij.color!=BLANK | pBoard-cellij.stable=0)coutnowPlayerName不能在i+1,j+1落子.;board.view(pBoard);elsebreak; board.putChess(pBoard,pChoice,nowPlayer);step+;coutnowPlayerName落子于坐标i+1,whiteNum - pBoard-blackNum; if(success0)coutn白棋()获胜.n;else if(success0)coutn黑棋()获胜.n;elsecoutn平局.n; coutn游戏结束!n;while(restart!=y & restart!=n)coutrestart;/if(restart=y)goto start;else /人机对战/while(dif60) /设置难度coutdif;if(dif60)cout难度设置错误.n;while(player!=WHITE & player!=BLACK)cout请选择执黑棋()(1),或执白棋()(-1)endl;cout执黑先行:;scanf(%d,&player);if(player!=WHITE & player!=BLACK)cout黑白设置错误.n;board.initChessboard(pBoard);/初始