基于博弈树的开源五子棋AI教程[5 启发式搜索]

启发式搜索的姿势千奇百怪，本文只讨论一下几种

//搜索空间
#define Search_Space_MVA    0     //最优价值攻击者[分数最大]
#define Search_Space_MCP    1     //最优棋型
#define Search_Space_MHT    2     //历史表排序
#define Search_Space_MKT    3     //杀手表排序
#define Search_Space_MT     4     //综合技术[MVA + MHT + MKT + 置换表]
#define Search_Space_FS     5     //第一手生成策略

1 最大化攻击者/最小化防守者排序

这里就是最简单对于当前节点棋盘分数/分数的增长量进行排序。得分越高，出现越靠前。

//视角为 evalPlayer
void GameBoard::getSearchSpaceAroundStonesMaxValuableAttacter(QList<MPoint> &searchVectors,
                                                              QList<MPoint> &seachSpace,
                                                              MPlayerType evalPlayer, MPlayerType searchPlayer,
                                                              quint8 searchType /* = MINIMAX_SEARCH*/) {
    bool maximizingPlayer = evalPlayer == searchPlayer;

    int cutLength = getSearchCutLength(seachSpace, maximizingPlayer, searchType);
    QList<int> searchVectorsScores;
    searchVectors.reserve(cutLength);
    searchVectorsScores.reserve(cutLength);

    quint16 savedSearchBoardPatternDirection[boardSize][boardSize];
    int minScore = INT_MAX;  // 记录最小分数

    for (const auto& s : seachSpace) {
        quint64 key = zobristSearchHash.generateHash(s, PLAYER_NONE, searchPlayer);
        int scoreCur;
        if (!zobristSearchHash.getLeafTable(searchPlayer, scoreCur, key)) {
            setSearchBoard(s, searchPlayer, savedSearchBoardPatternDirection);  // 模拟落子
            scoreCur = evaluateBoard(searchPlayer);
            setSearchBoard(s, PLAYER_NONE, savedSearchBoardPatternDirection);  // 撤销模拟落子
        }

        if (scoreCur <= minScore && searchVectors.size() >= cutLength) {
            continue; // 如果当前分数不够高且列表已满，跳过
        }

        // 插入排序
        int insertPos = 0;
        for (; insertPos < qMin(searchVectors.size(), cutLength); ++insertPos) {
            if (scoreCur > searchVectorsScores[insertPos]) {
                break;
            }
        }

        if (insertPos < cutLength) {
            searchVectors.insert(insertPos, s);
            searchVectorsScores.insert(insertPos, scoreCur);
            if (searchVectors.size() > cutLength) {
                searchVectors.removeLast(); // 移除最小分数的元素
                searchVectorsScores.removeLast();
            }
            minScore = searchVectorsScores.last(); // 更新最小分数
        }
    }

    // sortSearchResultByCoference(searchVectors, searchHash, maximizingPlayer, searchType);
}

2 置换表启发

置换表保存了搜索过程中最优价值的节点信息，如果发现当前搜索状态在置换表，那么这一状态应该率先被搜索。

//返回的值:[0,id-1]是使用历史表启发后的结果
int GameBoard::sortMoveBySearchHistoryTable(QVector<MPoint> &searchVector,quint8 startPosition/*=0*/, quint8 searchType/*=minimax_search*/)
{
    Q_UNUSED(searchType);
    if(!globalParam::utilGameSetting.IsOpenSearchHistoryTable) return startPosition;
    QReadLocker locker(&globalParam::historyTableLock);
    std::sort(searchVector.begin() + startPosition, searchVector.end(), [](const MPoint &a, const MPoint &b) {
        return globalParam::historyTable[a.x()][a.y()] > globalParam::historyTable[b.x()][b.y()];
    });

    //只保留有值点
    for(;startPosition < searchVector.size(); startPosition ++){
        if(globalParam::historyTable[searchVector.at(startPosition).x()][searchVector.at(startPosition).y()] == 0) break;
    }
    return startPosition;
}

3 杀手表启发

