基于博弈树的开源五子棋AI教程[4 静态棋盘评估]

引子

静态棋盘的评估是棋力的一个很重要的体现，一个优秀的基于博弈树搜索的AI往往有上千行工作量，本文没有做深入讨论，仅仅写了个引子用来抛砖引玉。
评估一般从两个角度入手，一个是子力，另一个是局势。

1 评估维度

1.1子力

所谓的子力，也就是每个子的重要程度，这边用基础棋型来衡量。通过扫描匹配棋型，重要的棋型给予更大的值，这里棋型得分表参考了网上的数值。
另一种衡量子力的方式是是利用五元组，通过判定五元组内子的连续性和阻断性赋予不同的分数。

//------定义基础棋型------//
#define ChessNone          0    // 空棋型:0
#define ChessSleepingOne   1    // 眠一  :0
#define ChessActiveOne     2    // 活一  :20
#define ChessSleepingTwo   3    // 眠二  :20
#define ChessActiveTwo     4    // 活二  :120
#define ChessSleepingThree 5    // 眠三  :120
#define ChessActiveThree   6    // 活三  :720
#define ChessBrokenFour    7    // 冲四  :720
#define ChessActiveFour    8    // 活四  :4320
#define ChessFive          9    // 连五  :50000
#define ChessSix           10   // 长连  :50000

//基础棋型得分表
static const QHash<quint8, int> UtilChessPatternScore ={
    {ChessNone,          0},       // 0: 无棋子
    {ChessSleepingOne,   0},       // 1: 眠一
    {ChessActiveOne,     20},      // 2: 活一
    {ChessSleepingTwo,   20},      // 3: 眠二
    {ChessActiveTwo,     120},     // 4: 活二
    {ChessSleepingThree, 120},     // 5: 眠三
    {ChessActiveThree,   720},     // 6: 活三
    {ChessBrokenFour,    720},     // 7: 冲四
    {ChessActiveFour,    4320},    // 8: 活四
    {ChessFive,          50000},   // 9: 连五
    {ChessSix,           50000}    // 10: 长连
};

在后续棋型评估中，本文可以有选择性的开启可识别的基础棋型。

    //定义搜索棋型
    QVector<quint8> activateChessPattern = {
        //活棋型
        ChessActiveOne,ChessActiveTwo,ChessActiveThree,ChessActiveFour,ChessBrokenFour,
        //眠棋型
//        ChessSleepingTwo,ChessSleepingThree,
//        ChessSleepingOne,
        ChessFive,ChessSix
    };

一些特殊棋型需要进行修正，例如双活三，三四。本文在后面会依次介绍。

1.2 局势

所谓局势，就是一方可以轻松的组织起攻势，另一方或许防守，或许反击。通常来说，棋局子力越大，局势可能会更好。由于子力评估天然不关注空间位置，注定了无法准确衡量局势。图中子力[只评估了活棋型]相同，但是两者局势截然不同。

AI中并没有找到合适的方案来衡量不同的局势，因此这一块暂时为空白状态。

2 实现

实现分成两个部分，一是基础棋型子力计算，二是基础棋型匹配算法。

2.1 子力计算

棋盘得分即是棋盘上所有点的子力。单点子力分成三步实现，第一步计算基础得分。第二步修正分数，修正分数的逻辑就是将活三，三四修正成一个活四。第三步禁手逻辑的处理。

//评分视角为evaluatePlayer
int GameBoard::evaluateBoard(MPlayerType evalPlayer)
{
    int score = 0;
    if (evalPlayer == PLAYER_NONE) return score;

    if(zobristSearchHash.getLeafTable(evalPlayer, score)){
        aiCalInfo.hitEvaluateBoardZobristHashCurrentTurn ++;
        return score;
    }
    QElapsedTimer timer;
    timer.start();
    aiCalInfo.evaluateBoardTimesCurrentTurn ++;

    int evaluatePlayerScore = 0;
    int enemyPlayerScore = 0;

    // 遍历整个棋盘
    for(const auto &curPoint : searchSpacePlayers){
        MPlayerType curPlayer = getSearchBoardPiece(curPoint.x(), curPoint.y());
        quint8 curChessPatterns[Direction4Num];
        getSearchBoardPatternDirection(curPoint.x(), curPoint.y(), curChessPatterns);
        int chessPatternCount[ChessPatternsNum] = {0};

        for(int direction = 0;direction < Direction4Num; ++direction){
            if(curPlayer == evalPlayer){
                evaluatePlayerScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[curChessPatterns[direction]];
            }
            else{
                enemyPlayerScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[curChessPatterns[direction]];
            }
            ++ chessPatternCount[curChessPatterns[direction]];
        }
        int fixedScore = 0;
        //修正分数
        if(chessPatternCount[ChessActiveThree] > 1){
            //多个活三修正成一个活四
            fixedScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveFour] * 3;
        }

        if(chessPatternCount[ChessBrokenFour] + chessPatternCount[ChessActiveThree] > 1 || chessPatternCount[ChessBrokenFour] > 1)
        {
            //单活三单冲四修正成一个活四
            //双冲四修正成一个活四
            fixedScore += globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveFour] * 2;
        }


        //禁手逻辑
        if(globalParam::utilGameSetting.IsOpenBalanceBreaker && evalPlayer == PLAYER_BLACK){
            bool isTriggerBalanceBreaker = false;
            if(chessPatternCount[ChessActiveThree] > 1){
                //三三禁手(黑棋一子落下同时形成两个活三，此子必须为两个活三共同的构成子)
                fixedScore -= chessPatternCount[ChessActiveThree] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveThree];
                isTriggerBalanceBreaker = true;
            }
            if(chessPatternCount[ChessActiveFour] + chessPatternCount[ChessBrokenFour]>1)
            {
                //四四禁手(黑棋一子落下同时形成两个或两个以上的冲四或活四)
                fixedScore -= chessPatternCount[ChessActiveFour] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessActiveFour];
                fixedScore -= chessPatternCount[ChessBrokenFour] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessBrokenFour];
                isTriggerBalanceBreaker = true;
            }
            if(chessPatternCount[ChessSix] > 0)
            {
                //长连禁手(黑棋一子落下形成一个或一个以上的长连)
                fixedScore -= chessPatternCount[ChessSix] * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessSix];
                isTriggerBalanceBreaker = true;
            }

            if(isTriggerBalanceBreaker)
                fixedScore -= 5 * globalParam::utilChessPatternInfo.utilSpecialPatternScoreTable[ChessSix];
        }

        if(curPlayer == evalPlayer)
            evaluatePlayerScore += fixedScore;
        else
            enemyPlayerScore += fixedScore;
    }

    UtilCalculateScore(score, evaluatePlayerScore, enemyPlayerScore,globalParam::utilGameSetting.AttackParam);

    zobristSearchHash.appendLeafTable(evalPlayer, evaluatePlayerScore, enemyPlayerScore);

    aiCalInfo.AIEvaluateBoardTime += timer.nsecsElapsed();
    return score;
}

