基于游戏树搜索算法的决策模型数据处理方法及系统

摘要

本发明公开了一种基于游戏树搜索算法的决策模型数据处理方法及系统，该方法包括：在游戏树搜索算法的剪枝策略的设计过程中，利用双深度Q学习算法模型预估在当前出牌决策中出每张牌对应的分数，选择预估得分大于或等于分数阈值的出牌动作来扩展游戏树；在游戏树搜索算法的估值函数的设计过程中，若游戏树搜索算法能够在限定时间内搜索到游戏终局，则将估值函数设置为游戏终局能够获取到的游戏得分，若游戏树搜索算法不能在限定时间内搜索到游戏终局，则利用双深度Q学习算法模型计算当前游戏节点的每个动作的预估分数，并将预估分数的最大值作为估值函数的值。本发明能够在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统。

说明书

技术领域

本发明涉及计算机数据处理技术领域，特别是涉及一种基于游戏树搜索算法的决策模型数据处理方法及系统。

背景技术

对决策模型中涉及的数据进行数据处理是构建决策模型的前提，以麻将为例，麻将决策模型是先在当前麻将游戏中获取一些数据信息（包括手牌、副露、对手的副露、弃牌、庄家位置等），通过对这些数据信息进行一定的处理，进行合理的决策动作，从而追求在麻将游戏中赢取更多的分数。在麻将游戏中，决策主要包括出牌决策与吃碰杠决策。

目前关于智能麻将决策模型的构建主要是应用了游戏树搜索算法（ExpectimaxSearch）来实现。在2008年，T.Lin根据在每轮决策中结合运用Expectimax Search算法与动态规划设计了麻将程序LongCat。该程序通过在搜索的过程追求向听数的减少，以此获得较高的胜率。在2015年，相关技术人员提出了“转张”的概念来改进以前的LongCat程序，以此来追求更高的胜率。但是在麻将游戏的对局中，追求更高的得分比更高的胜率显得更重要，然而目前基于Expectimax Search算法的模型都没有很好地解决这一问题。除此之外，目前Expectimax Search算法的剪枝策略和估值函数都要依赖于人工先验知识进行设计，这难免会引入设计者自身理解的偏差。

此外，日本东京大学Naoki Mizukami and Yoshimasa Tsuruoka团队在2006~2016年，基于日本麻将规则，成功开发了日麻AI“爆打”，应用在日本天凤麻将平台。该技术方案使用的是传统的机器学习算法，通过收集人类在麻将中对打的大量数据，来训练麻将智能决策模型。这种方法的实现需要大量专业玩家的高水平对战数据，对于刚上线、用户量不多的游戏平台则无能为力。

发明内容

为此，本发明的一个目的在于提出一种基于游戏树搜索算法的决策模型数据处理方法，以在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统。

本发明提供一种基于游戏树搜索算法的决策模型数据处理方法，包括：

在游戏树搜索算法的剪枝策略的设计过程中，利用双深度Q学习算法模型预估在当前出牌决策中出每张牌对应的分数，选择预估得分大于或等于分数阈值的出牌动作来扩展游戏树，以得到对游戏树进行剪枝的结果；

在游戏树搜索算法的估值函数的设计过程中，若游戏树搜索算法能够在限定时间内搜索到游戏终局，则将估值函数设置为游戏终局能够获取到的游戏得分，若游戏树搜索算法不能在限定时间内搜索到游戏终局，则利用双深度Q学习算法模型计算当前游戏节点的每个动作的预估分数，并将预估分数的最大值作为估值函数的值。

根据本发明提供的基于游戏树搜索算法的决策模型数据处理方法，结合了双深度Q学习算法（Double Deep Q Network，简称Double DQN）与游戏树搜索算法，利用DoubleDQN弥补了Expectimax Search算法在剪枝策略设计、估值函数设计的不足，能够在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统，与现有技术相比，本发明具有以下有益效果：

1、本发明不需要大量的高水平玩家用户数据进行训练，具有更好的普适性以及更高的商业价值，由于在实际商业运用的过程中，很多游戏公司需要在刚上线的游戏内配置高水平的AI，但是由于没有积累足够多的用户数据，所以很难利用监督学习方法构建AI，相比之下，本发明可以解决这种问题，更好的普适性。

2、本发明在计算方面耗时更少，响应速度更快。相比于传统的Expectimax Search算法，由于本发明结合了Double DQN进行剪枝的缘故，在响应速度方面具有更明显的优势。比如说，游戏树同样在往下搜索两层的情况下，传统的Expectimax Search算法需要耗时6.778s来完成计算，而本发明只需0.068s就能完成相同的计算。

