Regular Games -- an Automata-Based General Game Playing Language

AI summary

Overview

Research area: General Game Playing (GGP) — specifically, the design of formal description languages that encode the rules of arbitrary games so that AI agents can be tested on many games without game-specific engineering.

Technical level: Advanced. The paper assumes familiarity with finite automata, formal language theory, computational complexity (EXPSPACE/PSPACE), and the history of GGP formalisms (GDL, GDL-II, Ludii, Regular Boardgames). The efficiency benchmark tables and the higher-level language examples are readable at an intermediate level, but the theoretical sections and the "proper description" conditions require a formal-methods background.

Scope: The paper introduces Regular Games (RG), a GGP system whose low-level rules language is a nondeterministic finite automaton, plus a high-level design language (HRG), translators from existing languages, a toolchain, and benchmarks comparing forward-model speed against Regular Boardgames (RBG) and Ludii.

What This Paper Is About

GGP systems let researchers describe many different games in one formal language so that a single AI agent can be run on all of them. Two competing goals have shaped the field: languages should be expressive and pleasant for humans to design games in, yet also compile into fast simulators, because slow rule interpreters destroyed the popularity of the original logic-based Game Description Language (GDL). The paper's goal is to build a system — Regular Games (RG) — that is simultaneously minimal enough for automatic processing by agents and optimizers, universal in the class of games it can express, and measurably faster at generating forward models than the current fastest systems.

Key Contributions

1. A new minimal low-level GGP language (RG) based on finite automata. Rules are described by a nondeterministic finite automaton (described as a directed graph with edge labels) rather than a regular expression. The authors note this is theoretically exponentially more succinct than regular expressions, which is what Regular Boardgames uses. RG has only a handful of mechanisms — types, constants, variables, edges, and five action kinds — and no built-in concepts such as a board, arithmetic, or predefined move forms.

2. A universality result. The authors prove (Theorem 1, and Theorem 3 in the Appendix) that RG is universal for the class of all finite turn-based games, including imperfect information and randomness with rational probabilities — the same class covered by GDL-II and Ludii. Simultaneous moves are modelled through imperfect information.

3. A layered ecosystem of languages and tools. On top of the low-level language sits High-level Regular Games (HRG), a declarative/structural language for human and machine game design that compiles down to RG. Above HRG sit specialized frameworks, including the LineGames Python library, in which the authors defined 23 unique existing games for Alquerque-like games on line boards. The ecosystem also includes a code editor with Language-Server Protocol (LSP) support, automaton visualization, benchmarking tools, and a debugger of game-description transformations. RG and Ludii are described as the only GGP languages with a proper, industry-grade IDE.

4. Translations into RG as a common target. The authors developed an automatic translation from Regular Boardgames (RBG) to RG using Thompson's construction, and an experimental translation from GDL to RG based on the propositional-network approach. The stated aim is for RG to serve as an "assembler for GGP," so new specialized languages need no changes to the underlying pipeline.

Main Findings

• RG beats the previous fastest GGP language. The paper reports that RG outperforms RBG in all games implemented in HRG (whether handmade or generated) and in part of the games automatically translated from RBG. RG is reported as typically 10–20 times faster than Ludii.

• Concrete benchmark numbers (flat Monte Carlo playouts per second, averaged over three 1-minute runs). Selected entries from the paper's Table 1 (HRG-RG / RG-translated-from-RBG / RBG / Ludii):

  • Chess: 1 572 / 531 / 995 / 113†
  • Connect Four: 1 297 176 / 122 716 / 914 514 / 55 858
  • Tic-Tac-Die: 2 708 648 / – / – / 36 702
  • English Draughts: 69 244 / 45 927 / 62 251 / 4 104†
  • Amazons: 6 226 / 3 582 / 3 693 / –
  • Pentago: 43 875 / 500 / 22 553 / –
  • Hex (11x11): 23 535 / 2 447 / 22 441 / 11 024
  • Yavalath: 415 251 / 359 832 / 352 910 / 93 642
  • Oware: 27 991 / – / – / 347
  • Backgammon: 2 323 / – / – / 7†
  • Bombardment: 416 266 / – / – / 14 907

  A dagger (†) marks Ludii variants with known subtle differences that the authors consider minor or in favour of efficiency; the paper lists examples such as Backgammon prematurely ending a move, Chess executing promotion choice in a separate move, and The Mill Game having a bug where 3 pieces left cannot form a capturing mill. Dashes mean the cell does not apply (e.g., no translated variant was produced).

• Optimizations substantially shrink automata. For automata translated from RBG, the optimization pipeline yields over 72% fewer nodes, 66% fewer edges, and 21% smaller state size — where state size is the memory needed to store the game state, described as a key factor for reasoner efficiency. For games written in HRG, optimizations reduce the number of nodes and edges by 47% and 41% respectively.

• Fast compile/optimize cycle. The complete translation and optimization suite for most HRG games runs under 100ms, which the authors say gives an almost immediate feedback loop in the IDE.

• Complexity results. Deciding whether a legal move exists from the initial game state is EXPSPACE-complete, and verifying any of the five proper-description conditions is likewise EXPSPACE-complete. If the maximum type length — the number of arrows plus one in a type definition, with set types having type length 1 — is fixed, these problems become PSPACE-complete. The paper notes that in general a game state's size can be exponential in the description length, and computing one move can be as hard as traversing the whole game tree.

