引子
多線程加快搜索速度這一認(rèn)知是經(jīng)受住實(shí)踐考驗(yàn)的。博弈樹(shù)搜索的并行搜索方式有很多種，例如葉子并行，根并行，樹(shù)分裂等算法。筆者給出一種實(shí)現(xiàn)起來(lái)比較簡(jiǎn)單的根并行算法。
在是實(shí)現(xiàn)時(shí)需要注意兩點(diǎn)，第一，怎么安全的剪枝；第二，如何進(jìn)行線程間的通信。對(duì)于AB剪枝有三點(diǎn)發(fā)現(xiàn)可以指導(dǎo)我們?cè)O(shè)計(jì)多線程的并行算法：
- 當(dāng)某一節(jié)點(diǎn)搜索完成，其分?jǐn)?shù)才能安全的更新父親節(jié)點(diǎn)的AB值。
- 一個(gè)節(jié)點(diǎn)的AB值可以安全的更新其所有子孫節(jié)點(diǎn)的AB值。
- 如果一個(gè)節(jié)點(diǎn)alpha >= beta, 這個(gè)節(jié)點(diǎn)可以安全的被剪枝
這樣一來(lái)，就可以知道一個(gè)節(jié)點(diǎn)搜索完成后，如何更新博弈樹(shù)所有節(jié)點(diǎn)的AB值，如何剪枝。通信方式使用的全局變量+讀寫(xiě)鎖控制的，全局變量保存所有節(jié)點(diǎn)狀態(tài)的AB值。當(dāng)搜索開(kāi)始，從根節(jié)點(diǎn)沿著搜索路徑開(kāi)始更新沿路的所有節(jié)點(diǎn)AB值，然后從全局變量中讀取該節(jié)點(diǎn)的AB值。搜索完成后，更新父親節(jié)點(diǎn)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已經(jīng)更新，false表示沒(méi)更新
bool getAlphaBeta(int &aalpha, int &abeta);
bool updateLeaf2RootAlphaBeta(int score);
//返回值:true已經(jīng)更新，false表示沒(méi)更新
bool updateRoot2LeafAlphaBeta(int aalpha, int abeta);
};
//并行化搜索技術(shù)
static QReadWriteLock parallelSearchTableLock;
static QHash<quint64, parallelNABSearchNode> parallelSearchTable;
函數(shù)實(shí)現(xiàn)三個(gè)方法，一個(gè)getAlphaBeta(int &aalpha, int &abeta)是從全局變量中獲取AB值，一個(gè)updateLeaf2RootAlphaBeta是從更新該節(jié)點(diǎn)的父親的AB值，還有一個(gè)updateRoot2LeafAlphaBeta是更新兒子節(jié)點(diǎn)的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;
}
實(shí)現(xiàn)
現(xiàn)在已經(jīng)實(shí)現(xiàn)了線程間通信的工具，只需要在搜索時(shí)調(diào)用這些利器就可以了，總體的實(shí)現(xiàn)思路和常規(guī)負(fù)極大搜索如出一撤。為了能后續(xù)兼容樹(shù)分裂的算法，這里給出了并行化搜索指定深度的接口。
//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);
// 更新根節(jié)點(diǎn)->當(dāng)前節(jié)點(diǎn)搜索路徑上AB值
for(int pid = 0;pid < parallelSsearchHistoryPlayersHash.size() - 1; ++pid){
//表項(xiàng)不存在會(huì)自動(dòng)調(diào)用默認(rèn)構(gòu)造函數(shù)
parallelNABSearchNode *curNode = &globalParam::parallelSearchTable[parallelSsearchHistoryPlayersHash[pid]];
parallelNABSearchNode *sontNode = &globalParam::parallelSearchTable[parallelSsearchHistoryPlayersHash[pid + 1]];
//更新下一層的AB值
sontNode->updateRoot2LeafAlphaBeta(- curNode->beta, - curNode->alpha);
}
// 獲取當(dāng)前AB值
globalParam::parallelSearchTable[zobristSearchHash.hash()].getAlphaBeta(alpha, beta);
// // 更新AB值后可能引發(fā)剪枝
// if(alpha >= beta){ // AB剪枝
// aiCalInfo.cutTreeTimesCurrentTurn ++;
// return beta;
// }
writeLock.unlock();
//探查置換表中值
if(zobristSearchHash.getNABTranspositionTable(score, depth, alpha, beta)) {
return score;
}
// ??或 分?jǐn)?shù)過(guò)大過(guò)小
// if (qAbs(score) > globalParam::utilGameSetting.MaxScore){
// //保存置換表
// return score;
// }
int evalPlayer = globalParam::AIPlayer;
MPlayerType searchPlayer = maximizingPlayer ? evalPlayer : UtilReservePlayer(evalPlayer);
// 達(dá)到搜索深度
if (depth == 0 || checkSearchBoardWiner() != PLAYER_NONE){
//保存置換表
score = evaluateBoard(evalPlayer);//負(fù)極大搜索中評(píng)估必須searchPlayer
if(!maximizingPlayer) score *= -1;
// //VCF
// QList<MPoint> 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;
}
// 著法生成
QVector<MPoint> 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;
//更新當(dāng)前層的AB值
writeLock.relock();
parallelNABSearchNode *curNode = &globalParam::parallelSearchTable[zobristSearchHash.hash()];
curNode->alpha = scoreBest;
writeLock.unlock();
}
}
}
}
// writeLock.relock();
// //更新當(dāng)前層的AB值
// parallelNABSearchNode *curNode = &globalParam::parallelSearchTable[zobristSearchHash.hash()];
// curNode->alpha = scoreBest;
// writeLock.unlock();
writeLock.relock();
//更新上一層的AB值：只有當(dāng)前所有節(jié)點(diǎn)搜索完成后，得到的值才是可靠的，才能用來(lái)更新父親節(jié)點(diǎn)的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;
}
結(jié)果
這里實(shí)現(xiàn)的并行化搜索效果并不出眾，只能說(shuō)是有一定效果。在深度為6搜索情況下，線程數(shù)為4的并行化搜索能加速2~3倍。這一點(diǎn)也是可以理解的，因?yàn)樨?fù)極大搜索的節(jié)點(diǎn)如果排序較好，搜索量主要集中在PV路徑的搜索上。簡(jiǎn)單的分裂根節(jié)點(diǎn)能提升的速度是可預(yù)見(jiàn)，只有動(dòng)態(tài)的分裂樹(shù)，把算力平攤到PV路徑搜索，加速PV路徑產(chǎn)生能提高博弈樹(shù)搜索的瓶頸。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-789385.html
尾記
這里實(shí)現(xiàn)并行化搜索還存在一些值得思考的問(wèn)題，如何能提高搜索的穩(wěn)定性，在發(fā)生截?cái)喾祷貢r(shí)，仍能正確的搜索到PV路徑，而不是會(huì)因?yàn)樘崆暗牟话踩募糁εcPV路徑失之交臂。后面也希望有時(shí)間繼續(xù)研究下如何高效的分裂樹(shù)，而不是盲目的根分裂。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-789385.html
到了這里，關(guān)于基于博弈樹(shù)的開(kāi)源五子棋AI教程[7 多線程搜索]的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