3、本发明构建的模型具有更高的胜率以及胡牌得分。相比于传统的ExpectimaxSearch算法，本发明利用强化学习算法Double DQN改进了以往算法存在的一些不足，从而使模型的胜率与得分都有了进一步的提升。

另外，根据本发明上述的基于游戏树搜索算法的决策模型数据处理方法，还可以具有如下附加的技术特征：

进一步地，在游戏树搜索算法的剪枝策略的设计过程中，对于预估得分小于分数阈值的出牌动作不予考虑。

进一步地，在游戏树搜索算法的剪枝策略的设计过程中，利用双深度Q学习算法模型预估在当前出牌决策中出每张牌对应的分数，选择预估得分大于或等于分数阈值的出牌动作来扩展游戏树，以得到对游戏树进行剪枝的结果的步骤具体包括：

获取当前出牌决策状态信息；

将当前出牌决策状态信息输入至双深度Q学习算法模型中，以计算出每张牌对应的预估得分；

将双深度Q学习算法模型计算的预估得分降序排序，选择预估得分排前k个的出牌动作，以得到对游戏树进行剪枝的结果，其余的出牌动作不予考虑，作剪枝处理。

进一步地，所述决策模型为麻将决策模型，在游戏树搜索算法的估值函数的设计过程中，若游戏树搜索算法能够在限定时间内搜索到游戏终局，则将估值函数设置为游戏终局能够获取到的游戏得分，若游戏树搜索算法不能在限定时间内搜索到游戏终局，则利用双深度Q学习算法模型计算当前游戏节点的每个动作的预估分数，并将预估分数的最大值作为估值函数的值的步骤具体包括：

获取当前出牌决策状态下的麻将场面信息；

根据当前出牌决策状态下的麻将场面信息确定当前节点的类型是抓牌节点还是出牌节点；

根据当前节点的类型将当前节点往下展开若干层游戏树进行计算，对于没有达到终局的情况，将双深度Q学习算法模型的拟合值作为当前节点的分数，对于到达终局的情况，则将当前游戏分数作为当前节点的分数。

进一步地，所述麻将场面信息包括手牌信息、副露信息、弃牌信息。

本发明的另一个目的在于提出一种基于游戏树搜索算法的决策模型数据处理系统，以在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统。

本发明提供一种基于游戏树搜索算法的决策模型数据处理系统，包括：

剪枝策略设计模块，用于在游戏树搜索算法的剪枝策略的设计过程中，利用双深度Q学习算法模型预估在当前出牌决策中出每张牌对应的分数，选择预估得分大于或等于分数阈值的出牌动作来扩展游戏树，以得到对游戏树进行剪枝的结果；

估值函数设计模块，用于在游戏树搜索算法的估值函数的设计过程中，若游戏树搜索算法能够在限定时间内搜索到游戏终局，则将估值函数设置为游戏终局能够获取到的游戏得分，若游戏树搜索算法不能在限定时间内搜索到游戏终局，则利用双深度Q学习算法模型计算当前游戏节点的每个动作的预估分数，并将预估分数的最大值作为估值函数的值。

根据本发明提供的基于游戏树搜索算法的决策模型数据处理系统，结合了双深度Q学习算法（Double Deep Q Network，简称Double DQN）与游戏树搜索算法，利用DoubleDQN弥补了Expectimax Search算法在剪枝策略设计、估值函数设计的不足，能够在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统，与现有技术相比，本发明具有以下有益效果：

1、本发明不需要大量的高水平玩家用户数据进行训练，具有更好的普适性以及更高的商业价值，由于在实际商业运用的过程中，很多游戏公司需要在刚上线的游戏内配置高水平的AI，但是由于没有积累足够多的用户数据，所以很难利用监督学习方法构建AI，相比之下，本发明可以解决这种问题，更好的普适性。

2、本发明在计算方面耗时更少，响应速度更快。相比于传统的Expectimax Search算法，由于本发明结合了Double DQN进行剪枝的缘故，在响应速度方面具有更明显的优势。比如说，游戏树同样在往下搜索两层的情况下，传统的Expectimax Search算法需要耗时6.778s来完成计算，而本发明只需0.068s就能完成相同的计算。

3、本发明构建的模型具有更高的胜率以及胡牌得分。相比于传统的ExpectimaxSearch算法，本发明利用强化学习算法Double DQN改进了以往算法存在的一些不足，从而使模型的胜率与得分都有了进一步的提升。

