面向通用博弈系统的策略表示与推理研究

General Game Playing (GGP) is a research project launched by Stanford University in 2005. It aims to develop a game player with general intelligence that is able to play more than one game successfully. As an important AI research area, the main challenge of GGP is how to build an efficient general game player, which can understand the rules of arbitrary games and learn to play these games effectively without human intervention. Strategy representation and reasoning is a core technique to build such a general game player. Based on the GGP platform, this project focuses on the study of strategy representation and reasoning for general game players. The main contents include: .1) Establish a unified logic theory for game description, strategy representation and reasoning, and study its logical properties such as soundness, proof theory and complexity..2) Investigate effective tools for representing and reasoning about dynamic information and uncertainty during the game, develop model-checking algorithms for a general game player to automatically verify game properties, and study automatic reasoning techniques..3) Design strategy generation algorithms based on game rules, and develop search algorithms to support efficient decision-making for general game players. .The results of this project can be applied to other areas, bringing today's AI systems to a new level of generality. They can also promote the development of the theory and techniques of General Artificial Intelligence.

全局博弈策略(GGP)是由斯坦福大学在2005年发起的研究项目，旨在研发具有通用性智能的博弈系统。作为人工智能的重要研究领域，GGP研究目前所面临的主要挑战是如何构造高效的通用博弈系统，使其能够自主学习任意给定的博弈规则，并自动生成有效的博弈策略。策略表示与推理是构建通用博弈系统的关键。为此，本项目将基于GGP平台研究通用博弈系统的策略表示与推理机制设计。主要内容包括：1) 构建用于博弈描述、策略表示与推理的统一逻辑框架，并研究其可靠性、复杂性、证明论等系统性质。2）研究处理博弈过程中信息动态化和不确定性的知识表示与推理的有效工具，开发通用博弈系统自动验证博弈性质的模型检测算法以及自动推理技术。3）探究基于博弈规则的策略生成算法，设计支持通用博弈系统进行高效智能决策的搜索算法。本研究成果可广泛用于提高当今经济、社会等领域人工智能系统的通用性水平，有助于推动通用人工智能理论与技术的发展。

作为人工智能的重要研究领域，全局博弈策略 (General Game Playing, GGP) 旨在研发具有通用性智能的博弈系统，使其能够成功地基于博弈规则进行任意已知或未知的博弈。GGP研究的主要问题是如何构造高效的通用博弈系统，使其能够自主学习任意给定的博弈规则，并自动生成有效的博弈策略。针对这一问题，本项目系统地研究了通用博弈系统策略推理的逻辑基础与高效策略生成算法。主要研究内容包括：（1）通过自下而上的方式构建了用于（非）完美信息博弈描述、策略表示与推理的统一逻辑系统，并研究了它们的语言表达力，计算复杂性，公理化等元性质。研究结果表明，与同类策略逻辑相比，这些逻辑系统实现了语言表达力与计算复杂性的良好均衡；（2）针对所构建的逻辑系统，研发了具有良好复杂度的模型检测算法来自动验证博弈和策略的性质；同时，基于所建立的语义理论和证明论系统，设计了有效的推理机制，使博弈主体能够基于给定的博弈规则自动推导出博弈状态上的重要决策信息，并对其认知状态以及策略推理实现精细刻画；（3）深入分析了主流通用策略生成算法蒙特卡洛树搜索算法（MCTS）及其变种所具有的状态评估方差大、不稳定等问题，利用相似状态共享信息的泛化思想，通过在MCTS基础上设计了记忆存储结构来记录状态的特征信息，并基于这些记忆生成在线近似值，有效地提高了状态模拟估值的准确性，提升了MCTS的性能表现；（4）通过整合所研发的模型检测算法，带记忆结构的MCTS算法和深度强化学习算法，特别是AlphaZero的广义深度强化学习算法构建了通用博弈系统，并基于GGP平台对所构建的通用博弈系统在不同类型的多个博弈上进行了全面的性能评估。实验结果表明，与基准系统相比，所构建的通用博弈系统无论在决策水平还是效率上都有了显著的提升。项目组已在国际人工智能顶级期刊 Artificial Intelligence，顶级会议IJCAI和AAAI上发表论文3篇; 此外，有1篇论文已被AAAI-2022接收录用。