酷应用

象棋人工智能算法的C++实现（二）

百家作者：程序人生 2018-10-25 07:38:57

点击上方“程序人生”，选择“置顶公众号”

第一时间关注程序猿（媛）身边的故事

作者

De掉所有bug

已获原作者授权，如需转载，请联系原作者。

前言：在看完上一期《象棋人工智能算法的C++实现（一）》后，是不是对这个项目感到有点小兴奋呢？但是我首先要声明的是，这并不是最前沿的人工智能，所用的算法或许不是最快速的，只是闲的没事做着玩的一个小项目。欢迎各位攻城狮、各位行业大牛的讨论、批评与指正。

有了上一期的铺垫，本期就可以实现诸如马走日、象走田等各种棋子的走棋算法了。为了方便后期人工智能算法的实现，我们写一个总的canMove函数，在这个总的canMove函数里调用各种类型棋子的canMove函数来判断各种棋子选择的路径能不能走得通。

总的canMove函数的源代码：

bool Board::canMove(int moveid, int killid, int row, int col)
{
    if(killid==-1||!sameColor(moveid,killid))
    {
        switch(_s[moveid]._type)
        {
        case Stone::JIANG:
            return canMoveJIANG(moveid,row,col,killid);
            break;
        case Stone::SHI:
            return canMoveSHI(moveid,row,col,killid);
            break;
        case Stone::XIANG:
            return canMoveXIANG(moveid,row,col,killid);
            break;
        case Stone::CHE:
            return canMoveCHE(moveid,row,col,killid);
            break;
        case Stone::MA:
            return canMoveMA(moveid,row,col,killid);
            break;
        case Stone::PAO:
            return canMovePAO(moveid,row,col,killid);
            break;
        case Stone::BING:
            return canMoveBING(moveid,row,col,killid);
            break;
        default: break;
        }
    }
 
    //move的棋子和kill的棋子是相同颜色的
    if(sameColor(moveid,killid))
    {
        /*换选择*/
        _selectid=killid;
        update();
        return false;
    }
    return true;
}

本期博客主要介绍相对简单的士、兵、相、马的走棋算法。

1.士的走棋算法

士的走棋规则：只能在米字格（大本营）内行走，且一次只能沿着对角线斜着走一步。

上canMoveSHI函数的源代码：

bool Board::canMoveSHI(int moveid,int row,int col,int killid)
{
    if(_s[moveid]._red)
    {
        //判断红方士的纵向行走是否超出米字格范围
        if(row>2) return false;
    }
    else
    {
        //判断黑方士的纵向行走是否超出米字格范围
        if(row< 7) return false;
    }
 
    //判断红黑双方方士的横向行走是否超出米字格范围
    if(col< 3) return false;
    if(col>5) return false;
 
    //判断是否为沿着对角线斜着行走
    int dr=_s[moveid]._row-row;
    int dc=_s[moveid]._col-col;
    if(abs(dr)==1&&abs(dc)==1)
        return true;
 
    return false;
}

算法解析：红方和黑方的米字格范围不同，红方米字格的范围：row:0~2，col:3~5；黑方米字格的范围：row:7~9，col:3~5。要想让士沿着对角线斜着走，就是想让移动前后的横坐标差的绝对值和纵坐标差的绝对值都为1，横纵各移动一个单位长度。

士的行走图示：

2.兵的走棋算法

兵的走棋规则：无论过没过河，纵向上都不能走回头路。没过河的时候只能纵向走，过了河才可以横向走。

上canMoveBING函数的源代码：

bool Board::canMoveBING(int moveid,int row,int col,int killid)
{
    /*兵的走棋规则*/
    int dr=_s[moveid]._row-row;
    int dc=_s[moveid]._col-col;
 
    //红棋
    if(_s[moveid]._red)
    {
        //过河前
        if(_s[moveid]._row>=3&&_s[moveid]._row< =4)
        {
            //竖着走
            if(dr==-1&&dc==0)
                return true;
            //横着走
            else
                return false;
        }
        //过河后
        else
        {
            if(abs(dr)==1&&abs(dc)==0||(abs(dc)==1&&abs(dr)==0))
            {
                //竖着走
                if(dr==1)
                    //竖着走走了回头路就要返回错误
                    return false;
                //横着走
                else
                    return true;
            }
            else
                return false;
        }
    }
    //黑棋
    else
    {
        //过河前
        if(_s[moveid]._row>=5&&_s[moveid]._row< =6)
        {
            //竖着走
            if(dr==1&&dc==0)
                return true;
            //横着走
            else
                return false;
        }
        //过河后
        else
        {
            //竖着走
            if(abs(dr)==1&&abs(dc)==0||(abs(dc)==1&&abs(dr)==0))
            {
                //竖着走走了回头路就要返回错误
                if(dr==-1)
                    return false;
                //横着走
                else
                    return true;
            }
            else
                return false;
        }
    }
    return true;
}

