Why are Ties Impossible in Catchup?
Now and again I get an email/text/carrier-pigeon from someone who’s playing my abstract game Catchup, noting that only after many plays did she realize it’s impossible for the game to end in a tie.
Unlike other games with ultra-simple rules, such as your combinatorial games (“last-mover-wins” games, such as Amazons), or your fundamental connection games (e.g. Hex), the reason for Catchup’s drawlessness isn’t obvious. So I’ve decided to make it obviouser with the following explanation.
For those unfamiliar with Catchup, it’s played on a hexagonal board with a scoring track around it, like this:
The board starts out empty and the players take turns. Except for the first turn (where there’s a special balancing rule), you place 2 stones onto any 2 empty spaces on each turn, unless your opponent, on his most recent turn, advanced farther along the scoring track than either player had gone up to that point, in which case you may place 3 stones on your turn.
The game ends when the board is full and the player with the largest contiguous group of stones in her color wins. If the players’ largest groups are the same size, they compare their second-largest groups, and so on, until they come to a pair which aren’t the same size, and whoever owns the larger of the two wins.
What’s not obvious is that players will always come to a pair which aren’t the same size, so one player will always win. Why?
First, notice there’s an odd number of spaces on the board. That’s true no matter what size board you use as long as it’s a regular hexagon. This is the key.
Let’s say the two players’ largest groups are the same size. When you add up the total number of spaces occupied by those two groups, that number must be even, because both groups occupy the same number of spaces and any number times 2 is even.
Now let’s say the players’ second-largest groups are both the same size as well, so the total number of spaces they occupy must also be even.
Because an even number plus an even number is even, the total number of spaces collectively occupied by both players’ largest and second-largest groups must also be even.
Ergo: if you keep going down the line, comparing the players’ 3rd largest, 4th largest, and so on all the way to the players’ smallest groups, they will all sum up to an even number as long as the players’ groups are the same size at each level.
But! Since there’s an odd number of spaces on the board, the total sum must be odd when the board is full, which means at that point there must be some pair of opposing groups on the board which aren’t the same size. Which means, voila and abracadabra, one player must win.
I’ve played Catchup more than 800 times now, and the closest game I’ve seen was decided on the players’ third largest groups. I’ve seen that happen twice, once between two humans and once between a human and an AI. I managed to record the former game and will soon post a turn-by-turn breakdown to illustrate what a really close game of Catchup looks like. I love such games. Playing in one feels like finding a 4-leaf clover. A 4-leaf clover that causes heart attacks.
Three Related Points
First, the nested tie-break system adds a layer of strategy of which new players aren’t aware. Against a skilled opponent, you have to worry not only about the size of your largest group, but also the size of your smaller groups (second-largest-group endings are common among skilled players), which requires shifting strategy in important ways. One of the reasons I adore good abstract strategy games is that they have layers of hidden complexity, but it also makes it hard to promote them, because so much of the creamy filling is so hidden. At least I can try to point out where hidden complexity hides out in my own games. I’ll discuss this and other subtleties of Catchup in future posts.
Second, we’ve made an effort to find an imbalance between the two sides by playing a very strong AI against itself, millions of times, and we can’t find even the slightest sign of imbalance. The nested tie-break system is partly responsible, I believe. I’ll pontificate about why in a future post as well.
Third, although Catchup can’t end in a tie, it can get real close.