基于博弈树的开源五子棋AI教程[7 多线程搜索]

文章目录

  • 引子
  • 定义
  • 实现
  • 结果
  • 尾记

引子

多线程加快搜索速度这一认知是经受住实践考验的。博弈树搜索的并行搜索方式有很多种，例如叶子并行，根并行，树分裂等算法。笔者给出一种实现起来比较简单的根并行算法。
在是实现时需要注意两点，第一，怎么安全的剪枝；第二，如何进行线程间的通信。对于AB剪枝有三点发现可以指导我们设计多线程的并行算法：

  1. 当某一节点搜索完成，其分数才能安全的更新父亲节点的AB值。
  2. 一个节点的AB值可以安全的更新其所有子孙节点的AB值。
  3. 如果一个节点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 QHash<quint64, 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);//负极大搜索中评估必须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;

                    //更新当前层的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路径失之交臂。后面也希望有时间继续研究下如何高效的分裂树，而不是盲目的根分裂。


http://www.niftyadmin.cn/n/5322989.html

相关文章

c 小熊猫 c++ IDE编译ffmpeg 设置

c 小熊猫 c++ IDE编译ffmpeg 设置

菜单-》运行-》编译器选项-》链接时加入下列选项 &#xff1a; -I /usr/local/ffmpeg/include -L /usr/local/ffmpeg/lib -lavformat -lavdevice -lavfilter -lavcodec -lavutil -lswscale -lswresample -lm 本机ffmpeg存储位置&#xff1a;include &#xff1a;/usr/local/ff…
阅读更多...
约瑟夫环问题解决

约瑟夫环问题解决

链表 struct List {int data;struct List* next; }创建链表 单链表 实现 struct List* listCreate() {int data;struct List* head NULL;struct List* pre NULL;struct List* current NULL;while(scanf("%d",&data) && data ! -1){current (stru…
阅读更多...
六、新建窗体时，几种窗体的区别

六、新建窗体时，几种窗体的区别

新建窗体时&#xff0c;会有几种类型的选项&#xff0c;很多同学不明白其中的意思&#xff0c;我们在本章节中详细介绍一下几种窗体的区别。 窗体的类型分以下几种 Dialog with Buttons Bottom 带按钮的对话框&#xff0c;按钮在底部 Dialog with Buttons Right 带按钮的对话框…
阅读更多...
在centos系统安装mqtt

在centos系统安装mqtt

在CentOS系统上安装MQTT&#xff0c;通常意味着要安装一个MQTT代理&#xff08;broker&#xff09;&#xff0c;比如Mosquitto。下面是在CentOS上安装Mosquitto的步骤&#xff1a; 添加EPEL仓库&#xff1a; 由于Mosquitto可能不在CentOS默认的Yum仓库中&#xff0c;你可能需要…
阅读更多...
华为设备vlan下配置MSTP，STP选举

华为设备vlan下配置MSTP，STP选举

核心代码,不同实例&#xff0c;承载不同流量&#xff0c;为每个实例设置一个根网桥达到分流的效果 stp region-config //进入stp区域的设置 region-name R1 //区域命名为R1 instance 1 vlan 10 …
阅读更多...
SpringCloud：微服务

SpringCloud：微服务

文章目录 微服务服务架构演变单例架构&#xff08;集中式架构&#xff09;分布式架构 微服务SpringCloud 微服务 服务架构演变 单例架构&#xff08;集中式架构&#xff09; 单例架构&#xff1a; 将业务的所有功能集中在一个项目中开发&#xff0c;打成一个包部署 优点&…
阅读更多...
小程序基础学习（js混编）

小程序基础学习（js混编）

在组件中使用外部js代码实现数据改变 先创建js文件 编写一些组件代码 编写外部js代码 在组件的js中引入外部js 在 app.json中添加路径规则 组件代码 <!--components/my-behavior/my-behavior.wxml--> <view><view>当前计数为{{count}}</view> <v…
阅读更多...
wsl(ubuntu22)安装mysql

wsl(ubuntu22)安装mysql

wsl安装mysql 参考链接 首先换源&#xff0c;清华镜像为链接sudo apt-get update sudo apt-get upgrade安装mysql依赖sudo apt install mysql-server sudo apt install libmysqlclient-dev// 执行安全安装 sudo mysql_secure_installation// 启动MySQL服务 sudo systemctl sta…
阅读更多...
最新文章

Copyright @ 2022~2023