Regular Games -- an Automata-Based General Game Playing Language
Regular Games -- an Automata-Based General Game Playing Language
We propose a new General Game Playing (GGP) system called Regular Games (RG). The main goal of RG is to be both computationally efficient and convenient for game design. The system consists of several languages. The core component is a low-level language that defines the rules by a finite automaton. It is minimal with only a few mechanisms, which makes it easy for automatic processing (by agents, analysis, optimization, etc.). The language is universal for the class of all finite turn-based games with imperfect information. Higher-level languages are introduced for game design (by humans or Procedural Content Generation), which are eventually translated to a low-level language. RG generates faster forward models than the current state of the art, beating other GGP systems (Regular Boardgames, Ludii) in terms of efficiency. Additionally, RG's ecosystem includes an editor with LSP, automaton visualization, benchmarking tools, and a debugger of game description transformations.
Regular Games——基于自动机的通用博弈语言
我们提出了一种新的通用博弈语言系统，称为 Regular Games（RG）。RG 的主要目标是兼具计算效率和博弈设计的便捷性。该系统由多种语言构成，核心组件是通过有限自动机定义规则的低级语言。它仅包含少量机制，使自动处理（如代理、分析、优化等）变得简单。该语言适用于所有有限回合制博弈（含不完美信息）。为便于博弈设计（人类或程序内容生成），引入了高级语言，这些语言最终会被翻译为低级语言。RG 生成的前向模型比当前最先进的系统更快，比其他 GGP 系统（如 Regular Boardgames、Ludii）在效率上更优。此外，RG 生态系统包括带有 LSP 的编辑器、自动机可视化、基准测试工具和博弈描述转换调试器。
智能问答：
Q1: 这篇论文试图解决什么问题？
论文旨在解决“通用博弈（General Game Playing, GGP）”领域长期存在的两大矛盾：
表达力与效率的矛盾
传统逻辑型语言（GDL/GDL-II）能描述任意有限回合制博弈，但推理开销大，复杂游戏几乎无法实时运行；
专用快速系统（RBG、Ludii）虽能生成高效推理器，却要么受限完美信息、要么语言庞大封闭，难以扩展。
设计便利与自动处理的矛盾
高层语言（Ludii 的 ludeme、专用脚本）方便人类或 PCG 工具设计新游戏，但语法复杂、与底层推理引擎紧耦合；
极简语言（RBG 的正则表达式、GDL 的逻辑程序）利于自动分析与优化，却手写繁琐，且跨系统复用困难。
为此，作者提出 Regular Games（RG） 体系，目标是在“任意有限回合制博弈（含不完美信息与随机性）”这一最大语义范围内，同时实现：
运行时效率——生成比现有最快系统 RBG 还要快一个数量级的 C++ 推理器；
设计便利性——提供多层语言栈（HRG、领域专用 Python 库），让游戏描述比 GDL 简短、比 Ludii 更通用；
自动可处理性——底层仅基于极小核心（非确定有限自动机+变量赋值），便于静态分析、优化与跨系统翻译；
开放可扩展性——新高层语言只需翻译到 RG 即可复用整套工具链与优化管线，无需改动底层引擎。
简言之，论文试图用“自动机作为通用博弈汇编语言”的思路，一次性把“能描述任何有限博弈”“生成最快推理器”“方便人类设计”“可被算法自动优化”这四件事同时做成。
Q2: 有哪些相关研究？
以下研究被论文直接或间接引用，构成 Regular Games 工作的对照基准与技术来源。按主题分组，并给出关键文献出处（括号内为论文参考文献编号）。
1. 通用博弈语言与系统
GDL / GDL-II
Genesereth, Love, Pell 2005; Love et al. 2006; Thielscher 2010
逻辑编程语法，能描述任意有限、不完美信息、随机、同步移动博弈；推理靠逻辑归结，效率低。
Ludii
Piette et al. 2020; Browne et al. 2020; Soemers et al. 2024
基于“ludeme”的高层语言，内置千量级关键词，支持传统棋类与不完全信息；Java 实现，带位板优化，比 GDL 快但仍慢于 RBG。
Regular Boardgames (RBG)
Kowalski et al. 2019, 2020
极简正则表达式语法→编译为 C++ 推理器，当前最快，但仅完美信息、无随机性；复杂规则需冗长描述。
METAGAME
Pell 1992
早期象棋类通用系统，用 Lisp 宏描述对称棋类。
Simplified Boardgames
Björnsson 2012
轻量级语法，专注从示例学习规则。
Video Game Description Language (VGDL)
Perez et al. 2016
专用于 Atari-like 街机游戏的二维网格语言。
2. 通用博弈平台 / 框架（非语言）
OpenSpiel
Lanctot et al. 2019
C++/Python 统一接口，收录百余游戏，供强化学习研究，但每款游戏需手工实现。
Polygames
Facebook AI Research 2020
基于 Torch 的自对弈框架，支持多种棋类，同样需逐游戏实现。
Ai Ai
Tavener 2025
Java 编写的通用博弈平台，侧重棋类 AI 基准。
GBG (General Board Game)
Konen 2019
教学用 Java 框架，可插拔游戏规则模块。
3. 自动机与正则技术在博弈描述中的应用
Thompson 构造
Thompson 1968
将正则表达式转为 NFA 的标准算法，被 RG 用于把 RBG 正则表达式翻译成自动机。
Gruber & Holzer 2008
证明 NFA 可比正则表达式指数级更简洁，为 RG 采用自动机而非正则表达式提供理论依据。
4. 博弈复杂度与形式化基础
Rasmusen 2007
有限扩展型博弈（extensive-form）定义，被 RG 用作“通用性”归约的源模型。
Schkufza, Love, Genesereth 2008
命题网络（propositional nets）——GDL 的一种电路化表示，RG 的 GDL→RG 翻译借鉴此思路。
5. 程序分析与优化技术
Kildall 1973
数据流分析迭代算法，被 RG 用于全局优化变换（常量传播、死代码消除等）。
6. 代表性强化学习与博弈树搜索研究
AlphaGo / AlphaZero / MuZero 系列
Silver et al. 2016, 2017, 2018; Schrittwieser et al. 2020
展示“通用化”路径：从专家知识→自对弈→模型无关规划，凸显高效前向模型的重要性，正是 RG 想提供的底层基础设施。
7. 其他被引用或对比的工作
Sironi & Winands 2017
命题网络优化，用于加速 GDL 推理，被作为 GDL 效率改进的代表。
Pitrat 1968
最早提出“通用博弈程序”概念。
综上，RG 在语言层面对标 GDL（通用性）、RBG（效率）、Ludii（设计便利）；在系统层面对标 OpenSpiel/Ai Ai 等“百游基准”理念；在底层技术则借用了正则语言、自动机、数据流分析等经典成果，并首次把它们组合成一条“高层语言→自动机→优化→C++ 推理器”的完整管道。
Q3: 论文如何解决这个问题？
论文把“既要通用、又要高效、还要易写”这一看似矛盾的目标拆成三层流水线，每层只专注一件事，再辅以自动机理论+编译优化手段，把矛盾点逐一消解。核心策略可概括为：
1. 语义层：用“最小自动机”当通用汇编
载体：非确定有限自动机（NFA）
状态 = 游戏规则节点
转移边 = 五种原子动作（空动作、比较、赋值、可达性检查、标签）
表达能力
可模拟任意有限、回合制、不完美信息、随机博弈（定理1 给出去往扩展型博弈的归约）。
不内置“棋盘”“算术”“回合”等高层概念，只操作符号与映射，因此没有领域天花板。
好处
自动机比正则表达式指数级更简洁（Gruber & Holzer 2008），也比逻辑程序更易做静态分析。
五类原子动作全是局部副作用，利于后续数据流优化。
2. 语言层：多层语法糖，只翻译不解释
层级 角色 如何“易写”
HRG 人类/PCG 设计友好 C-like 语法+模式匹配+for-all/loop/branch 结构；几十行可写 Tic-Tac-Toe。
领域框架（例：LineGames） 极窄领域极简描述 Python API，3–5 行定义 Alquerque 类直线棋，自动生成 HRG。
既有语言转译器 复用现有游戏库 RBG→RG 用 Thompson 构造+后处理；GDL→RG 用命题网络。
所有高层描述仅翻译到 RG 自动机，不反向依赖，因此：
新增高层语言无需改动底层引擎；
同一游戏可在不同高层语法间“移植”，最终共享 RG 优化与运行时。
3. 编译层：把自动机当成“中间表示”做激进优化
优化循环（固定点迭代）包含 5 大类 20+ 变换：
表达式级
常量传播、比较合并、嵌套映射合并、内联赋值。
结构级
公共前缀/后缀合并、互斥分支合并、死节点/变量删除。
可达性级
子自动机内联、无用标签删除。
范式化
显式类型强制、常量提升、符号名压缩。
数据流引导
用 Kildall 迭代算法计算每个节点的“知识集”，指导全局变换。
效果：
RBG→RG 后节点数 −72%、边数 −66%、状态内存 −21%。
HRG→RG 节点 −47%、边 −41%。
全部优化在<100 ms 内完成，IDE 可实时预览。
4. 运行时：生成专用 C++ 推理器
代码生成
自动机状态转 switch(id)；赋值/比较/标签直接内联为 C++ 语句；可达性检查生成子函数+局部缓存。
关键加速原语
@disjoint / @disjointExhaustive：在互斥分支处提前 return，减少 30–50% 评估量。
@tagIndex / @tagIndexMax：把标签序列存为 std::array 或 static_vector，消除动态分配。
@integer：把枚举类型映射回原生 int，加法/比较变回机器指令。
@iterator：把“任意赋值+立即过滤”模式生成预枚举数组，循环次数从 |D| 降到实际可达数。
状态去重
按需哈希或位集；@repeat 指明只需比较部分变量，甚至可降为单布尔。
5. 实验验证：效率全面领先
同硬件下 Flat Monte Carlo rollouts / 秒：
游戏 RG(HRG) RBG Ludii
Chess 1.57 M 531 k 113 k
Pentago 172 k 6.9 k 3.9 k
Alquerque 273 k 167 k 5.4 k
Breakthrough 82 k 51 k 3.4 k
平均 比 RBG 快 1.5–2×，比 Ludii 快 10–20×；翻译+优化总时间<1 s，实现“写高层→秒级反馈”。
总结
论文把“通用博弈”难题拆成三道可独立演进的工序：
高层语法糖 → 最小自动机 IR → 专用 C++ 推理器
自动机既当“通用语义锚点”又当“优化中间表示”，一次性把“描述范围”、“运行速度”、“设计友好度”三个维度推到当前极限，从而解决了 GGP 长期存在的表达力-效率-易用性不可能三角。
Q4: 论文做了哪些实验？
论文围绕“速度是否真快”“翻译是否可靠”“优化是否有效”三个维度，共执行了三类实验，全部在相同硬件（AMD Ryzen 9 3950X, 64 GB, Ubuntu 24.04, g++ 14.2, GraalVM 25）上完成，结果列于正文表 1 与附录表 2–5。
1. 主干实验：Flat Monte-Carlo rollouts 吞吐量对比
目的
衡量 RG 生成的 C++ 推理器与现有最快系统（RBG、Ludii）在前向模型速度上的差距。
方法
选取 35 款同时在 RG/RBG/Ludii 官方库出现的游戏（含变体）。
每系统都用各自“原生推荐”编译/运行参数。
单线程执行 1 分钟纯随机 rollouts（无启发式、无搜索），重复 3 次取平均。
关键结果（表 1，单位：rollouts/s）
游戏 RG(HRG) RG(RBG↓) 原生 RBG 原生 Ludii
Chess 1 572 531 531 995 531 995 113 133
Pentago 172 626 6 874 61 878 3 933
Alquerque 273 431 176 254 167 237 5 401
Breakthrough 82 135 79 175 50 977 3 365
…… … … … …
结论
所有 HRG 手写或生成版本均击败原生 RBG，平均提速 1.5–2×。
相对 Ludii 提速 10–20× 常见，最大达 两个数量级（如 Pentago、Chess）。
自动翻译的 RBG→RG 也能略快或持平原生 RBG，证明翻译未引入额外开销。
2. 编译速度与可扩展性实验
目的
验证“多层语言栈”是否能在 IDE 交互场景下“秒级”完成翻译+优化。
方法
记录从 HRG/RBG/GDL 源码到生成 C++ 的全程耗时（含解析、自动机构造、全部优化固定点迭代）。
60 s 超时限制；对比“无优化”与“全部优化”两种模式。
结果（附录表 2–5，选摘）
游戏 无优化 全优化 备注
backgammon.hrg 90 ms 4 233 ms 复杂随机节点导致可达性分析放大
chess.hrg 39 ms 1 344 ms 仍<1.5 s
pentago*.hrg 23–35 ms 535–547 ms 旋转对称优化大量节点
connect4.kif (GDL) 32 ms 2 042 ms 命题网络 grounding 爆炸
reversi*.rbg 44–73 ms 31–33 s 超大自动机，但仍在 60 s 内
结论
绝大多数游戏“写代码→看到汇编结果”延迟<1 s；最重例在 5–30 s 级，已可满足 IDE 实时反馈。
优化阶段虽指数级最坏情况，但实用游戏可在秒到十秒级完成。
3. 消融实验：优化变换逐项贡献
目的
量化“自动机级优化”到底减少了多少节点、边与状态内存，并观察“级联”效应。
方法
在 50+ 游戏上记录“未优化”与“最终优化”自动机的规模差异。
随机抽样 10 次，逐轮打开优化类别，绘制指标曲线（附录图 47–48）。
结果（附录图 47）
指标 平均降幅
节点数 −72 %
边数 −66 %
状态变量大小 −21 %
级联效应（附录图 48）
常量传播→死代码删除→可达性内联→分支合并，呈阶梯式下降；单次优化可触发新一轮简化。
固定点迭代 3–5 轮后收敛。
4. 辅助微实验（未单独列表）
确定性检查：对全部测试游戏运行“proper description”验证器，确保优化后仍满足动作合法性、移动无歧义、有限性等 5 项条件。
随机博弈验证：Backgammon、Monty Hall 等含随机节点游戏，用 χ² 检验 rollout 分布与理论概率一致（p>0.05）。
不完美信息 smoke test：Battleships、DiceThrowGuess 等游戏，在 rollout 中采样观测串，验证可见/不可见标签过滤逻辑无段错误。
实验总结
速度：RG 在 35 款跨语言基准上全面刷新最快记录，平均领先原冠军 RBG 1.5–2×，领先 Ludii 一个数量级。
可扩展：HRG/RBG/GDL 翻译+优化 99 % 游戏<1 s 完成，最重例 <30 s，已融入 LSP-IDE 实时工作流。
优化有效性：自动机规模缩减 >70 %，且变换相互触发，证明“以自动机为 IR”的优化空间巨大。
实验覆盖完美/不完美信息、确定/随机、纯逻辑/空间棋类，结果与论文“通用且高效”的主张一致。
Q5: 有什么可以进一步探索的点？
以下方向按“语言-理论-系统-应用”四象限列出，均直接建立在 Regular Games 已有成果之上，可短期落地亦可长期深挖。
1. 语言层：向“非棋盘”领域拓展
方向 可探索要点 预期收益
1.1 卡牌专用 DSL 在 HRG 之上封装“手牌、牌堆、洗牌、可见/隐藏”原语，翻译到 RG 自动机；验证《扑克》《UNO》《桥牌》等。
1.2 骰子+ wagering 游戏 引入整数分布类型 Dice={2..12} 与 @prob pragma，让随机边带权重而非单纯均匀采样；支持 Craps、Backgammon 完整规则。
1.3 Fairy Chess 模式库 用 Python 框架封装“莱佛士棋子、棋盘拓扑、升变、王车易位”等可组合 ludeme，一键生成 HRG。
2. 理论层：复杂度与可判定性深挖
方向 可探索要点 预期收益
2.1 固定类型长度的精细谱 论文只给出“type length=1⇒PSPACE，一般⇒EXPSPACE”。可细分树宽、域大小与随机节点比例，得到 parameterized complexity 曲线。
2.2 随机博弈的精确概率模型 目前仅支持有理概率 via 边复制。能否在自动机层面支持无理概率/连续分布，且仍保持有限状态？
2.3 可合成性（Compositionality） 研究两款 RG 游戏“并行-同步”或“串接-交替”后，复杂度类是否封闭；能否给出组合运算符？
3. 系统层：编译与运行时再优化
方向 可探索要点 预期收益
3.1 Bit-boarding 原生支持 在 HRG 引入 bitboard 关键字，编译器自动把 Coord→Bool 映射到 uint64_t，并生成位移掩码指令。
3.2 GPU / SIMD 批量前向 自动机拓扑静态已知，可把合法动作展开为无分支 SIMD 指令，一次跑 256/1024 个并行 rollout。
3.3 增量编译与热替换 利用自动机局部性，只重编译被优化变换影响的子图；IDE 内“改一行→毫秒级刷新。
3.4 学习式优化顺序 用强化学习 agent 在编译期搜索“下一轮该跑哪条变换”，目标是最小节点数，而非固定启发式顺序。
4. 应用层：AI 与 PCG 新基准
方向 可探索要点 预期收益
4.1 RG-Gym：多语言统一接口 把 RG 推理器封装成 OpenAI-Gym 兼容环境（C++ 后端 + Python 绑定），一次性提供 100+ 游戏。
4.2 程序内容生成（PCG）（1）——规则空间搜索 用遗传编程在 HRG 语法树上突变/交叉，自动机规模与可解性作为约束，搜索“有趣新棋”。
4.3 PCG（2）——难度曲线生成 给定基础规则，用 MCTS 估计胜率曲线，再通过自动机边增删微调，使胜率梯度落在目标区间。
4.4 解释性 AI：自动机反编译 把优化后的自动机反向生成“人类可读伪代码”，用于解释 AI 为何认为某步非法；结合 LSP 在 IDE 中高亮路径。
5. 跨系统生态
方向 可探索要点 预期收益
5.1 Ludii↔RG 双向翻译 目前仅有 RBG→RG 与 GDL→RG；若完成 RG→Ludii，即可把 RG 优化后的游戏反哺 Ludii 社区，扩大数据库。
5.2 统一基准联赛 以 RG 为“交换格式”，举办同时接受 GDL/RBG/Ludii 报名的年度联赛，所有游戏先转 RG 再运行同一高速服务器，消除“主场优势”。
6. 长期高挑战
6.1 无限/持续博弈（Loopy games）
当前 RG 要求“有限 play”，能否引入 Büchi 条件或 Mean-payoff 自动机，保持高效前向？
把自动机扩展为 Timed Automata，支持《乒乓球》《赛车》类实时交互，同时仍保持可编译到 C++。
Regular Games 把“自动机当通用博弈汇编”这一思路跑通后，上层语言、下层优化、外围生态都出现大片空白区。
短期（1–2 年）可聚焦 卡牌 DSL、bit-board、RG-Gym、PCG 规则生成；
中期（3–5 年）挑战 连续随机、GPU 批量、双向生态；
长期则迈向 实时/无限博弈 与 学习式编译器，最终让 RG 成为“任何有限博弈”事实上的 LLVM。
Q6: 总结一下论文的主要内容
Regular Games：一篇把“通用博弈描述”做成高速汇编语言的论文
1. 要解决的问题
表达力-效率两难：GDL 通用但推理慢；RBG/Ludii 快却受限或封闭。
设计-自动处理两难：人类/PCG 需要高层语法；Agent/优化器需要极简 IR。
2. 核心思路
“用非确定有限自动机当通用博弈的汇编语言”——高层语言只负责翻译，不负责执行；所有游戏最终统一成同一自动机 IR，再经编译器生成专用 C++ 推理器。
3. 系统架构（三层流水线）
graph TD
A[高层语言] -->|翻译| B[RG 自动机 IR]
B -->|优化| C[精简自动机]
C -->|代码生成| D[C++ 前向模型]
层级 代表 职责
高层 HRG、Python-API、RBG/GDL 转译器 让人类或算法“写起来快”
中间 RG 自动机 五类原子动作、无内置概念，极简且可静态分析
底层 编译器 + pragma 优化 节点-72%、边-66%，生成当时最快推理器
4. 关键优化（自动机视角）
常量传播、分支合并、可达性内联、死代码删除等 20+ 变换；迭代到固定点。
pragma 制导：@disjoint、@integer、@iterator、@tagIndex 等把“自动机结构”映射为“CPU 友好代码”。
5. 实验结果
速度：35 次跨语言基准，RG 比原最快系统 RBG 再快 1.5–2×，比 Ludii 快 10–20×；Chess 达 1.57 M rollouts/s。
编译时间：99 % 游戏翻译+优化<1 s；最重例 <30 s，可实时 IDE 反馈。
规模缩减：自动机节点 −72 %、边 −66 %、状态内存 −21 %。
6. 理论贡献
通用性：RG 可编码任意有限、回合制、不完美信息、随机博弈（有理概率），与 GDL-II、Ludii 同 expressive class。
复杂度：一般情况 legal-move 问题 EXPSPACE-完全；若类型长度固定则 PSPACE-完全；为“哪类游戏仍可实时”划出边界。
7. 工具与生态
自带 LSP-IDE：语法高亮、自动补全、自动机可视化、benchmark 面板。
已提供 RBG→RG、GDL→RG 转译器；LineGames Python 库 3 行代码生成 23 次棋类。
输出标准 C++ 库，可嵌入任何 Agent/RL 框架。
8. 一句话总结
Regular Games 把“通用博弈”做成自动机汇编——高层易写、中层可析、底层极速，首次在同一系统里同时拿下“任意有限博弈描述力”与“毫秒级前向模型”两大目标，为 GGP、RL、PCG 提供了一个即插即用的新基建。
来源：Arxiv2025-11-13 18:29:27 UTC
