Solving Terni Lapilli: A 2000-Year-Old Game

A Game Lost to Time

Scratched into the stone steps of ancient Roman forums, carved into Egyptian temple floors, etched onto medieval church benches—the same simple pattern appears across millennia: a circle divided into eight segments with a center point. This is Terni Lapilli (called Trias in Ancient Greek), a game that traces its roots to Egypt millennia ago.

This discovery prompted an investigation into how mathematical techniques could model optimal play in a constrained game space.

In my previous exploration of naval warfare and Warhammer 40k, I showed how mathematical modeling can reveal optimal strategies in complex games. Terni Lapilli presents a different challenge: it’s small enough that we might be able to solve it completely—to prove mathematically what happens when both players play perfectly. This blog post is about the different mathematical techniques I apply to understand this game.

The Rules

Terni Lapilli is played on a board with 9 positions: 8 arranged in a circle and 1 in the center. Two players (let’s call them Black and White) compete to get three of their pieces in a row.

The game has two phases:

Phase 1: Placement - Players alternate placing their three pieces on empty positions.

Phase 2: Movement - Once all pieces are placed, players alternate moving one piece to an adjacent empty position.

A player wins by getting three pieces in a row. There are 12 possible winning patterns:

Winning Patterns

There are 12 ways to win: 8 consecutive positions around the ring, and 4 through the center

Pattern 1

Ring: 0-1-2

Pattern 2

Ring: 1-2-3

Pattern 3

Ring: 2-3-4

Pattern 4

Ring: 3-4-5

Pattern 5

Ring: 4-5-6

Pattern 6

Ring: 5-6-7

Pattern 7

Ring: 6-7-0

Pattern 8

Ring: 7-0-1

Pattern 9

Center: 0-8-4

Pattern 10

Center: 1-8-5

Pattern 11

Center: 2-8-6

Pattern 12

Center: 3-8-7

Pattern Statistics

• Total winning patterns: 12
• Ring patterns (consecutive): 8
• Center patterns: 4
• Positions per pattern: 3

The patterns break down into two categories:

• 8 ring patterns: Three consecutive positions around the outer circle (like 0-1-2 or 5-6-7)
• 4 center patterns: Three positions through the center (like 0-8-4 or 2-8-6)

Try playing a quick game to get a feel for it. This is with an AI opponent who makes completely random moves. Like Stanley the monkey if you remember the old Chessmaster games.

Reset Game

Game Info

Phase: Placement

Current Player: black

Black Pieces: 0/3

White Pieces: 0/3

AI Opponent

Type: Random

Move History

No moves yet

This isn’t really good enough, so I thought I’d take a look at different approaches for building a stronger opponent.

Implementing an opponent

We must first define the board mathematically. Then we can implement heuristics—rules that score moves as good or bad. Finally, the minimax algorithm searches ahead through possible move sequences to find the best move.

Graph Theory: Understanding the Board

Before we can build an AI, we need to understand the board’s structure mathematically. The board is actually a graph, a collection of vertices (positions) and edges (legal moves).

Each position connects to its adjacent neighbors:

• Ring positions connect to their two ring neighbors plus the center
• The center connects to all 8 ring positions

const ADJACENCY = {
  0: [1, 7, 8],  // Position 0 connects to 1, 7, and center
  1: [0, 2, 8],
  // ... and so on
  8: [0, 1, 2, 3, 4, 5, 6, 7]  // Center connects to all
};

This graph structure defines which moves are legal. In game theory terms, we’re working with a finite, deterministic, perfect information game with a clearly defined state space.

Evaluating Positions Heuristically

We can score positions using a heuristic function that looks at all 12 winning patterns:

• Two pieces + empty space = threat → +500 points
• One piece + two empty spaces = potential → +10 points
• Opponent has the same = negative points

For example, if Black has pieces on positions 0 and 1, with position 2 empty, that’s a strong threat worth +500 points. If Black can move to position 2 next turn, they win.

Fine-tuning heuristics proved crucial—different scoring rules produce drastically different AI behavior.

Position Evaluation

Overall Score

+1040

Evaluating for black

Strong advantage

Scoring System

• +10000: Win
• +500: Strong threat (2 in a row)
• +10: Potential (1 piece positioned)
• Negative values: Opponent advantages

Significant Patterns

0-1-2(Strong threat)

2/0/1

+500

7-0-1(Strong threat)

2/0/1

