chessboard.cpp

用C++环境编写的五子棋小游戏

// chessboard.cpp

#include "chessboard.h"
#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <ctime>
using namespace std;


//     Function Implement Beginning

unsigned int randSeed=time(0);
unsigned int random()
{
    int multiplier=2743;
    int adder=5923;
    randSeed=multiplier*randSeed+adder;
    return randSeed;
}
//    线性同余, 得随即数
chessboard::chessboard()
{
    int row, col;
    for( row=0; row<size; row++)
    for( col=0; col<size; col++)
        m_gridState[row][col]=blank;
    initiGridMark();
}

void chessboard::renew()
{
    int row, col;
    for( row=0; row<size; row++)
    for( col=0; col<size; col++)
        m_gridState[row][col]=blank;
    initiGridMark();
}


chessboard::~chessboard()
{
}

void chessboard::initiGridMark()
{
    int row, col;
    int sum, count;

    for( row=0; row<size; row++ )
    for( col=0; col<size; col++ )
    {
        sum=0;
        for( count=1; count<=4; count++)   //    扫描邻近的四个格子    */
        {
            
            if( row-count>=0 )
                sum++;
            if( col-count>=0 )
                sum++;
            if( row+count<size )
                sum++;
            if( col+count<size )
                sum++;
            if( row-count>=0 && col-count>=0 )
                sum++;
            if( row+count<size && col+count<size )
                sum++;
            if( row-count>=0 && col+count<size )
                sum++;
            if( row+count<size && col-count>=0 )
                sum++;
            //   八个方向的判断
            }        
        m_gridMark[row][col]=sum;
    } 
    //   这是棋盘格子的底分, 在相同的情况之下, 越在棋盘的中间, 底分越高,
    //    越处于有利的地位
    
}

void chessboard::outputStates() const
{

    int row, col;
   
    cout<<"   ";
    for( row=0; row<size; row++ )
    {
        putchar(' ');
        row<9 ? putchar('1'+row) : putchar('A'+row-9);
    }
    cout<<endl;
    // 输出横向的标志,方便输入 1 2 3 4 5 6 7 8 9 A B C D E F...
   
    for( row=0; row<size; row++ )
    {
        row<9 ? putchar('1'+row) : putchar('A'+row-9);
        //    竖向的标志,方便输入     
        cout<<"  |";
        for( col=0; col<size; col++ )
        {
            switch( m_gridState[row][col] )
            {
            case blank: cout<<' '<<'|';        //    空 | |   
                        break;
            case black: cout<<'*'<<'|';       //   黑 |#|    
                        break;
            case white: cout<<'O'<<'|';        //    白 |O|   
                        break;
            default:    break;
            }
        }
        cout<<endl;    
    }
}

void chessboard::setGridState(const point& pt, states gridState)
{
    m_gridState[pt.x][pt.y]=gridState;
}

states chessboard::getGridState( const point& pt)
{
    return m_gridState[pt.x][pt.y];
}

void chessboard::getMaxGridMark(point &pt) const
{
    vector< point > max_Mark;
    int max_mark=m_gridMark[0][0];
    for( int i=0; i<size; i++)
    for( int j=0; j<size; j++)
        if( m_gridMark[i][j]>max_mark )
            max_mark=m_gridMark[i][j];
    //    得到最大的分数
    
    for( i=0; i<size; i++)
        for( int j=0; j<size; j++)
            if( m_gridMark[i][j]==max_mark )
                max_Mark.push_back( point(i,j));
    //   将分数最大的坐标点, 放在一个向量里面    

    pt=max_Mark[random()%max_Mark.size()];
    //   分数相同的, 随机取点, 保证每次游戏, 电脑不会下在同一个地方    */
    max_Mark.clear();
    //    注:    上面的算法效率低下, 不过够简单. 对于这样的小程序, 也足够了
    
}

