网站免费建站的方法,最好机票网站建设,wordpress路由映射,佛山网站建设报价文章目录 1 最大化攻击者/最小化防守者排序2 置换表启发3 杀手表启发4 历史表启发历史表以及杀手表的维护初始化追加杀手表项清空杀手表 启发式搜索的姿势千奇百怪#xff0c;本文只讨论一下几种 //搜索空间
#define Search_Space_MVA 0 //最优价值攻击者[分数最大]
#d… 文章目录 1 最大化攻击者/最小化防守者排序2 置换表启发3 杀手表启发4 历史表启发历史表以及杀手表的维护初始化追加杀手表项清空杀手表 启发式搜索的姿势千奇百怪本文只讨论一下几种 //搜索空间
#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(QListMPoint searchVectors,QListMPoint seachSpace,MPlayerType evalPlayer, MPlayerType searchPlayer,quint8 searchType /* MINIMAX_SEARCH*/) {bool maximizingPlayer evalPlayer searchPlayer;int cutLength getSearchCutLength(seachSpace, maximizingPlayer, searchType);QListint 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(QVectorMPoint 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(QVectorMPoint 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(QVectorMPoint 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;// }// }
}