杀手表保存了搜索过程中某一指定搜索深度下各个节点的剪枝信息。搜索过程中，在因为某节点产生的剪枝次数越多，这个值也就越大。

//返回的值:[0,id-1]是使用杀手表启发后的结果
int GameBoard::sortMoveBySearchKillerTable(QVector<MPoint> &searchVector, quint8 startPosition/*=0*/, quint8 searchType/*=minimax_search*/)
{
    Q_UNUSED(searchType);
    if(!globalParam::utilGameSetting.IsOpenKillerTable) return startPosition;
    QReadLocker locker(&globalParam::killerTableLock);
    int depth = searchSpacePlayers.size();
    std::sort(searchVector.begin() + startPosition, searchVector.end(), [depth](const MPoint &a, const MPoint &b) {
        return globalParam::killerTable[depth][UtilGetMPointPosID(a)] > globalParam::killerTable[depth][UtilGetMPointPosID(b)];
    });
    //只保留有值点
    for(;startPosition < searchVector.size(); startPosition ++){
        if(globalParam::killerTable[depth][UtilGetMPointPosID(searchVector.at(startPosition))] == 0) break;
    }
    return startPosition;
}

4 历史表启发

类似于杀手表，但是历史表忽略了搜索深度信息。只要在搜索过程中因为某一节点产生了剪枝，这个节点的价值就会变大。

//返回的值:[0,id-1]是使用历史表启发后的结果
int GameBoard::sortMoveBySearchHistoryTable(QVector<MPoint> &searchVector,quint8 startPosition/*=0*/, quint8 searchType/*=minimax_search*/)
{
    Q_UNUSED(searchType);
    if(!globalParam::utilGameSetting.IsOpenSearchHistoryTable) return startPosition;
    QReadLocker locker(&globalParam::historyTableLock);
    std::sort(searchVector.begin() + startPosition, searchVector.end(), [](const MPoint &a, const MPoint &b) {
        return globalParam::historyTable[a.x()][a.y()] > globalParam::historyTable[b.x()][b.y()];
    });

    //只保留有值点
    for(;startPosition < searchVector.size(); startPosition ++){
        if(globalParam::historyTable[searchVector.at(startPosition).x()][searchVector.at(startPosition).y()] == 0) break;
    }
    return startPosition;
}

历史表以及杀手表的维护

杀手表和历史表的方法类似，这里仅提供杀手表的维护过程。

初始化

QReadWriteLock globalParam::killerTableLock;
int globalParam::killerTable[GameSetting::BoardSize * GameSetting::BoardSize + 1][GameSetting::BoardSize * GameSetting::BoardSize] = {{0}};

追加杀手表项

//追加杀手表表项
//depth:表示距离叶子的深度
void GameBoard::appendSearchKillerTable(const MPoint &position, int depth, quint8 NABSearchHashFlag)
{
    if(!globalParam::utilGameSetting.IsOpenKillerTable) return;
    QWriteLocker locker(&globalParam::killerTableLock);
    //随着搜索的加深，逐渐靠近叶子节点，depth的值逐步变小，对于历史表的贡献也在变小
    if(NABSearchHashFlag == hashfLowerBound){
        globalParam::killerTable[searchSpacePlayers.size()][UtilGetMPointPosID(position)] += depth * depth;
    }
}

清空杀手表

//清楚所有的杀手表
void GameBoard::clearSearchKillerTable()
{
    if(!globalParam::utilGameSetting.IsOpenKillerTable) return;

    QWriteLocker locker(&globalParam::killerTableLock);
    //全部置零清除杀手表
    for(int row = 0;row < boardSizeSquare + 1; ++row){
        for(int col = 0; col < boardSizeSquare; ++col){
            globalParam::killerTable[row][col] = 0;
        }
    }
    //    //使用累积影响的方式清除杀手表
    //    for(int row = 0;row < boardSizeSquare + 1; ++row){
    //        for(int col = 0; col < boardSizeSquare; ++col){
    //            globalParam::killerTable[row][col] = globalParam::historyTable[row][col] >> 2;
    //        }
    //    }
}