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:

A game of Catchup, in early mid-game

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.


5 thoughts on “Why are Ties Impossible in Catchup?

  1. I just encountered Catchup, and I like it. I’m looking forward to playing it, and especially looking forward to the iOS version.

    But I’m confused about this specific analysis, because it seems to me to assume that no one player has two groups of the same size.

    There are 61 hexes in the basic board. What if one player has a group of 26 and a group of 3, and the other player has a group of 26 and two groups of 3? Or, to make the total number of stones on each side closer to equal, what if each player has a group of 29 and a group of 1, and one of the players also has another group of 1?

    You’ve played a lot of games and never encountered a tie, so it may well not be possible to tie. But I feel like your specific argument here doesn’t account for this three-groups-of-the-same-size situation. But I may well be missing something.

    1. Ah, you’ve misunderstand the rules, probably because I’ve written them too vaguely. In the first example you give, the score would be 26-3-3 to 26-3-0. In other words, one player’s third largest group is considered be size zero. In the second example, the score is 29-1-1 to 29-1-0. The reason I’m not more explicit about it in the rules is that I don’t believe it will ever happen in an actual game and I like to keep the rules as simple as possible. Nonetheless, in all the cases where the game has been implemented online, or in the iOS version under development, the game has always been implemented with these rules.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s