基于博弈树的开源五子棋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;//        }//    }
}