算法解析：兵的走棋算法的实现就比士的要难，既要处理每次移动的长度又要区分过河前和过河后的情况。实现不能走回头路的方法是计算行坐标差，以下图所示为例，以上一期博客所述的坐标系为准，红方在上，黑方在下，则红兵不能走回头路的控制条件就是行坐标差（当前位置的行坐标-目标位置的行坐标）必须为-1，黑兵不能走回头路的控制条件就是行坐标差（当前位置的行坐标-目标位置的行坐标）必须为1。实现过河与否的判断则是通过简单的行坐标范围来界定。实现步长为1的控制则更为简单，即行坐标差的绝对值为1且列坐标差的绝对值为0（或行坐标差的绝对值为0且列坐标差的绝对值为1）。

3.相的走棋算法

相的走棋规则：走田字格。若所跨田字格的中心位置有棋子存在，此时为“别象眼”，相便不能完成行走。相不能过河。

上canMoveXIANG函数的源代码：

bool Board::canMoveXIANG(int moveid,int row,int col,int killid)
{
    //不能过河
    if(_s[moveid]._red)
    {
        if(row>4) return false;
    }
    else
    {
        if(row< 5) return false;
    }
 
    //走田字格
    int dr=_s[moveid]._row-row;
    int dc=_s[moveid]._col-col;
    int medium_r=(_s[moveid]._row+row)/2;
    int medium_c=(_s[moveid]._col+col)/2;
    if(abs(dr)==2&&abs(dc)==2)
        //别象眼检验
        if(!beStone(medium_r,medium_c))
            return true;
 
    return false;
}

算法解析：实现走田字格的控制条件即是行坐标差的绝对值为2且列坐标差的绝对值为2（横纵方向上的移动步长都为2）。实现过河与否的判断则是通过简单的行坐标范围来界定。别象眼检验是相的走棋算法的核心部分，此处运用了一点初中数学知识，即中点坐标的求法，田字格对角线上的中点的坐标为((相的当前行坐标+目标位置行坐标)/2,(相的当前位置列坐标+目标位置列坐标)/2)。确定了象眼的行列坐标再调用上期博客介绍的beStone函数即可得知象眼处是否有棋子，若有棋子相则不能完成行走。

相的行走图示：

4.马的走棋算法

马的走棋规则：走日字格（横向移动1格且竖向移动2格or横向移动2格且竖向移动1格）。移动2格的那个方向上距离马当前位置最近的位置上若有棋子存在，则此时为“别马腿”，马便不能完成行走。

上canMoveMA函数的源代码：

bool Board::canMoveMA(int moveid,int row,int col,int killid)
{
    int dr=_s[moveid]._row-row;
    int dc=_s[moveid]._col-col;
    int medium_r=(_s[moveid]._row+row)/2;
    int medium_c=(_s[moveid]._col+col)/2;
    if(abs(dr)==1&&abs(dc)==2||(abs(dr)==2&&abs(dc)==1))
    {
        if(abs(dr)==2)
        {
            //别马腿检验
            if(beStone(medium_r,_s[moveid]._col)==false)
                return true;
        }
        else
        {
            //别马腿检验
            if(beStone(_s[moveid]._row,medium_c)==false)
                return true;
        }
    }
    return false;
}

算法解析：实现走日字格的方法是控制行坐标差的绝对值为1且列坐标差的绝对值为2（或行坐标差的绝对值为2且列坐标差的绝对值为1）。要想实现别马腿的检验就要先确定马的“绊脚石”的行列坐标，若马的移动步长为2的方向为横向，则该“绊脚石”的坐标为(马的当前位置行坐标,(马的当前位置列坐标+目标位置列坐标)/2)；若马的移动步长为2的方向为纵向，则该“绊脚石”的坐标为((马的当前位置行坐标+目标位置行坐标)/2,马的当前位置列坐标)。

马的行走图示：

看到这里可能有人会说，我不会使用Qt开发项目，不用担心，整个项目的算法都可以抽象到控制台应用程序（黑框框）中，大家可以先动脑筋实现一下。如果后期还有人提问在黑框框中如何实现，我会视具体情况在后面的博客中加以介绍。

这个项目我会连载，后期各种算法的实现敬请期待！

- The End -

「若你有原创文章想与大家分享，欢迎投稿。」

加编辑微信ID，备注#投稿#：

程序丨 druidlost

小七丨 duoshangshuang

点文末阅读全文，看『程序人生』其他精彩文章推荐。

推荐阅读：

print_r('点个赞吧')；
var_dump('点个赞吧')；
NSLog(@"点个赞吧！")
System.out.println("点个赞吧!");
console.log("点个赞吧!");
print("点个赞吧!");
printf("点个赞吧!n");
cout < < "点个赞吧!" < < endl;
Console.WriteLine("点个赞吧!");
fmt.Println("点个赞吧!")
Response.Write("点个赞吧")；
alert（’点个赞吧’）