One of the most basic ways to describe the computational complexity of a game is its state space complexity—that is, the number of unique positions possible for a game—and that’s where I’ve started in my analysis of computer tafl. For now, and probably for every post I write on tafl and mathematics, I’m going to stick with Fetlar rules tafl or Copenhagen rules tafl¹, on an 11×11 board.

To start off, we can make an extremely, extremely rough estimate. The board has 121 spaces, and each space can be empty, occupied by a besieger, occupied by a defender, or occupied by the king, so to get an absolute upper bound, we can just do this:

7 x 10⁷² is surprisingly close to the rough estimate for chess (1.9 x 10⁷¹; chess has thirteen states per space and 64 spaces). We know the actual state space complexity of chess to be in the vicinity of 10⁴⁷, however, so we can clearly do better. And, if you think about it, we’re not even trying all that hard. Our current estimate permits some flagrantly illegal positions, like a board entirely filled with kings, or the board with no taflmen.

There are plenty of obvious constraints we can use to tighten up our guess. For one, any reachable tafl position has to have at least three taflmen: one side must have two taflmen, to have captured the second-to-last piece from the other side, and the other side must have at least one taflman left, or else the game is over. For another, there are only 37 taflmen to place.

An intermediate question presents itself: in how many different ways can three to 37 taflmen be placed on 121 spaces? Well, that’s a question for combinatorics. For any number n of taflmen, the number of unique arrangements of those taflmen into 121 spaces is:

And, since I’m a programmer, and loops come naturally to me…

So, we have 3 x 10³¹ ways to arrange our taflmen onto our board. Going forward, I’ll multiply it by one quarter², although it hardly matters at this scale³. This picture is also incomplete—it’s not an upper bound, because it doesn’t account for taflmen belonging to the besieging or defending sides. For every arrangement of n taflmen on the board, there are a bunch of distributions of the taflmen between the besieging and defending sides, and a bunch of options for the position of the king within the defending side.

So, since I am still a programmer, time to break out the nested sums. For every number of taflmen i between three and 37, consider the distribution of taflmen between the sides. For valid positions, let k be the number of pieces on the defending side, between one and i – 1. We need only consider one side. From a logic perspective, it’s obvious why: answering the question, “How many ways are there to assign k taflmen to the defending side?” contains in its answer the answer to the question, “How many ways are there to assign i – k taflmen to the besieging side?” Since the two sides exist on the same board, the number of defending positions is the number of attacking positions. (There’s a mathematical argument in a footnote⁴, if you don’t buy this.)

Anyway, that insight gets us most of the way there. We have one more thing to account for: the position of the king. One of the defending taflmen must be the king for this position to be valid, and the king is distinct from every other defending taflman. Any one of the k defending taflmen could be the king: that is, there are always exactly k distinct arrangements of the defending taflmen for any distribution of taflmen between the sides, so we multiply the two numbers together.

There we have it: the number of possible arrangements of taflmen on the board for every valid number of taflmen, multiplied by the number of ways to split a certain number i of taflmen between each side, is a much better bound on the number of possible positions. It’s still not perfect: mainly, this model permits some positions where pieces have illegally stopped on restricted spaces, and I’m probably missing some other things, too, but it’s a close enough bound to make an interesting point.

11×11 tafl games have an upper bound on state space complexity on the order of 10⁴³. Chess, as I mentioned earlier, has a state space complexity on the order of 10⁴⁷. This might seem like evidence against my theory that tafl games are more computationally complex than chess, but I’m still convinced. Ultimately, state space complexity is a poor measurement of computational difficulty. Consider backgammon: its state space complexity is on the order of 10²⁰, but backgammon AI is a more difficult problem than chess AI.

There is another metric to introduce: that of game tree complexity. State space complexity measures the number of possible positions for a given game. Game tree complexity measures, in a sense, the number of ways to get there. Consider a tree of every possible game of tafl. You start, obviously, with the starting position, then create a leaf node for every possible move by the defending player. At each of those leaves, create leaf nodes for every possible response for the defending player, and so on until every possible combination of moves has resulted in a game-ending state. (We’ll assume there are no ways for games to go on forever.) The number of leaves at the bottom of the tree is the game state complexity.

This number, Wikipedia remarks in its typical laconic style, is “hard even to estimate.” This is true. Wikipedia also remarks that a reasonable lower bound can be established by raising the branching factor, the average number of moves possible at any given step, to the power of the game length in plies (that is, one player moving once). This is where things start to get interesting.

The accepted figure for chess’s branching factor is 35. From the starting position, each player can make 20 distinct moves. (Pawns forward one or two squares, or knights to the inside or outside.) Chess games last, on average, about 40 turns, or 80 plies. The game tree complexity of chess is at least 10¹²³. Backgammon’s branching factor is 250, and its average game length is about 60 plies, so its game tree complexity is at least 10¹⁴⁴.

I don’t have a figure for tafl’s branching factor. Aage Nielsen’s tafl site has a tournament running right now, using the Copenhagen tafl rules. Once it’s finished, I’ll look at some positions from the midgame and the endgame and try to work out a good average. In the interests of providing a number, I tweaked OpenTafl’s debug script to print out a count of the number of possible moves on the opening turn. The besiegers can make 116 moves, and the defenders can make 60, for an average of 88. High-level tafl games seem to go on for about 40 turns or 80 plies, from my observation so far. This yields a lower bound of 10¹⁶⁷, which rather blows chess out of the water.

Let me try to contextualize that number. Relatively simple 11×11 tafl games are, as far as I can tell, more computationally difficult than any historical abstract strategy game besides go. Not only that, but larger tafl games (15×15 or 19×19 variants) seem likely to me to be more difficult than go.

If you’re not well-read on the subject of board game artifical intelligences, you may have missed what a crazy thought that is. Go is the benchmark for hard AI problems. Computers were playing chess and backgammon at grandmaster levels by the end of the 1970s. Computers still can’t beat professional go players in even games, and the hard tafl variants are probably harder than that.

This is a seriously cool game.

1. Here are rules for the Fetlar and Copenhagen variants. If you don’t care to read them, here’s the summary: they’re more or less identical for my purposes here, played on an 11×11 board with 12 defenders, one king, and 24 attackers.
2. Think about it: any arrangement of taflmen on the board is functionally identical if you were to rotate the board 90 degrees beneath them in either direction, or 180 degrees.
3. Remember, with scientific notation, 8 x 10⁵ divided by four is 2 x 10⁵. Or, indeed, 8 x 10⁰ divided by four is 2 x 10⁰.
4. Let i be the number of taflmen on the board, k be the number of defending taflmen, and i – k be the number of besieging taflmen. The number of distributions of taflmen for the defenders is:

Therefore, k taflmen have already been accounted for—the besieging side can’t choose them, because they’ve been chosen as defending taflmen. We do not choose from i, we choose besieging taflmen from from i – k, which yields:

Which is one, and can be simplified out.