另外，根据本发明上述的基于游戏树搜索算法的决策模型数据处理系统，还可以具有如下附加的技术特征：

进一步地，所述剪枝策略设计模块在游戏树搜索算法的剪枝策略的设计过程中，对于预估得分小于分数阈值的出牌动作不予考虑。

进一步地，所述剪枝策略设计模块具体用于：

获取当前出牌决策状态信息；

将当前出牌决策状态信息输入至双深度Q学习算法模型中，以计算出每张牌对应的预估得分；

将双深度Q学习算法模型计算的预估得分降序排序，选择预估得分排前k个的出牌动作，以得到对游戏树进行剪枝的结果，其余的出牌动作不予考虑，作剪枝处理。

进一步地，所述决策模型为麻将决策模型，所述估值函数设计模块具体用于：

获取当前出牌决策状态下的麻将场面信息；

根据当前出牌决策状态下的麻将场面信息确定当前节点的类型是抓牌节点还是出牌节点；

根据当前节点的类型将当前节点往下展开若干层游戏树进行计算，对于没有达到终局的情况，将双深度Q学习算法模型的拟合值作为当前节点的分数，对于到达终局的情况，则将当前游戏分数作为当前节点的分数。

进一步地，所述麻将场面信息包括手牌信息、副露信息、弃牌信息。

本发明还提出一种可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述方法的步骤。

本发明还提出一种计算机设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述方法的步骤。

本发明的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本发明的实施例了解到。

附图说明

本发明实施例的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：

图1是根据本发明一实施例的基于游戏树搜索算法的决策模型数据处理方法的流程图；

图2是图1中步骤S101的详细流程图；

图3是图1中步骤S102的详细流程图；

图4是根据本发明一实施例的基于游戏树搜索算法的决策模型数据处理系统的结构框图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

请参阅图1，本发明一实施例提出的基于游戏树搜索算法的决策模型数据处理方法，包括步骤S101~S102。

S101，在游戏树搜索算法的剪枝策略的设计过程中，利用双深度Q学习算法模型预估在当前出牌决策中出每张牌对应的分数，选择预估得分大于或等于分数阈值的出牌动作来扩展游戏树，以得到对游戏树进行剪枝的结果。

本实施例中，以麻将为例进行说明，需要指出的，在用搜索算法构建麻将决策模型时，会展开成一颗游戏树。剪枝策略是为了减少游戏树的分支，而估值函数是用来计算当前节点每个决策动作的预估游戏得分。剪枝策略的作用其实就是为了改进搜索过程，使算法能够有更多的时间往下进行搜索，从而计算更准确的游戏得分，从而改进估值函数的准确性。游戏树搜索的时候一般往下搜索若干层，在每层中首先进行剪枝，然后再用估值函数算出每个动作的预估得分。

其中，在游戏树搜索算法的剪枝策略的设计过程中，对于预估得分小于分数阈值的出牌动作不予考虑。

具体的，请参阅图2，步骤S101具体包括：

S1011，获取当前出牌决策状态信息；

S1012，将当前出牌决策状态信息输入至双深度Q学习算法模型中，以计算出每张牌对应的预估得分；

S1013，将双深度Q学习算法模型计算的预估得分降序排序，选择预估得分排前k个的出牌动作，以得到对游戏树进行剪枝的结果，其余的出牌动作不予考虑，作剪枝处理。

例如，当前手牌为12378w，666t，1345s，中白，无副露，对当前场面信息特征编码输入Double DQN模型得出当前每一个手牌的评估值，对评估值降序排序后中、白、78w一般情况下会排在前面，对前k个出牌动作展开进行搜索，对其他手牌不予考虑，作剪枝处理。

S102，在游戏树搜索算法的估值函数的设计过程中，若游戏树搜索算法能够在限定时间内搜索到游戏终局，则将估值函数设置为游戏终局能够获取到的游戏得分，若游戏树搜索算法不能在限定时间内搜索到游戏终局，则利用双深度Q学习算法模型计算当前游戏节点的每个动作的预估分数，并将预估分数的最大值作为估值函数的值。

其中，在基于Expectimax搜索的麻将决策过程中，需要把一次抓牌节点和下一层出牌节点看成是游戏树的一层，对于抓牌节点，估值函数的值等于其所有子节点分数的加权平均值，对于出牌节点，估值函数的值等于其所有子节点的最大分数。但在有限的时间内，往往无法完全搜索整棵游戏树。所以在发明中，通过改进的算法，限制了游戏树的搜索层数。对于游戏树中节点的分数，如果在没有达到终局的情况，是获取不了具体分数的。这时候就用Double DQN模型的拟合值作为当前节点的分数。

