第24次比赛第2题之测试程序: -- 业余空间-- 编程爱好者博客

第2题之测试程序:/* Name: Tic-Tac-Toe Copyright: original Author: goal00001111 Date: 12-04-06 10:25 Description: tic-tac-toe 是在3*3的棋盘上进行对弈的游戏。两个玩家在方格上轮流放置自己的棋子。谁先获得行，列或对角线上的连续3个方格，谁就获胜。请编写一个程序与其他程序进行tic-tac-toe比赛。我创建了一个棋盘，供两位选手对弈。选手根据我提供的当前棋盘布局情况，选择合适的棋子落点。注意：棋子要下在适当的空白处，若落子在已有棋子的地方或超出棋盘界限，判负。函数接口：void ChooseMove(const int board[][3], int & row, int & column); 输入：当前棋盘布局board[][3]，棋盘上某点的行号row和列号column,行号和列号均从0开始. 输出：棋子落点的坐标 row, column 当前棋盘布局board[][3]，空为0, 我方为1, 敌方为2.我会在测试程序中对棋盘布局board[][3]进行实时变更,使得面对每一个选手程序均为:空为0, 我方为1, 敌方为2. 评分方法：每一轮比赛由2个程序进行3局对弈，前两局分先，第3局猜先。每局对弈打平各得1分，胜利者得2分，失败者不得分。比赛按提交楼层顺序，每3个程序为一组（每人最多提交2个程序，如果超过2个则只取最后修改的2个程序）。每组进行循环赛，即组内任意2个程序进行一轮比赛。分组剩余的程序如果为1个则自动晋级。如果为2个则2个程序作为一组进行比赛。第一次循环赛结束后，每组得分最高的程序晋级，其他程序被淘汰。如果组内最高分相同，则一起晋级。对所有晋级程序按顺序进行第二次分组，淘汰的程序不继续参与比赛。重复直到最终剩余一个程序或者不再有人被淘汰为止。*/#include<cassert>#include<iostream>using namespace std;enum Side { EMPTY, PLAYER1, PLAYER2 };enum PositionVal { PLAYER1_WIN, DRAW, UNCLEAR, PLAYER2_WIN };int PlayGame( int player1, int player2 );void GetBoard(int board[][3]);void ClearBoard( int board[][3] );bool BoardIsFull( const int board[][3] );bool PlayMove( int board[][3], int player, int row, int column );bool IsAWin( const int board[][3], int player );void PrintBoard(const int board[][3]);void ChooseMove_1(const int board[][3], int & row, int & column);void ChooseMove_2(const int board[][3], int & row, int & column);void ChooseMove_3(const int board[][3], int & row, int & column);int ChooseMove(int board[][3], Side s, int & bestRow, int & bestColumn);void Place( int board[][3], int row, int column, int piece );bool SquareIsEmpty( const int board[][3], int row, int column );int PositionValue( const int board[][3]);////////////////////////////作者：eastcowboy///////////////////////////////////////////////// 测试环境Visual Stuidio 2005// 语言：C++// 考虑下子的顺序// 1、如果我方下一步能胜利，则胜利// 2、如果对手下一步能胜利，则试图阻止// 3、占据当前条件下最重要的位置 // 最重要的位置定义为：已经被占据的位置都不是当前重要位置。 // 在此前提下按以下标准评分，分最高的就是最重要的 // a、如果我方可通过此位置获得胜利，得一分。（有多种途径可得多分） // b、如果对手可通过此位置获得胜利，也得一分。（有多种途径可得多分）static inline bool WillWin( const int board[][3], const int WinLine[3][2], int &row, int &column ){ int i; int n0 = 0; int n1 = 0; for(i=0; i<3; ++i) { int x = WinLine[i][0]; int y = WinLine[i][1]; if( board[x][y] == 0 ) ++n0, row=x, column=y; else if( board[x][y] == 1 ) ++n1; } return ((n0==1) && (n1==2));}static inline bool WillLose( const int board[][3], const int WinLine[3][2], int &row, int &column ){ int i; int n0 = 0; int n1 = 0; for(i=0; i<3; ++i) { int x = WinLine[i][0]; int y = WinLine[i][1]; if( board[x][y] == 0 ) ++n0, row=x, column=y; else if( board[x][y] == 2 ) ++n1; } return ((n0==1) && (n1==2));}static inline bool PointInLine(const int WinLine[3][2], const int row, const int column){ register int i; for(i=0; i<3; ++i) if(WinLine[i][0]==row && WinLine[i][1]==column) return true; return false;}static inline bool CanWin( const int board[][3], const int WinLine[3][2] ){ int i; for(i=0; i<3; ++i) { int x = WinLine[i][0]; int y = WinLine[i][1]; if( board[x][y] == 2 ) return false; } return true;}static inline bool CanLose( const int board[][3], const int WinLine[3][2] ){ int i; for(i=0; i<3; ++i) { int x = WinLine[i][0]; int y = WinLine[i][1]; if( board[x][y] == 1 ) return false; } return true;}void ChooseMove_2(const int board[][3], int &row, int &column){ static int WinLine[8][3][2] = { 0,0,0,1,0,2, // 第一行 1,0,1,1,1,2, // 第二行 2,0,2,1,2,2, // 第三行 0,0,1,0,2,0, // 第一列 0,1,1,1,2,1, // 第二列 0,2,1,2,2,2, // 第三列 0,0,1,1,2,2, // 左上到右下方向 0,2,1,1,2,0 // 右下到左上方向 }; int i; // 1、如果我方下一步能胜利，则胜利 for(i=0; i<8; ++i) if( WillWin(board, WinLine[i], row, column) ) { assert( board[row][column] == 0 ); return; } // 2、如果对手下一步能胜利，则试图阻止 for(i=0; i<8; ++i) if( WillLose(board, WinLine[i], row, column) ) { assert( board[row][column] == 0 ); return; } // 3、占据当前条件下最重要的位置 int Importance[3][3] = {0}; int r,c; int maxImportance = -1; for(r=0; r<3; ++r) for(c=0; c<3; ++c) { if( board[r][c] != 0 ) { Importance[r][c] = -2; continue; } for(i=0; i<8; ++i) if( PointInLine(WinLine[i], r, c) ) { if( CanWin(board, WinLine[i]) ) ++(Importance[r][c]); if( CanLose(board, WinLine[i]) ) ++(Importance[r][c]); } if( Importance[r][c] > maxImportance ) maxImportance = Importance[r][c]; } for(r=0; r<3; ++r) for(c=0; c<3; ++c) if( Importance[r][c] == maxImportance ) { row = r; column = c; return; }}///////////////////////////////////////////////////////////////////////////////////////////////////////////////作者：yxs0001////////////////////////////////////////////////////struct Point{ int row; int column;};struct LINE{ int points;//点数 bool pass;//是否可能在该线获胜 //构造函数 LINE(){ points = 0; pass = true; }};struct PLAYER{ LINE H_Line[3];//横线 LINE C_Line[3];//竖线 LINE D_Line[2];//斜线// int ps;//本方点数};class CChess{private : int bps;//空点数 Point BlackPoint[9];//空点 PLAYER I,you;public : //构造函数 CChess(const int board[][3]); //点的分值 int ScorePoint(Point p); int ScoreCheck(Point p,LINE line,int player); //下的位置 void FallPoint(int & row, int & column); //初始化(row,column) void InitPoint(const int row,const int column,const int player);};void CChess::InitPoint(const int row,const int column,const int player){ PLAYER *p1,*p2; if(player == 2){ p1 = &you; p2 = &I; } else{ p1 = &I; p2 = &you; }// p1->ps ++; //横线 p1->H_Line[row].points++; p2->H_Line[row].pass = false; //竖线 p1->C_Line[column].points++; p2->C_Line[column].pass = false; //斜线 if(row == column){ p1->D_Line[0].points++; p2->D_Line[0].pass = false; } if(row + column == 2){ p1->D_Line[1].points++; p2->D_Line[1].pass = false; }}CChess::CChess(const int board[][3]){ int i,j; bps = 0;// I.ps =0;// you.ps = 0; for(i=0;i<3;i++) for(j=0;j<3;j++) { if(board[i][j]) InitPoint(i,j,board[i][j]); else{//空点 BlackPoint[bps].row = i; BlackPoint[bps].column = j; bps++; } }}int CChess::ScoreCheck(Point p,LINE line,int player){ int score = 0; int score1,score2; if(player == 1){ score1 = 125; score2 = 1000; } else{ score1 = 100; score2 = 500; } if(line.pass){ switch (line.points){ case 0: break; case 1: score += score1; break; case 2: score += score2;//胜点 } } return score;}int CChess::ScorePoint(Point p){ int score = 0; LINE line; if(p.column == p.row ){//斜线1 score ++; //己方 line = I.D_Line[0]; score += ScoreCheck(p,line,1); //对方 line = you.D_Line[0]; score += ScoreCheck(p,line,2); } if(p.row + p.column == 2){//斜线2 score ++; //己方 line = I.D_Line[1]; score += ScoreCheck(p,line,1); //对方 line = you.D_Line[1]; score += ScoreCheck(p,line,2); } //横线 //己方 line = I.H_Line[p.row]; score += ScoreCheck(p,line,1); //对方 line = you.H_Line[p.row]; score += ScoreCheck(p,line,2); //竖线 //己方 line = I.C_Line[p.column]; score += ScoreCheck(p,line,1); //对方 line = you.C_Line[p.column]; score += ScoreCheck(p,line,2); return score;}void CChess::FallPoint(int & row,int & column){ int max = -1; int score;// Point p; for(int i=0;i<bps;i++){ score = ScorePoint(BlackPoint[i]); if(score>max){ max = score; row = BlackPoint[i].row; column = BlackPoint[i].column; } if (max>=1000) return; }}void ChooseMove_1(const int board[][3], int & row, int & column){ CChess cchess(board); cchess.FallPoint(row,column);}//////////////////////////////////////////////////////////////////////////////////int main( ){ cout << "Welcome to TIC-TAC-TOE" << endl; const int N = 4; int score[N] = {0}; int winer; for (int i=1; i<N-1; i++) for (int j=i+1; j<N; j++) { winer = PlayGame( i, j ); if (winer == 0) { cout << "DRAW!\n"; score[i]++; score[j]++; } else { cout << winer << "WIN!\n"; score[winer] += 2; } } for (int i=1; i<N; i++) cout << i << ":" << score[i] << endl; getchar(); return 0;}int PlayGame( int player1, int player2 ){ int board[3][3]; int bestRow, bestColumn; int player = 1;//每一个选手程序的棋子值均为1 ClearBoard(board); while( !BoardIsFull(board) ) { //对棋盘布局board[][3]进行实时变更,使得面对每一个选手程序均为:空为0, 我方为1, 敌方为2 GetBoard(board); //创建空棋盘 if (player1 == 1) ChooseMove_1( board, bestRow, bestColumn); else if (player1 == 2) ChooseMove_2( board, bestRow, bestColumn); if (!PlayMove(board, player, bestRow, bestColumn)) return player2; if (IsAWin(board, player1)) return player1; if ( !BoardIsFull(board) )//如果棋盘未满 { GetBoard(board); if (player2 == 2) ChooseMove_2( board, bestRow, bestColumn); else if (player2 == 3) ChooseMove_3( board, bestRow, bestColumn); if (!PlayMove(board, player, bestRow, bestColumn)) return player1; if (IsAWin(board, player2)) return player2; } } return 0;}/*函数介绍：对棋盘布局board[][3]进行实时变更,使得面对每一个选手程序均为:空为0, 我方为1, 敌方为2 即若把原来为1的子变成2，原来为2的子变成1输入：当前棋局落子分布board[][3]输出：更新后的棋局落子分布board[][3]*/void GetBoard(int board[][3]){ for( int i = 0; i < 3; i++ ) for( int j = 0; j < 3; j++ ) { if (board[i][j] == 1) board[i][j] = 2; else if (board[i][j] == 2) board[i][j] = 1; }}/////////////////作者：goal00001111////////////////////////////////////// Routine to compute optimal tic-tac-toe move./*函数介绍：根据当前棋局落子分布，采用回溯算法，确定最佳着点输入：当前棋局落子分布board[][3]，最佳着点的坐标 bestRow, bestColumn输出：最佳着点的坐标 bestRow, bestColumn*/void ChooseMove_3(const int board[][3], int & row, int & column){ int c_board[3][3]; for( int i = 0; i < 3; i++ ) for( int j = 0; j < 3; j++ ) c_board[i][j] = board[i][j]; PrintBoard(board); ChooseMove( c_board, PLAYER1, row, column);}/*函数介绍：根据当前棋局落子分布，采用回溯算法，确定最佳着点输入：当前棋局落子分布board[][3]，当前选手s，最佳着点的坐标 bestRow, bestColumn输出：当前棋局落子分布board[][3]，最佳着点的坐标 bestRow, bestColumn 返回该落子点的分值value*/int ChooseMove(int board[][3], Side s, int & bestRow, int & bestColumn){ Side opp; // The other side int reply; // Value of opponent's reply int dc; // Placeholder int simpleEval; // Result of an immediate evaluation int value; //该落子点的分值，可以是枚举变量PositionVal中的任何一个 if( ( simpleEval = PositionValue(board) ) != UNCLEAR )//若胜负已分，则不再落子，直接返回分值 return simpleEval; if( s == PLAYER1 ) { opp = PLAYER2; value = PLAYER2_WIN; } else { opp = PLAYER1; value = PLAYER1_WIN; } // Search for a move. for( int row = 0; row < 3; row++ ) for( int column = 0; column < 3; column++ ) if( SquareIsEmpty( board, row, column ) ) { Place( board, row, column, s ); // Try s move; then reply = ChooseMove( board, opp, dc, dc );// Evaluate; Place( board, row, column, EMPTY ); // then undo // If s gets a better position; update //如果返回信息为自己可以赢，不再继续搜寻最佳落子点，直接在此处下子 if( s == PLAYER2 && reply == PLAYER2_WIN || s == PLAYER1 && reply == PLAYER1_WIN ) { bestRow = row; bestColumn = column; return reply; } //否则继续搜寻最佳落子点 if( s == PLAYER2 && reply > value || s == PLAYER1 && reply < value ) { value = reply; bestRow = row; bestColumn = column; } } return value;}void Place( int board[][3], int row, int column, int piece ){ board[ row ][ column ] = piece;}bool SquareIsEmpty( const int board[][3], int row, int column ){ return board[ row ][ column ] == EMPTY;}int PositionValue( const int board[][3]){ return IsAWin( board, PLAYER1 ) ? PLAYER1_WIN : IsAWin( board, PLAYER2 ) ? PLAYER2_WIN : BoardIsFull(board) ? DRAW : UNCLEAR;}/////////////////////////////////////////////////////////////////////////////////// Clear the board.void ClearBoard(int board[][3]){ for( int row = 0; row < 3; row++ ) for( int column = 0; column < 3; column++ ) board[ row ][ column ] = EMPTY;}/*函数介绍：根据当前棋局落子分布，判断棋盘是否已满输入：当前棋局落子分布board[][3]输出：若棋盘已满返回真，否则返回假*/bool BoardIsFull( const int board[][3]){ for( int row = 0; row < 3; row++ ) for( int column = 0; column < 3; column++ ) if( board[ row ][ column ] == EMPTY ) return false; return true;}/*函数介绍：根据当前落子选手选择的坐标落子，并判断其是否违规输入：落子前棋局分布board[][3] ，当前落子选手player，当前选手选择的坐标row, column输出：更新棋局分布board[][3] ；若当前落子选手没有违规返回真，否则返回假*/bool PlayMove( int board[][3], int player, int row, int column ){ if( row < 0 || row >= 3 || column < 0 || column >= 3 || board[ row ][ column ] != EMPTY ) {cout << row << column <<endl; return false; } board[ row ][ column ] = player; return true;}/*函数介绍：根据当前棋局落子分布，判断当前落子选手是否胜利输入：当前棋局落子分布board[][3] ，当前落子选手player输出：若当前落子选手胜利返回真，否则返回假*/bool IsAWin( const int board[][3], int player ){ int row, column; // Look for all in a row for( row = 0; row < 3; row++ ) { for( column = 0; column < 3; column++ ) if( board[ row ][ column ] != player ) break; if( column >= 3 ) return true; } // Look for all in a column for( column = 0; column < 3; column++ ) { for( row = 0; row < 3; row++ ) if( board[ row ][ column ] != player ) break; if( row >= 3 ) return true; } // Look on diagonals if( board[ 1 ][ 1 ] == player && board[ 2 ][ 2 ] == player && board[ 0 ][ 0 ] == player ) return true; if( board[ 0 ][ 2 ] == player && board[ 1 ][ 1 ] == player && board[ 2 ][ 0 ] == player ) return true; return false;}/*函数介绍：输出当前棋局落子分布输入：当前棋局落子分布board[][3]*/void PrintBoard(const int board[][3]){ cout << "-------\n"; for( int row = 0; row < 3; row++ ) { for( int col = 0; col < 3; col++ ) { cout << "|"; cout << board[row][col]; } cout << "|\n"; } cout << "-------" << endl;}

博客介绍

正文

第24次比赛第2题之测试程序:2006-04-17 20:51:00

评论