一种序贯同步博弈的双树蒙特卡洛搜索算法

摘要

本发明公开了一种用于解决大规模序贯同步博弈问题的双树蒙特卡洛搜索算法，相比于单树结构的序贯同步蒙特卡洛搜索，在保留同步特点的基础上，建立两棵树表示博弈双方的状态转移情况，使得博弈树的选择分支大大减少，在维持同步行动特点的同时，减小了博弈树的规模。消除了同步动作造成的双方动作组合爆炸问题，增加搜索深度，既保证了求解质量，又提高了求解效率。具体的技术手段包括：通过构建纳什均衡支撑库，解决同步的纳什均衡在线计算时间过长的问题；设计序贯同步博弈的深度策略网和深度估值网，实现序贯同步搜索的知识引导；研究面向环境的强化学习，解决状态转移或收益缺失下的决策问题。