具体的，所述决策模型为麻将决策模型，请参阅图3，步骤S102具体包括：

S1021，获取当前出牌决策状态下的麻将场面信息；

其中，所述麻将场面信息包括手牌信息、副露信息、弃牌信息等。

S1022，根据当前出牌决策状态下的麻将场面信息确定当前节点的类型是抓牌节点还是出牌节点；

S1023，根据当前节点的类型将当前节点往下展开若干层游戏树进行计算，对于没有达到终局的情况，将双深度Q学习算法模型的拟合值作为当前节点的分数，对于到达终局的情况，则将当前游戏分数作为当前节点的分数。

其中，以当前节点的手牌为起点，向下展开所有可能打出的牌，以及打出这张牌后所有可能摸到的牌，以此递归，当手牌达到胡牌状态时，就是搜索到游戏的终局，也是在此次搜索中的所有叶子节点。

通过用自博弈的方式以每局的得分作为奖励信号训练的Double DQN模型，可以抽象成一个估值函数，能够较为准确地预测出每一个节点的价值，而当节点是处在游戏的终局时，就可以把游戏终局的游戏得分作为当前节点的估值函数的输出值。

每个动作的得分可以理解为在执行该动作后的游戏终局的分数。而预估分数是指利用Double DQN模型来训练拟合执行每个动作后可能的游戏分数。那么在模型训练完后，就可以通过模型来算出当前节点执行不同动作的相应分数。

需要先获取当前出牌决策状态下的场面信息，包括手牌、副露、弃牌等信息，对这些信息进行特征编码，再把编码过后的信息输入到Double DQN模型中通过计算就可以输出每个动作的预估分数。

下表列出了本发明构建的模型与传统方法胜率和得分的比较。

上表中，Linear、SVM、FC、CNN、DenseNet、ResNet都是监督学习模型，DQN与DoubleDQN是强化学习模型。从上表可以看出，本发明相比于其他模型具有更高的胜率以及得分。

综上，根据本实施例提供的基于游戏树搜索算法的决策模型数据处理方法，结合了双深度Q学习算法（Double Deep Q Network，简称Double DQN）与游戏树搜索算法，利用Double DQN弥补了Expectimax Search算法在剪枝策略设计、估值函数设计的不足，能够在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统，与现有技术相比，本发明具有以下有益效果：

1、本发明不需要大量的高水平玩家用户数据进行训练，具有更好的普适性以及更高的商业价值，由于在实际商业运用的过程中，很多游戏公司需要在刚上线的游戏内配置高水平的AI，但是由于没有积累足够多的用户数据，所以很难利用监督学习方法构建AI，相比之下，本发明可以解决这种问题，更好的普适性。

2、本发明在计算方面耗时更少，响应速度更快。相比于传统的Expectimax Search算法，由于本发明结合了Double DQN进行剪枝的缘故，在响应速度方面具有更明显的优势。比如说，游戏树同样在往下搜索两层的情况下，传统的Expectimax Search算法需要耗时6.778s来完成计算，而本发明只需0.068s就能完成相同的计算。

3、本发明构建的模型具有更高的胜率以及胡牌得分。相比于传统的ExpectimaxSearch算法，本发明利用强化学习算法Double DQN改进了以往算法存在的一些不足，从而使模型的胜率与得分都有了进一步的提升。

请参阅图4，本发明一实施例提出的基于游戏树搜索算法的决策模型数据处理系统，包括：

剪枝策略设计模块，用于在游戏树搜索算法的剪枝策略的设计过程中，利用双深度Q学习算法模型预估在当前出牌决策中出每张牌对应的分数，选择预估得分大于或等于分数阈值的出牌动作来扩展游戏树，以得到对游戏树进行剪枝的结果；

估值函数设计模块，用于在游戏树搜索算法的估值函数的设计过程中，若游戏树搜索算法能够在限定时间内搜索到游戏终局，则将估值函数设置为游戏终局能够获取到的游戏得分，若游戏树搜索算法不能在限定时间内搜索到游戏终局，则利用双深度Q学习算法模型计算当前游戏节点的每个动作的预估分数，并将预估分数的最大值作为估值函数的值。

本实施例中，所述剪枝策略设计模块在游戏树搜索算法的剪枝策略的设计过程中，对于预估得分小于分数阈值的出牌动作不予考虑。

本实施例中，所述剪枝策略设计模块具体用于：

获取当前出牌决策状态信息；

