Presented at AAAI-19, Regular Boardgames (RBG) is a formal language designed to overcome the efficiency bottlenecks of traditional General Game Playing (GGP) frameworks. By shifting from logic-based predicates to the theory of regular languages, RBG enables computers to play complex games like Go, Arimaa, and International Checkers with unprecedented efficiency.
The Efficiency Bottleneck in GGP
For years, the Game Description Language (GDL) has been the standard for GGP. Based on Datalog, GDL is highly expressive but suffers from a significant "efficiency bottleneck." Because it relies on logic resolution to determine legal moves, describing complex mechanics—such as the "ko" rule in Go or multi-jump captures in checkers—results in slow processing. This often makes complex games computationally "unplayable" for AI agents that require high-speed state-space searches.
The RBG Framework
RBG addresses these issues by defining games through Regular Languages rather than logic facts. A game in RBG is defined as a 7-tuple (Players, Board, Pieces, Variables, Bounds, InitialState, and Rules).
Key innovations include:
- Graph-Based Board: The board is treated as a directed multigraph where edges represent directions (e.g., "up", "left"), mirroring human intuition.
- Rules as Regular Expressions: Legal move sequences are defined as regular expressions over elementary actions like shifting focus, checking/placing pieces, and variable assignment.
- The "Keeper": A special automated player handles administrative tasks (e.g., score calculation), streamlining the search tree for AI agents.
- Straightness ($k$): This complexity measure represents the maximum number of modifiers between player switches, allowing for mathematical bounds on move generation complexity.
As shown in the complexity analysis above, for the subclass of $k$-straight games, determining a legal move is achievable in polynomial time, a significant improvement over the EXPTIME-completeness of GDL.
Empirical Performance
The authors evaluated RBG using a benchmark suite of classical board games, comparing the RBG compiler and interpreter against the best-performing GDL engines (Propnet and Prolog).
The results demonstrate dramatic performance gains:
- Amazons: The RBG compiler processed ~7.7 million nodes per second (Perft), nearly 100 times faster than the GDL Propnet (~78,000).
- Complex Games: Games like Go and Arimaa, previously considered "not available" for GDL due to complexity, were handled easily by RBG. Go reached over 550,000 nodes per second.
- Memory Efficiency: Unlike GDL propnets, which often crash on large games due to massive logic circuits, RBG reasoners maintain a low memory footprint.
Conclusion
By leveraging regular expressions, RBG provides a "just right" level of expressivity—powerful enough to describe any finite deterministic game with full information, yet efficient enough to be compiled into high-speed C++ code. This framework bridges the gap between general-purpose game description and the performance of hand-coded, game-specific engines, opening new doors for research in General Game Playing.
Reference: Kowalski, J., Mika, M., Sutowicz, J., & Szykuła, M. (2019). Regular Boardgames. Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (AAAI-19), 1699-1706.
Summary updated