怎么用阿里云服务器做淘客网站,重庆seo网络推广优化,只会后端不会前端如何做网站,网站访问量怎么做文章目录 引子定义实现结果尾记 引子
多线程加快搜索速度这一认知是经受住实践考验的。博弈树搜索的并行搜索方式有很多种#xff0c;例如叶子并行#xff0c;根并行#xff0c;树分裂等算法。笔者给出一种实现起来比较简单的根并行算法。 在是实现时需要注意两点#xff… 文章目录 引子定义实现结果尾记 引子
多线程加快搜索速度这一认知是经受住实践考验的。博弈树搜索的并行搜索方式有很多种例如叶子并行根并行树分裂等算法。笔者给出一种实现起来比较简单的根并行算法。 在是实现时需要注意两点第一怎么安全的剪枝第二如何进行线程间的通信。对于AB剪枝有三点发现可以指导我们设计多线程的并行算法
当某一节点搜索完成其分数才能安全的更新父亲节点的AB值。一个节点的AB值可以安全的更新其所有子孙节点的AB值。如果一个节点alpha beta, 这个节点可以安全的被剪枝
这样一来就可以知道一个节点搜索完成后如何更新博弈树所有节点的AB值如何剪枝。通信方式使用的全局变量读写锁控制的全局变量保存所有节点状态的AB值。当搜索开始从根节点沿着搜索路径开始更新沿路的所有节点AB值然后从全局变量中读取该节点的AB值。搜索完成后更新父亲节点AB值。
定义
struct parallelNABSearchNode{int alpha, beta;parallelNABSearchNode() : alpha(-INT_MAX), beta(INT_MAX){}parallelNABSearchNode(int aalpha, int abeta) : alpha(aalpha), beta(abeta){}QString str();//返回值:true已经更新false表示没更新bool getAlphaBeta(int aalpha, int abeta);bool updateLeaf2RootAlphaBeta(int score);//返回值:true已经更新false表示没更新bool updateRoot2LeafAlphaBeta(int aalpha, int abeta);
};//并行化搜索技术static QReadWriteLock parallelSearchTableLock;static QHashquint64, parallelNABSearchNode parallelSearchTable;函数实现三个方法一个getAlphaBeta(int aalpha, int abeta)是从全局变量中获取AB值一个updateLeaf2RootAlphaBeta是从更新该节点的父亲的AB值还有一个updateRoot2LeafAlphaBeta是更新儿子节点的AB值。
bool parallelNABSearchNode::getAlphaBeta(int aalpha, int abeta){if(!globalParam::utilGameSetting.IsOpenParallelSearch) return false;if(aalpha alpha beta abeta) return false;if(aalpha alpha){aalpha alpha;}if(beta abeta){abeta beta;}return true;
}bool parallelNABSearchNode::updateLeaf2RootAlphaBeta(int score){if(!globalParam::utilGameSetting.IsOpenParallelSearch) return false;if(score alpha){alpha score;return true;}return false;
}bool parallelNABSearchNode::updateRoot2LeafAlphaBeta(int aalpha, int abeta){if(!globalParam::utilGameSetting.IsOpenParallelSearch) return false;if(alpha aalpha abeta beta) return false;if(alpha aalpha){alpha aalpha;}if(abeta beta){beta abeta;}return true;
}实现
现在已经实现了线程间通信的工具只需要在搜索时调用这些利器就可以了总体的实现思路和常规负极大搜索如出一撤。为了能后续兼容树分裂的算法这里给出了并行化搜索指定深度的接口。
//fail-soft negMax Alpha-Beta pruning search
int GameAI::NABParallelSearch(int depth, int alpha, int beta, bool maximizingPlayer, quint8 searchSpaceType)
{int score -INT_MAX;QWriteLocker writeLock(globalParam::parallelSearchTableLock);// 更新根节点-当前节点搜索路径上AB值for(int pid 0;pid parallelSsearchHistoryPlayersHash.size() - 1; pid){//表项不存在会自动调用默认构造函数parallelNABSearchNode *curNode globalParam::parallelSearchTable[parallelSsearchHistoryPlayersHash[pid]];parallelNABSearchNode *sontNode globalParam::parallelSearchTable[parallelSsearchHistoryPlayersHash[pid 1]];//更新下一层的AB值sontNode-updateRoot2LeafAlphaBeta(- curNode-beta, - curNode-alpha);}// 获取当前AB值globalParam::parallelSearchTable[zobristSearchHash.hash()].getAlphaBeta(alpha, beta);
// // 更新AB值后可能引发剪枝
// if(alpha beta){ // AB剪枝
// aiCalInfo.cutTreeTimesCurrentTurn ;
// return beta;
// }writeLock.unlock();//探查置换表中值if(zobristSearchHash.getNABTranspositionTable(score, depth, alpha, beta)) {return score;}// ??或 分数过大过小
// if (qAbs(score) globalParam::utilGameSetting.MaxScore){
// //保存置换表
// return score;
// }int evalPlayer globalParam::AIPlayer;MPlayerType searchPlayer maximizingPlayer ? evalPlayer : UtilReservePlayer(evalPlayer);// 达到搜索深度if (depth 0 || checkSearchBoardWiner() ! PLAYER_NONE){//保存置换表score evaluateBoard(evalPlayer);//负极大搜索中评估必须searchPlayerif(!maximizingPlayer) score * -1;// //VCF
// QListMPoint vcf, vcfpath;
// if(VCXSearch(globalParam::utilGameSetting.MaxVctSearchDepth, maximizingPlayer, VCT_SEARCH, vcf, vcfpath)){
// qDebug() NABsearch : find vct;
// if(maximizingPlayer) return globalParam::utilGameSetting.MaxScore;
// else return -globalParam::utilGameSetting.MaxScore;
// }return score;}// 着法生成QVectorMPoint searchPoints;getSortedSearchSpace(searchPoints, evalPlayer, searchPlayer, searchSpaceType);int scoreBest -INT_MAX;int hashf hashfUperBound;MPoint moveBest(InvalidMPoint);quint16 savedSearchBoardPatternDirection[boardSize][boardSize];for (const auto curPoint : searchPoints) {if (!searchBoardHasPiece(curPoint)) {setSearchBoard(curPoint, searchPlayer, savedSearchBoardPatternDirection);// searchPlayer落子score -NABParallelSearch(depth - 1, -beta, -alpha, !maximizingPlayer,searchSpaceType);setSearchBoard(curPoint, PLAYER_NONE, savedSearchBoardPatternDirection);// 撤销落子if (score scoreBest) {scoreBest score;moveBest curPoint;if (score beta) {hashf hashfLowerBound;appendSearchKillerTable(curPoint, depth, hashf);aiCalInfo.cutTreeTimesCurrentTurn ;break; // Alpha-Beta 剪枝}if (score alpha) {alpha score;hashf hashfExact;//更新当前层的AB值writeLock.relock();parallelNABSearchNode *curNode globalParam::parallelSearchTable[zobristSearchHash.hash()];curNode-alpha scoreBest;writeLock.unlock();}}}}// writeLock.relock();
// //更新当前层的AB值
// parallelNABSearchNode *curNode globalParam::parallelSearchTable[zobristSearchHash.hash()];
// curNode-alpha scoreBest;
// writeLock.unlock();writeLock.relock();//更新上一层的AB值只有当前所有节点搜索完成后得到的值才是可靠的才能用来更新父亲节点的AB值if(parallelSsearchHistoryPlayersHash.size() 2){const quint64 fatherHash parallelSsearchHistoryPlayersHash[parallelSsearchHistoryPlayersHash.size()-2];parallelNABSearchNode *fatherNode globalParam::parallelSearchTable[fatherHash];fatherNode-updateLeaf2RootAlphaBeta(-scoreBest);}writeLock.unlock();//更新历史表appendSearchHistoryTable(moveBest, depth, hashf);// 更新置换表zobristSearchHash.appendNABTranspositionTable(depth, scoreBest, hashf, moveBest, UtilReservePlayer(searchPlayer));return scoreBest;
}
结果
这里实现的并行化搜索效果并不出众只能说是有一定效果。在深度为6搜索情况下线程数为4的并行化搜索能加速2~3倍。这一点也是可以理解的因为负极大搜索的节点如果排序较好搜索量主要集中在PV路径的搜索上。简单的分裂根节点能提升的速度是可预见只有动态的分裂树把算力平摊到PV路径搜索加速PV路径产生能提高博弈树搜索的瓶颈。
尾记
这里实现并行化搜索还存在一些值得思考的问题如何能提高搜索的稳定性在发生截断返回时仍能正确的搜索到PV路径而不是会因为提前的不安全的剪枝与PV路径失之交臂。后面也希望有时间继续研究下如何高效的分裂树而不是盲目的根分裂。
