基于Expectimax搜索与Double DQN的非完备信息博弈算法

• 作者: 雷捷维 王嘉旸 任航 闫天伟 黄伟
• 来源期刊: 计算机工程
• 关键词: Double DQN算法 Expectimax搜索 非完备信息博弈 麻将 强化学习
• 年，卷（期）: 2021,（3）
• 所属期刊栏目: 开发研究与工程应用|Development Research and Engineering Application
• 页码范围: 304-310,320
• 页数: 8页
• 分类号: TP183
• 语种: 中文
• DOI: 10.19678/j.issn.1000-3428.0057309

摘要

麻将作为典型的非完备信息博弈游戏主要通过传统Expectimax搜索算法实现,其剪枝策略与估值函数基于人工先验知识设计,存在假设不合理等问题.提出一种结合Expectimax搜索与Double DQN强化学习算法的非完备信息博弈算法.在Expectimax搜索树扩展过程中,采用Double DQN输出的估值设计估值函数并在限定搜索层数内获得分支估值,同时设计剪枝策略对打牌动作进行排序与部分扩展实现搜索树剪枝.在Double DQN模型训练过程中,将麻将信息编码为特征数据输入神经网络获得估值,使用Expectimax搜索算法得到最优动作以改进探索策略.实验结果表明,与Expectimax搜索算法、Double DQN算法等监督学习算法相比,该算法在麻将游戏上胜率与得分更高,具有更优异的博弈性能.