第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;
}

评论