+500

Potential Patterns (4)

1-2-3+10

6-7-0+10

0-8-4+10

1-8-5+10

The Minimax Algorithm

Once we can describe the game mathematically, we can apply an optimization algorithm to search for the best move. The minimax algorithm is a classic method for decision-making in two-player games. It assumes both players play optimally and minimizes possible loss for worst-case scenarios. In practice, humans rarely play optimally, but our analysis assumes perfect play.

The minimax algorithm works recursively:

1. Base case: If we find a winning position or reach our search depth limit, evaluate it
2. Recursive case:
   • If it’s our turn, choose the move that maximizes our score
   • If it’s opponent’s turn, they’ll choose the move that minimizes our score
3. Propagate values back up the tree

Here’s the core algorithm:

function minimax(board, depth, isMaximizing) {
  // Terminal states
  if (gameWon(board)) return 10000;
  if (depth === 0) return evaluatePosition(board);

  const moves = getValidMoves(board);

  if (isMaximizing) {
    let maxScore = -Infinity;
    for (const move of moves) {
      const newBoard = applyMove(board, move);
      const score = minimax(newBoard, depth - 1, false);
      maxScore = Math.max(maxScore, score);
    }
    return maxScore;
  } else {
    let minScore = Infinity;
    for (const move of moves) {
      const newBoard = applyMove(board, move);
      const score = minimax(newBoard, depth - 1, true);
      minScore = Math.min(minScore, score);
    }
    return minScore;
  }
}

Try playing against the minimax AI with depth 4 (looking 4 moves ahead):

Reset Game

Game Info

Phase: Placement

Current Player: black

Black Pieces: 0/3

White Pieces: 0/3

AI Opponent

Type: Minimax (depth 4)

Evaluation

Heuristic Score: 0

Move History

No moves yet

You’ll notice this AI is much stronger. It creates threats, blocks your wins, and thinks several moves ahead.

Alpha-Beta Pruning: Making It Faster

Minimax explores every possible move sequence, which gets expensive quickly. With branching factor and depth , we’re looking at positions!

Alpha-beta pruning is an optimization that eliminates branches that cannot affect the final decision:

function minimax(board, depth, alpha, beta, isMaximizing) {
  // ... base cases ...

  if (isMaximizing) {
    for (const move of moves) {
      score = minimax(newBoard, depth - 1, alpha, beta, false);
      maxScore = Math.max(maxScore, score);
      alpha = Math.max(alpha, score);
      if (beta <= alpha) break;  // Prune!
    }
  }
  // ...
}

If we’ve already found a move with score X, and we’re exploring a branch where the opponent can force a score worse than X, we can stop searching that branch immediately.

Alpha-beta pruning typically reduces the effective branching factor by about , meaning we can search roughly twice as deep in the same time.

Transposition Tables: Remembering What We’ve Seen

Many different move sequences lead to the same board position. A transposition table (essentially a cache) stores positions we’ve already evaluated:

const cache = new Map();

function minimax(board, depth, alpha, beta, isMaximizing) {
  const key = getBoardKey(board);
  if (cache.has(key)) return cache.get(key);

  // ... search logic ...

  cache.set(key, result);
  return result;
}

This is a form of dynamic programming—we’re breaking the problem into overlapping subproblems and storing solutions to avoid redundant work.

Symmetry: Exploiting Structure

Here’s a critical insight: the board has 8-fold rotational symmetry. Rotating the board by 45° gives an equivalent position:

X . .    . . X    . . .
. . .    . . .    . . .
. . .    . . .    . . X

This now gets us into an area of mathematics called group theory, a topic I’ve never come across before until now. In group theory terms, the board’s symmetries form a cyclic group with 8 rotations. Each rotation shifts pieces around the ring by one position (45°). Let me show all eight rotations of a single position:

Rotation 0°:   Rotation 45°:  Rotation 90°:  Rotation 135°:
X . .          . X .           . . X          . . .
. . .          . . .           . . .          . . X
. . .          . . .           . . .          . . .

Rotation 180°: Rotation 225°: Rotation 270°: Rotation 315°:
. . .          . . .           . . .          . . .
. . .          . . .           . . .          X . .
. . X          . X .           X . .          . . .

All eight of these positions are essentially identical. The center position (marked 8) stays fixed under all rotations, while ring positions shift.

Why Only Rotations?