//    下面是整个程序最重要的函数, 是电脑下棋的根据.
//    这个算法是简易的,根据当前棋局的形势来分析哪个地方有利,只考虑了当前的
//    一步棋. 简单说来, 五子棋都是相连的棋子越多,就越有利.
//    对每个格子进行计分. 要是格子附近, 相连的格子越多, 分数越高.
//  考虑三个棋子相连, T表示要考虑的格子(T其实也是一个空格, 因为已经下了的棋子
//    不用考虑,**     B表示黑, W表示白, K表示空.
//    1) T B B B K, 第一个B记8分, 第二个B记16分, 第三个B记32分, T的分数是三个相加
//    这样就相当于, a=8, n=3的等比数列求和. 
//    再考虑 2) T K B B B K, T和B中间隔了个空格, 对比情形1), 1) 更有利, 第一个
//    B记5分, 第二个B记10分, 第三个B记20分, 相当于a=5, n=3的等比数列求和.
//    3) T B B B W, 这个时候因为有个W挡着, 原来n=3, 现在取n--, 相当于a=8, n=2
//    4) T K B B B W , 取a=5, n=2
// 5) T K B B W, 取 a=5, n=1. 
//    6) T B B B B W, 这个时候要另当别论, 因为已经有了4个B相连, 和 T B B B B K 是一样
//        这个时候, 当n=4的时候就立即跳出循环, 不再扫描了, 就没有机会 n--了,
//       这时候 a=8, n=4, 基本上要是有4个相同棋子相连, 就会下在那个地方.
//    7) T K B B B B W  要考虑的格子T, a=5, n=4, 本来会好大的分数了, 
//            不过第一个空格是 a=8, n=4, 分数更大.
//  8) T K K B B B W, 和 T K B B B W一样, 就是说隔一个空格和隔几个空格的情况一样.
//        因为我们是要找出最大分数的格子,不是要排列每一个格子的分数.只要找到最有利就
//        成利, 上面两种情况, 都不如T B B B W, 有利.

//  上面只是考虑了一个方向的情况, 但是五子棋是有8个方向的, 同一直线上的棋子会互相
//    影响, 比如向左的棋子会影响向右的棋子. 比如 B T B B B, 考虑T, 左有一个空格了,
//  使右边的棋子价值升高, 右边的棋子也会让左边的棋子分数变高. 
//    程序采用同一直线扫描两次的方法, 先向右扫描, n=3, 跟着,n保持不变,左扫描, n+=1=4.
//   所以第一次扫描的时候, 左边棋子, a=8, n=3, 右边棋子, a=8, n=4.第二次扫描先左
//    后右, 左边a=8, n=1, 右边n+=3, a=8, n=4. 另外要是有别的棋子挡路, 按上,n作调整.
//    向8个方向扫描, 每个方向两次, 实际上扫描16次, 将分数相加.得出格子分数.
//    上面是基本策略, 程序中还有一些对策略的微小调整, 好象边界问题 
//   程序中 a用 mark表示, n用N表示