2.2 棋型匹配算法

棋型匹配方案和算法都有多种。方案一般就及时匹配，增广的匹配。及时匹配是指对于一个给定的棋盘，扫描所有的行来匹配棋型。增广匹配是指利用在已知原有棋型的棋盘上增加一子后，仅扫描匹配变动行的棋型。对于算法我尝试了三种，第一种是字符串的暴力匹配，第二种是改进的位暴力匹配，第三种是AC自动机的匹配。
本文采用的是增广匹配+位暴力匹配的模式来完成的。

//这一段代码即是在原有棋盘上添加evaluatePoint后，更新evaluatePoint所在行列上点的棋型
void GameBoard::updatePointPattern(const MPoint &evaluatePoint)
{
    //拓展后的位置
    if(!isValidSearchPosition(evaluatePoint)) return;

    int row = evaluatePoint.x();
    int col = evaluatePoint.y();

    for(int direction = 0;direction < Direction4Num;direction ++){
        int dx = UtilsSearchDirection4[direction].x();
        int dy = UtilsSearchDirection4[direction].y();
        for(int i = -globalParam::utilChessPatternInfo.maxChessPatternLength + 1;i <=globalParam::utilChessPatternInfo.maxChessPatternLength-1;i ++){
            //更新所在方向上的棋型
            int tmpRow = row + dx*i;
            int tmpCol = col + dy*i;
            if(searchBoardHasPiece(tmpRow,tmpCol)){
                setSearchBoardPatternDirection(tmpRow,tmpCol,direction,ChessNone);
                updatePointPattern(tmpRow, tmpCol, direction);
            }
        }
    }
}

下面给出的更新MPoint(row,col)在direction上的棋型，四个方向的处理逻辑大同小异，仅以水平方向为例，循环匹配已经从大到小排好序的基础棋型直到找到一个最大的棋型后退出。匹配过程包含两部分，通过位运算提取棋盘的棋型，接着和库中棋型比较。对于比较也就是简单的几个int值的比较。

void GameBoard::updatePointPattern(MPositionType row, MPositionType col, int direction)
{
    //拓展后的位置
    MPlayerType evalPlayer = getSearchBoardPiece(row, col);

    int dx = UtilsSearchDirection4[direction].x();
    int dy = UtilsSearchDirection4[direction].y();

    if(getSearchBoardPiece(0,0,true) == evalPlayer)
        setSearchBoardBoarder(UtilReservePlayer(evalPlayer));

    quint16 curEvaluatePointChessPattern = ChessNone;

    int xx,yy;

    switch (direction) {
    case MHorizontal:
        //水平[右]
        for(int i = -globalParam::utilChessPatternInfo.maxChessPatternLength+1;i <=0;i ++){
            int tmpRow = row + dx*i;
            int tmpCol = col + dy*i;
            if(!isValidSearchPosition(tmpRow,tmpCol,true)) continue;

            for(int chessPatternId = globalParam::utilChessPatternInfo.chessPatternSize-1;chessPatternId>=0; chessPatternId --){
                int chessPatternLength = globalParam::utilChessPatternInfo.standLengthInfo[chessPatternId];
                int searchLength = - i + 1;
                if(searchLength > chessPatternLength) continue;
                if(globalParam::utilChessPatternInfo.standPatternInfo[chessPatternId] <= curEvaluatePointChessPattern) continue;

                int mask = (1 << chessPatternLength) - 1;
                int Datamask = (searchBoardMask[tmpRow] >> tmpCol) & mask;
                int Data = (searchBoard[tmpRow] >> tmpCol) & Datamask;

                int cpmask = globalParam::utilChessPatternInfo.utilWhiteChessPatternMaskInfo[chessPatternId];
                int cp = globalParam::utilChessPatternInfo.utilWhiteChessPatternDataInfo[chessPatternId];
                int cpReverse = globalParam::utilChessPatternInfo.utilBlackChessPatternDataInfo[chessPatternId];

                if( Datamask == cpmask && ((Data == cp && evalPlayer == PLAYER_WHITE)
                                           || (Data == cpReverse && evalPlayer == PLAYER_BLACK)))
                {
                    quint8 chessPattern = globalParam::utilChessPatternInfo.standPatternInfo[chessPatternId];
                    setSearchBoardPatternDirection(row,col,direction,chessPattern);
                    curEvaluatePointChessPattern = chessPattern;
                    break;
                }

            }
        }
        break;
        }
}