You might wonder: what about reflections? Tic-tac-toe typically uses both rotations and reflections as symmetries to reduce the search space. The solver implements rotational symmetry but not reflectional symmetry.

Technically, reflections are valid symmetries—mirroring a board position produces a strategically equivalent position. Implementing only rotations simplifies the canonicalization logic: adding reflections would double the symmetry group size (from 4 rotations to 8 symmetries: 4 rotations 2 for reflection) while providing diminishing returns in state space reduction.

Implementing Rotations

Rotating the board is simple. Ring positions shift by one, while the center stays fixed.

function rotatePosition(pos: number): number {
  if (pos === 8) return 8;  // Center is fixed
  return (pos + 1) % 8;      // Ring positions shift clockwise
}

function rotateBoard(board: Board): Board {
  return board.map((piece, pos) =>
    board[pos === 8 ? 8 : (pos + 7) % 8]
  );
}

Canonical Forms and Search Space Reduction

We can use this to reduce our search space by ~8×. Instead of storing every position in our cache, we store only the canonical form—the lexicographically smallest rotation:

function getCanonicalForm(board) {
  const rotations = getAllRotations(board);
  const keys = rotations.map(b => getBoardKey(b));
  keys.sort();
  return keys[0];  // Smallest = canonical
}

This means our 1,680 positions collapse to roughly 1,680 ÷ 8 = 210 unique equivalence classes. Each equivalence class (or “orbit” in group theory terms) represents a set of rotationally identical positions. By storing only one representative from each class, we cut our memory usage and computation time by nearly 8×.

This is a powerful technique used in chess engines, Go programs, and many other game solvers.

The Complete Solution: Retrograde Analysis

Now for the main event: can we solve this game completely?

State Space Analysis

First, let’s count positions. In the 3v3 endgame (after all pieces are placed):

• Choose 3 positions for Black:
• Choose 3 positions for White:
• Total: positions

With 8-fold symmetry, we have roughly unique positions.

For comparison:

• Tic-tac-toe: ~6,000 positions
• Chess: positions (unsolvable by brute force)
• Terni Lapilli: ~200 positions (completely solvable!)

Retrograde Analysis Algorithm

Rather than searching forward from the starting position, we can work backwards from known winning positions:

1. Generate all 3v3 positions (~210 after symmetry reduction)
2. Mark terminal positions (positions with 3-in-a-row)
3. Iterate backwards:
   • If any move leads to our win → this position is winning
   • If all moves lead to opponent win → this position is losing
   • Otherwise, keep searching
4. Repeat until convergence (all positions classified)

This builds a complete tablebase—a lookup table showing the outcome of every position.

function buildTablebase() {
  const positions = generateAll3v3Positions();
  const table = new Map();

  // Mark immediate wins
  for (const pos of positions) {
    if (hasThreeInRow(pos)) {
      table.set(getCanonical(pos), 'win');
    }
  }

  // Retrograde iteration
  while (changed) {
    for (const pos of positions) {
      if (table.has(pos)) continue;

      const moves = getValidMoves(pos);
      if (moves.some(m => table.get(applyMove(pos, m)) === 'win')) {
        table.set(pos, 'win');
      } else if (moves.every(m => table.get(applyMove(pos, m)) === 'loss')) {
        table.set(pos, 'loss');
      }
    }
  }

  return table;
}

Solving from the Start

Once we have the endgame tablebase, we use minimax to search from the starting position. When we reach a 3v3 position, we look it up in the tablebase instead of using our heuristic.

Click below to solve the game completely (takes about 1 second):

Solve Game

Click "Solve Game" button above to see the complete solution.

The solver reveals the game-theoretic truth: with perfect play from both sides, the game has a definite outcome. Every position in the endgame is classified as either:

• Black wins with perfect play
• White wins with perfect play
• Draw with perfect play

Now try playing against perfect AI that uses this complete solution:

Reset Game

Game Info

Phase: Placement

Current Player: black

Black Pieces: 0/3

White Pieces: 0/3

AI Opponent

Type: Perfect Play

Evaluation

Heuristic Score: 0

Move History

No moves yet

Conclusion

Two thousand years after Romans scratched this game into stone, mathematical analysis and computers now reveal its complete solution. Classical game theory, symmetry reduction, and retrograde analysis combine to prove the game’s outcome under perfect play—a technique equally powerful for chess engines, Go programs, and countless other games.

If you find errors or have suggestions for improvement, please share them.