• The move representation is flexible. A move is a finite sequence of tag names ("labels") produced along a legal walk; the authors require that all legal walks with the same labelling lead to the same next state (the "move unambiguosity" condition).

• No agent-performance or learning results are reported. All efficiency figures in the paper come from forward-model playout throughput and transformation statistics; the paper does not report win rates, Elo, or MCTS/Minimax comparison results. (Future work explicitly mentions that such algorithm comparisons matter.)

Methodology in Plain English

The authors start from an analysis of what went wrong historically with GGP languages: GDL was expressive but forced expensive logic resolution, while Ludii is convenient but with a few thousand keywords is complex and tied to its own software. They pick a middle path.

The core idea is to define a game's rules as a finite automaton: nodes are rule stages, edges carry small actions that check conditions, update variables, or emit visible labels. A game state is the current variable assignment plus the current automaton node, and playing means walking the graph and collecting labels into moves. There are only five action types — an empty action, comparisons, assignments, a "reachability check" that asks whether some node can be reached (with a negated form), and tags that become part of the move. Two additional shorthand actions (assignment of any value of a type, and a variable-derived tag) exist purely to shorten descriptions, and can be expanded automatically. Optional pragmas such as @disjoint only hint at optimizations and do not change the game tree.

Because this low-level language is verbose, the authors layer HRG on top: a structural syntax with domains, numeric ranges, set unions, pattern matching, reusable graph blocks, and loops, which is translated into RG. On top of that, they add game-class-specific generators, demonstrated by the LineGames Python library.

For efficiency, they built an optimization pipeline of transformations — some RG-specific (like pruning redundant tags), others general (like inlining assignments or constant propagation) — run in a fixed-point loop because one transformation can enable others. Global reasoning uses data-flow analysis to compute knowledge at each node. Validators (type checking, reachability possibleness, map correctness) run after every transformation to keep descriptions correct.

Finally, RG descriptions are compiled to C++ code that exposes a forward model: check whether a state is terminal, get the current player, enumerate all legal moves, apply a move, and produce a human-readable state description. Efficiency was measured as flat Monte Carlo playouts per second, averaged over three 1-minute runs, on an AMD Ryzen 9 3950X with 64GB RAM, Ubuntu 24.04.3 LTS, g++ 14.2.0, and GraalVM 25.0.1+8.1.

Why This Matters

Impact on research. Much of game-AI research — MCTS enhancements, Minimax variants, reinforcement learning experiments — needs to be evaluated across a diverse set of games, and the authors argue that many algorithmic enhancements do not work in all cases, so the subdomain where they help must be found and described. Faster forward models directly increase how many playouts an experiment can afford. RG also changes the research workflow by acting as a compilation target: instead of every language shipping its own executable, RBG and (experimentally) GDL descriptions can be translated into RG, and new specialized languages can be added without touching the bottom of the pipeline.

Real-world applications (as motivated or implied by the paper):

• Reinforcement learning benchmarking. The paper notes that generalizable game systems gain special attention from the RL community as benchmarking domains, and that efficiency is even more crucial for RL experiments.
• Procedural content generation (PCG). The paper states that the multilevel translation approach and extensibility make the system "excellent for procedural content generation applications and exploration of new game rules."
• Rapid game design and prototyping. The IDE with LSP, instant diagnostics, automaton visualization, and sub-100ms translation gives designers feedback comparable to a normal code editor, and the LineGames library lets designers define game rules in a few lines of Python.
• Research platforms for game AI agents. RG provides a C++ library that can be embedded in a larger program, giving a programmer full control over communication between an agent and the game engine.

Industry relevance. The authors position RG as production-oriented in tooling terms: an industry-grade editor, LSP support, a C++ compilation target chosen for effectiveness and interoperability with other languages, and a common interface for traversing the game tree. Translation support for existing languages (RBG, experimental GDL) lowers the cost of adopting RG for existing projects. The paper does not report commercial deployment, adoption metrics, or user studies.

Future Directions

• More higher-level languages for specific game families. The authors name fairy chess, card games, and dice games as targets for new specialized languages on top of RG.
• Further efficiency work. They propose extending the automaton analysis and applying additional techniques, naming bit-boarding as an example.
• Improving the GDL translation. The experimental GDL-to-RG translator could be improved, for instance by detecting alternating moves.
• Completing the agent-facing toolchain. The paper notes that more tools supporting agent programmers are still in development, though the system can already be used as a research platform.

Target Audience

This paper is most valuable to GGP and game-AI researchers who need a fast, general game description language for benchmarking agents; to reinforcement learning researchers looking for a diverse, high-throughput environment suite; to programming-language and formal-methods researchers interested in automata-based rule encoding and its complexity; to game designers and PCG researchers who want a declarative rule language with strong tooling; and to tool builders who want a compilation target for translating their own game description languages. Readers without a background in automata theory or computational complexity will find the language examples and benchmark tables accessible, but will need to consult the appendix and cited literature for the formal results.

Authors’ abstract

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.