将当前出牌决策状态信息输入至双深度Q学习算法模型中，以计算出每张牌对应的预估得分；

将双深度Q学习算法模型计算的预估得分降序排序，选择预估得分排前k个的出牌动作，以得到对游戏树进行剪枝的结果，其余的出牌动作不予考虑，作剪枝处理。

本实施例中，所述决策模型为麻将决策模型，所述估值函数设计模块具体用于：

获取当前出牌决策状态下的麻将场面信息；

根据当前出牌决策状态下的麻将场面信息确定当前节点的类型是抓牌节点还是出牌节点；

根据当前节点的类型将当前节点往下展开若干层游戏树进行计算，对于没有达到终局的情况，将双深度Q学习算法模型的拟合值作为当前节点的分数，对于到达终局的情况，则将当前游戏分数作为当前节点的分数。

本实施例中，所述麻将场面信息包括手牌信息、副露信息、弃牌信息。

根据本实施例提供的基于游戏树搜索算法的决策模型数据处理系统，结合了双深度Q学习算法（Double Deep Q Network，简称Double DQN）与游戏树搜索算法，利用DoubleDQN弥补了Expectimax Search算法在剪枝策略设计、估值函数设计的不足，能够在没有大量高质量玩家数据的情况下，构建高水平的智能决策系统，与现有技术相比，本发明具有以下有益效果：

1、本发明不需要大量的高水平玩家用户数据进行训练，具有更好的普适性以及更高的商业价值，由于在实际商业运用的过程中，很多游戏公司需要在刚上线的游戏内配置高水平的AI，但是由于没有积累足够多的用户数据，所以很难利用监督学习方法构建AI，相比之下，本发明可以解决这种问题，更好的普适性。

2、本发明在计算方面耗时更少，响应速度更快。相比于传统的Expectimax Search算法，由于本发明结合了Double DQN进行剪枝的缘故，在响应速度方面具有更明显的优势。比如说，游戏树同样在往下搜索两层的情况下，传统的Expectimax Search算法需要耗时6.778s来完成计算，而本发明只需0.068s就能完成相同的计算。

3、本发明构建的模型具有更高的胜率以及胡牌得分。相比于传统的ExpectimaxSearch算法，本发明利用强化学习算法Double DQN改进了以往算法存在的一些不足，从而使模型的胜率与得分都有了进一步的提升。

此外，本发明的实施例还提出一种可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现上述实施例中所述方法的步骤。

此外，本发明的实施例还提出一种计算机设备，包括存储器、处理器以及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述程序时实现上述实施例中所述方法的步骤。

在流程图中表示或在此以其他方式描述的逻辑和/或步骤，例如，可以被认为是用于实现逻辑功能的可执行指令的定序列表，可以具体实现在任何计算机可读介质中，以供指令执行系统、装置或设备（如基于计算机的系统、包括处理器的系统或其他可以从指令执行系统、装置或设备取指令并执行指令的系统）使用，或结合这些指令执行系统、装置或设备而使用。就本说明书而言，“计算机可读介质”可以是任何可以包含、存储、通信、传播或传输程序以供指令执行系统、装置或设备或结合这些指令执行系统、装置或设备而使用的装置。

计算机可读介质的更具体的示例（非穷尽性列表）包括以下：具有一个或多个布线的电连接部（电子装置），便携式计算机盘盒（磁装置），随机存取存储器（RAM），只读存储器（ROM），可擦除可编辑只读存储器（EPROM或闪速存储器），光纤装置，以及便携式光盘只读存储器（CDROM）。另外，计算机可读介质甚至可以是可在其上打印所述程序的纸或其他合适的介质，因为可以例如通过对纸或其他介质进行光学扫描，接着进行编辑、解译或必要时以其他合适方式进行处理来以电子方式获得所述程序，然后将其存储在计算机存储器中。

应当理解，本发明的各部分可以用硬件、软件、固件或它们的组合来实现。在上述实施方式中，多个步骤或方法可以用存储在存储器中且由合适的指令执行系统执行的软件或固件来实现。例如，如果用硬件来实现，和在另一实施方式中一样，可用本领域公知的下列技术中的任一项或他们的组合来实现：具有用于对数据信号实现逻辑功能的逻辑门电路的离散逻辑电路，具有合适的组合逻辑门电路的专用集成电路，可编程门阵列（PGA），现场可编程门阵列（FPGA）等。

在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、 “示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本发明的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。

尽管已经示出和描述了本发明的实施例，本领域的普通技术人员可以理解：在不脱离本发明的原理和宗旨的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由权利要求及其等同物限定。