void chessboard::updateGridMark(const point &pt, states chessmanColor)
{
    states beginState;       //    扫描方向第一个格子的状态, 以决定mark的值    */
    states lastState;       //    扫描方向上最后扫描的格子状态, 用来决定扫
                           //    描下一个格子时, 更改N的值.    */                            
    states temp;            // 放着向着一个方向时,    第一个格子的的状态.用来决定
                            //    扫描同一直线的下个方向时, 更改N的值.    */

//   考虑 B T B B B. 向左扫描时, temp=black, 向右扫描时, beginState=black, 
//    temp==beginState && temp!=blank
//             N++, 这样的话, 左边的棋子就会影响右边.
//    因为还有一次先由后左的扫描, 向右时, temp=black, 向左扫描时, beginState=black
//    temp==beginState, N++, 这样的话, 右边的棋子就会影响左边. 
//    上面说的是好的影响, 要是
//    W T B B B, 向左扫描是, temp=white, 向右扫描时, beginState=black, N--
//               向右扫描是, temp=black, 向左扫描时, beginState=white, N--
//    还有种情况, 要是temp或者beginState等于blank时, 左边和右边互相不影响. N不变.              
    int countA, countB, countC;
    int x, y;
    int N;
    int mark;

     
    if( m_gridState[pt.x][pt.y]!=blank)
    {
        m_gridMark[pt.x][pt.y]=0;
        return ;
    }
    //棋盘上已经有棋子了, 分数为0, 这样就不会下到这个地方.
    
    for( countA=1; countA<=2; countA++)        //   每个方向两次扫描    
    for( countB=1; countB<=8; countB++ )    //   扫描8个方向    
    {
        x=pt.x;        
        y=pt.y;
        N=0;
        if( countB%2==1)
            temp=blank;        //    一条直线要扫描两个方向
                            //   每扫描完一条直线时,将temp的值重新设置为blank.
                            //   保证不同直线上的棋子不会互相影响     

        for( countC=1; countC<=size; countC++)
       //   扫描一个方向, 虽然设置得要扫描的次数好大,不过通常扫描了4个格子就可以
        //   跳出循环     
        {
            if( countA==1 )
            {
               
                switch( countB )
                {
                case 1:        x--; break;
                case 2:        x++; break;
                case 3:        y--; break;
                case 4:        y++; break;
                case 5:        x--; y--; break;
                case 6:        x++; y++; break;
                case 7:        x++; y--; break;
                case 8:        x--; y++; break;
                }
                //    第一次扫描, 先左后右, 先上后下....   
             }
             else
             {
                 switch( countB )
                 {
                 case 1:        x++; break;
                 case 2:        x--; break;
                 case 3:        y++; break;
                 case 4:        y--; break;
                 case 5:        x++; y++; break;
                 case 6:        x--; y--; break;
                 case 7:        x--; y++; break;
                 case 8:        x++; y-- ; break;
                 }
                 //    第一次扫描, 先右后左, 先下后上....     
             }
             //       switch中 case的语句不可以顺便掉转
             
             if( !(x>=0 && x<size && y>=0 && y<size) )
                 break;
             //   遇到边界, 跳出循环    
             
             if( countC==1)
             {
                 beginState=lastState=m_gridState[x][y];
                //     初始这两个值,为扫描作准备     
                  
                 if( temp==beginState && temp!=blank)
                    N++;
                 if( temp!=beginState && temp!=blank && beginState!=blank)
                    N--;
                 temp=beginState;
                 //   同一直线的棋子互相影响, 见states temp下的注释
                 
                 if( beginState==blank )
                    mark=5;        
                 else mark=8;
                 //  根据附近第一个格子是不是空格, 记分, 见上面注释
                 
                 if( beginState==chessmanColor )
                     mark+=1;
                 //    假设轮到黑棋下的,要是附近也是黑棋,mark++, 使电脑
                 //    更具有攻击性.
                  
             }   

          
             if( m_gridState[x][y]!=lastState && lastState!=blank )
             {
                  if( m_gridState[x][y]!=blank )
                      N--;        
                  break;
                  //    黑被白挡, 或者白被黑挡, n--, 跳出循环
                  
             }
             //   遇到不同状态的格子挡路
             
             if( m_gridState[x][y]!=blank )
             {
                 N++;
                 lastState=m_gridState[x][y];
             }
             //    遇到己方棋子,n++, 因为要是黑遇白或者白遇黑, 在上面的语句已经
             //    处理过了, 并跳出了循环, 不会来到这个地方.
              

             if( N==4 )
                 break;  
             //        N为4时, 就跳出循环, 以免再遇到其他的棋子, 将N值减少    */

        }//endfor

         
        if( !(x>=0 && x<size && y>=0 && y<size) && N>0)
            N--;
        //    边界情形, N--, 相当于不同棋子挡路.
        
        m_gridMark[pt.x][pt.y]+=(mark*pow(3,N)-mark)/2+3*N;
        //    根据等比公式, 本来是 mark*pow(2,N)-mark.
        //    改成上面的形式,是为了让连得越多的棋,得到的分数越高.
        //   使得只要有一个N=4, 就会下到那个地方. 可以更改其他值试验,得出
        //    最合理的值.
         
   }//endfor_for
}

void chessboard::updateMarks(states chessmanColor)
{
    int row, col;
    initiGridMark();        //   底分     
    for( row=0; row<size; row++)
    for( col=0; col<size; col++)
        updateGridMark(point(row,col), chessmanColor);
}
//     程序只考虑了当前的形势, 不是成熟的策略.
//        另外, 每走一步棋, 都要更新整个棋盘的格子分数,也是不合理的,
//       因为只有和那步棋处在同一条直线上的格子才有可能改变分数.
//        要是根据这个条件来改写, 程序的效率会成倍数增加.
//        不过这样会会问题复杂, 对于这样的小程序,已经快到你看不见了,也没有必要