Territories and the Theory of Perfect Information Games
My friend Ryan Miller sent me an Excel spreadsheet with a game he’d invented called Territories. It had the satisfying quality of a good pencil-and-paper game: the rules fit in a sentence, but the strategy is unclear. It feels like a simplified Go.
Players take turns claiming empty squares on a 10×10 board. A square is worth one point for each orthogonally adjacent square owned by the same player. When the board is full, the player with the highest score wins. There are no dice, hidden cards, captures, or resources to collect—just a shared grid and a choice of the next square.
That makes it a nice little example of a perfect-information game: after the starting player is chosen, every player can see the entire state and every legal move. Perfect information, however, is not the same thing as an easy solution.
From spreadsheet to Flex
I turned Ryan’s workbook into a small Adobe Flex application. The setup screen supported one to four human or computer players, each with a color and, for computers, a selectable strategy.
The implementation is deliberately small. The board model stores a player (or no player) for each square; the UI paints that ownership and advanced the turn. At the end, it adds up the scores and announced the winner.
The scoring rule has a useful consequence. A shared edge between two of your squares is counted once by each square, so it is worth two points to you. If an empty square touches k of your own squares, claiming it changes your score by 2k.
That is the tension of Territories. A cell in the middle of your growing region can be immediately valuable; an empty cell that would complete somebody else’s region may be more valuable to deny. Early moves tend to be tied at zero, so the consequences only become visible as the board fills.
Perfect information, but a lot of states
For a fixed turn order, a complete game has 100 moves. The first player has 100 choices, then 99, then 98, and so on: 100! — about 9×10157 — possible move sequences before even considering how to evaluate them. Many sequences lead to the same board, so a serious solver would memoize board states, but that only trades one enormous number for another. A two-player game has at most 3100 ≈ 5×1047 labeled boards, and even the final positions alone—the ways to split 100 squares evenly between two players—number about 1.0×1029. For scale, checkers has roughly 5×1020 positions, and Jonathan Schaeffer’s group needed eighteen years to solve it.
What perfect information buys you is a guarantee that an answer exists. Ernst Zermelo proved in 1913, in a paper about chess, that a finite two-player game with no hidden state and no chance is determined: either one player can force a win, or both can force at least a draw. John von Neumann and Oskar Morgenstern supplied the machinery in Theory of Games and Economic Behavior (1944), which represents a game as a tree annotated with what each player can and cannot distinguish, and solves it by backward induction—label the leaves with their payoffs, then walk upward, letting each node take the best value available to whoever moves there.
Solved by symmetry, not by search
Searching this game is hopeless. It turns out not to need searching.
Take σ, the rotation of the board by 180°: σ(i, j) = (9 − i, 9 − j). The second player can answer every move by mirroring it through the center:
Whenever the first player claims x, reply with σ(x).
The reply is always available. After each of the second player’s moves the position is symmetric under σ, so the empty squares are symmetric too; if x is empty then σ(x) is empty as well, and σ(x) is never x itself. When the board fills, the second player’s region is precisely the mirror image of the first player’s. σ preserves adjacency, so the two regions contain the same number of internal edges, and the game ends level.
In this way, the second player can force a draw on a 10×10 board. (Note: When both sides are odd there is a center square, and the argument changes hands: the first player takes the center and mirrors from then on. Each of the center’s four neighbors sits in a two-element orbit of σ, and the second player is forced to take exactly one square from each orbit, handing the first player the other. The first player finishes with exactly two more internal edges—a four-point win.)
Four small AIs
Mirroring is kind of boring play, and it’s not clear how this analysis should extend to games with more than two players. So the computer opponents in this version play based on a few heuristics.
The first bot chooses a legal square at random. It is a baseline, not a serious opponent. The other three all evaluate every empty square and picked randomly among ties:
- Offensive chose the square with the largest immediate score increase for itself.
- Defensive chose the square with the largest combined immediate increase available to the other players, denying their most attractive next move.
- Combo chose the square with the largest total immediate value across all players—a rough way to identify the most contested part of the board.
The distinction is subtle but makes the board behave very differently. The offensive bot turns its color into large compact regions. The defensive bot is happy to give up points if it can prevent everyone else from connecting a pair of squares.
In one three-player match, the Offensive player won the local fight, while the Combo and Defensive players trailed behind:
Two Defensive players will make an alternating checkerboard and finish with no matching neighbors at all—zero points for both sides:
Two Offensive players do nearly the opposite:
What the toy game taught me
Territories is fun to play, and a fun intro to the theory of games. The state is completely visible, the move rules are deterministic, and the score can be evaluated with four neighbor checks. The eventual value of a move still depends on the entire sequence of claims that follows it—and, with several players, on several competing objectives.
Update
The original application was a Flex/Flash project, so it is more archival than playable today. Its source code, the Excel original, and the screenshots remain a small record of a game that was much richer than its rules first suggested.
With the help of Claude Code, you can play a version of the game that has between ported to vanilla HTML/CSS/JS here.
