Skip to content

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

🕒 Published (v1): 2025-11-13 18:29 UTC · Source: Arxiv · Venue: AAAI 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

Regular Games (RG) is a new General Game Playing (GGP) system that encodes game rules as nondeterministic finite automata (NFA) rather than logic programs or regular expressions. It is theoretically universal for all finite turn-based games with imperfect information and randomness, and generates C++ forward models that outperform the prior state-of-the-art GGP systems (RBG, Ludii) on flat Monte Carlo playout throughput.

Problem

Existing GGP formalisms face an expressiveness-efficiency tradeoff: GDL/GDL-II are logically expressive but computationally expensive due to mandatory logic resolution; RBG is fast but restricted to perfect-information board games; Ludii is expressive but complex (~thousands of keywords) and Java-only. No single system combines minimal language design, universality for imperfect-information games, and competitive computational efficiency with practical tooling.

Method

The core RG language defines a game as a set of typed variables and constants plus a rules automaton—a directed graph whose edges carry one of five action types: empty (ε-transition), equality/inequality comparison, assignment, reachability check (?q₁→q₂ / !q₁→q₂), and symbolic tag. NFA representation is theoretically exponentially more succinct than the regular-expression basis of RBG. A player's move is the sequence of tags observed along a legal walk that ends in reassigning the player variable. The compiler applies a dataflow-analysis optimization pipeline (constant propagation, assignment inlining, disjoint-path detection, redundant-tag pruning) run to fixed point, then emits a C++ forward model. A higher-level language (HRG) with structural programming constructs compiles down to RG; a Python library (LineGames) generates HRG for Alquerque-like games. Automatic RBG→RG and experimental GDL→RG translators are included.

Key Contributions

  • Minimal NFA-based GGP language (RG) universal for finite turn-based games with imperfect information and randomness (same class as GDL-II and Ludii).
  • Formal complexity results: determining legal-move existence is EXPSPACE-complete in general, PSPACE-complete with fixed max type length.
  • HRG: a human-friendly high-level language compiled to RG without performance penalty.
  • Multilevel translation pipeline enabling RG to act as an "assembler" for other GGP languages.
  • Dataflow-analysis optimization pipeline reducing automaton size by 47–72% (nodes) and 41–66% (edges) and state memory by up to 21%.
  • IDE with Language Server Protocol (LSP) support, automaton visualization, benchmarking, and transformation debugger.

Results

All figures are flat Monte Carlo playouts/second; baselines are native RBG and Ludii.

  • HRG→RG beats RBG and Ludii on every tested game.
  • Connect Four: 1,297,176 (HRG→RG) vs 914,514 (RBG) vs 55,858 (Ludii).
  • Chess: 1,572 (HRG→RG) vs 995 (RBG) vs 113 (Ludii).
  • Tic-Tac-Die: 2,708,648 (HRG→RG) vs no RBG variant vs 36,702 (Ludii).
  • Breakthrough: 82,135 (HRG→RG) vs 50,977 (RBG) vs 3,365 (Ludii).
  • RG is typically 10–20× faster than Ludii across the benchmark set.
  • RBG→RG translations match or beat native RBG on a subset of games (e.g., Fox and Hounds: 323,068 vs 331,884 RBG; Alquerque rbg: 79,899 vs 79,312).
  • Optimization + compilation finishes in under 100 ms for most HRG games.

Limitations

  • GDL→RG translation is experimental and not yet production-quality.
  • RBG→RG translations do not uniformly beat native RBG (e.g., Chess king-capture: 4,887 vs 11,062 native RBG; Hex 11×11: 2,447 vs 22,441).
  • Deciding game-description correctness is EXPSPACE-complete in the general case.
  • Bit-boarding and other low-level performance techniques are not yet implemented.
  • Higher-level language frameworks for card, dice, and fairy-chess games are future work.
  • Agent tooling (beyond the C++ forward model interface) is still in development.

Relevance to Agentic AI / LLM Agents

RG provides a high-throughput, universal game environment infrastructure directly relevant to training and evaluating general-purpose agents: faster forward models directly translate to more MCTS rollouts per second, which is the primary bottleneck for planning-based agents. The system's universality over imperfect-information and stochastic games makes it a stronger benchmark platform than RBG for agents that must handle partial observability—a key challenge in agentic settings. The "assembler" design, where domain-specific languages compile to a common efficient substrate, mirrors modular agent architectures and could enable procedurally generated task environments for RL research at scale. For LLM-based agents being evaluated on game-playing tasks, the IDE and formal game description language offer a structured, verifiable specification layer that could complement natural-language game instructions.