🤖 AI

Scalable Board Expansion within a General Game System

This thesis proposes a dynamic board expansion mechanism within a General Game System to automatically grow game boards during play, thereby eliminating the unnecessary complexity associated with traditional static, oversized boards.

Original authors: Clémentine Sacré

Published 2026-01-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Clémentine Sacré

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are playing a game like Carcassonne, where you build a medieval landscape by snapping tiles together. In the real world, you just keep adding tiles to the table, and the map grows as big as you need it to be. There is no "edge" to the table; you just keep going.

However, the computer system used to play these games (called Ludii) was struggling with this concept. Here is the problem and the solution proposed in this paper, explained simply.

The Problem: The "Giant Blank Canvas" Trap

Imagine you want to paint a small flower on a canvas. But instead of giving you a small canvas, the computer forces you to use a massive, 40-foot-by-40-foot sheet of paper.

The Reality: You only paint a tiny flower in the middle.
The Computer's View: The computer has to remember every single inch of that giant 40-foot sheet, even though 99% of it is empty white space.
The Consequence: The computer gets tired and slow. It wastes energy calculating the empty corners of the giant sheet, leaving it with less brainpower to actually play the game or think of good moves.

In the paper, the author explains that Ludii was doing exactly this. It started every "boardless" game with a huge, fixed grid (like a 41x41 square) and hid the edges from the human player to make it look infinite. But the computer was still stuck calculating that massive, mostly empty grid.

The Solution: The "Magic Growing Tent"

The author, Clémentine Sacré, built a new system where the board isn't a giant fixed sheet. Instead, it's like a magic tent that only expands when you need it to.

The paper tests two main ways to grow this tent:

1. The "Perimeter" Strategy (The Bubble Wrap Method)

Imagine you have a small square of bubble wrap. Every time you place a tile on the edge, you don't just add one bubble; you wrap the entire square in a new layer of bubble wrap.

How it works: The board gets bigger all around at once.
Pros: It's very fast for the computer to calculate because the shape stays perfectly square.
Cons: If you only play on one side, you end up adding a lot of empty space on the other three sides that you might never use.

2. The "Zone" Strategy (The Puzzle Piece Method)

Imagine you are building a puzzle. You only add new puzzle pieces right next to the piece you just placed.

How it works: If you play on the edge, the computer only adds the immediate neighbors of that spot.
Pros: It creates the least amount of "wasted" empty space. The board stays compact.
Cons: It's harder for the computer to manage because the shape gets weird and irregular, requiring more complex math to keep track of where everything is.

The Results: Speeding Up the Game

The author tested these new methods against the old "Giant Canvas" method using three different games (Andantino, Bravalath, and Plotto) and different tile shapes (squares, hexagons, and triangles).

Here is what happened:

The Old Way: The computer could only do about 0.3 game simulations per second. It was moving in slow motion because it was carrying around that giant, empty board.
The New Way (Best Method): The "Perimeter" method with a specific mapping trick (called PERI-MAP) allowed the computer to do about 13 to 228 simulations per second.
The Takeaway: The new system made the computer roughly 25 times faster. It stopped wasting time on empty space and focused only on the area where the game was actually happening.

Why This Matters

This isn't just about making the computer faster; it's about making the game honest.

Before: The computer was forced to pretend the game was happening on a giant, finite board that didn't really exist.
Now: The computer can handle games that truly feel infinite, growing only as the players build them.

The paper concludes that while the "Zone" method (adding pieces only where needed) is the most efficient in terms of space, the "Perimeter" method (adding a full layer) is currently the fastest for the computer to process. By using this new system, the Ludii platform can now support complex, modern board games that were previously too difficult to simulate efficiently.

In short: The author replaced a giant, empty warehouse with a smart, expanding tent, allowing the computer to play board games 25 times faster and more accurately.

Technical Summary: Scalable Board Expansion within a General Game System

Problem Statement

General Game Playing (GGP) systems, such as Ludii, aim to support a wide variety of games through a unified framework. However, the current implementation of Ludii struggles with boardless tabletop games (e.g., Carcassonne, Andantino), where the playing area is not fixed but dynamically constructed by players placing tiles.

In the existing Ludii architecture, boardless games are simulated using a static, fixed-size board (e.g., $41 \times 41$ for square/triangular tiles, $21 \times 21$ for hexagonal tiles). While the user interface hides the boundaries to simulate an infinite space, the AI agents must reason over this entire pre-allocated grid. This approach introduces three critical limitations:

Memory and Computational Waste: The system precomputes extensive data structures (such as "radials" for movement and adjacency) for the entire grid, including vast areas that remain empty throughout the game.
Inaccurate Representation: A fixed grid imposes artificial boundaries that contradict the fundamental nature of boardless games, which can theoretically expand indefinitely.
Performance Degradation: The large state space reduces the number of random playouts (simulations) an AI can perform per second, significantly hindering the effectiveness of Monte Carlo Tree Search (MCTS) and other AI strategies.

Methodology

The thesis proposes a dynamic board expansion mechanism that replaces the static grid with a scalable structure. The core objective is to initialize the board with a minimal size sufficient for the starting tiles and expand it only when necessary based on player actions.

The research explores two primary expansion strategies, each implemented with two state-management approaches:

1. Expansion Strategies

Perimeter Strategy (Contour): When a player places a tile on the edge of the current board, the system adds a complete new layer of cells around the entire perimeter. This ensures the board is always surrounded by potential play areas but can lead to rapid, exponential growth in the worst-case scenarios.
Zone Strategy: When a player places a tile on the edge, the system adds new cells only in the immediate neighborhood of that specific move (e.g., the 8 adjacent cells for squares, 6 for hexagons). This approach is more localized and aims to minimize the number of generated tiles.

2. State Management Approaches

To handle the structural changes during expansion, two methods for updating the game state were developed:

Reapplication (RE): Inspired by the "undo" mechanism, the board is reset to its initial state, resized to the new dimensions, and all previous moves are replayed sequentially to reconstruct the current state.
Direct Mapping (MAP): The existing game state (containers, ownership, move history) is directly mapped onto the new, larger board structure. Indices of existing cells are recalculated based on the new topology, and new cells are added to the empty sets without replaying the entire move history.

3. Implementation Details

The implementation adapts Ludii's internal structures, specifically:

Graph/Topology: Dynamically reconstructs the graph of cells, vertices, and edges.
Container State: Updates ChunkSet bitsets (tracking empty, occupied, and playable sites) to reflect the new board size and cell mappings.
Owned Structure: Remaps component ownership to new cell indices.
Tile Shapes: Specific algorithms were derived for Square, Hexagonal, and Triangular tiles, accounting for their unique neighbor counts and geometric growth patterns.

Key Contributions

Dynamic Board Architecture: The introduction of a scalable board expansion mechanism that allows Ludii to support boardless games without arbitrary size limits.
Optimized State Management: The development of the PERI-MAP and ZONE-MAP techniques, which efficiently update game states during expansion without the overhead of full state reconstruction in every instance.
Shape-Specific Logic: Detailed mathematical formulations for calculating new cell counts and index mappings for square, hexagonal, and triangular grids during expansion.
Empirical Evaluation: A comprehensive benchmark comparing the new dynamic approaches against the static baseline across multiple games (Andantino, Bravalath, Plotto) and tile shapes.

Results

Experiments were conducted on a cluster using four games with square, hexagonal, and triangular tiles, measuring board size growth and random playout performance (playouts/sec and moves/sec).

Board Size Efficiency:
- The static BASE implementation maintains a constant, massive board size (e.g., 1,681 cells for squares) regardless of game progress, resulting in >90% unused tiles.
- The ZONE strategy maintains the smallest board sizes, staying significantly below the static limit even in worst-case scenarios.
- The PERI strategy grows exponentially in worst-case scenarios but remains smaller than the static baseline in best-case scenarios.
Performance (Random Playouts):
- The PERI-MAP strategy achieved the highest performance, outperforming the static BASE implementation by approximately 25 times on average.
- PERI-MAP and PERI-RE showed comparable performance, with PERI-MAP generally slightly superior.
- Contrary to theoretical expectations, the ZONE strategies (which generate fewer tiles) performed worse than the PERI strategies. The authors attribute this to the current implementation's inefficiency in dynamically generating irregular graph structures compared to the highly optimized, built-in functions for generating regular perimeter grids in Ludii.

Significance and Claims

The paper claims that the proposed PERI-MAP approach represents a significant advancement in the representation of boardless games within GGP systems. By eliminating the need for massive, pre-allocated static grids, the system achieves:

Scalability: The ability to model games with virtually unlimited board growth.
Efficiency: A drastic reduction in memory usage and an increase in simulation speed, enabling more effective AI agents.
Fidelity: A more accurate representation of the game's spatial dynamics, removing artificial boundaries.

The authors conclude that while the ZONE strategy is theoretically more efficient in terms of tile generation, the PERI-MAP strategy currently offers the best balance of performance and implementation maturity within the Ludii framework. This work lays the foundation for implementing a broader range of modern boardless games and supports future research in dynamic topology and rule-based expansion.