Search

Game Complexity II: Modern Board Game Analysis

Updated: Jan 12, 2021

Pip Modern calculates the complexity of modern classics; Carcassonne, Agricola, and Through the Ages.

Welcome to part two of the game complexity series where we are exploring the complexity of board games. In part one, we discussed a trio of abstract games; tic-tac-toe, chess, and Go. This discussion will reference the figures and methods discussed from that article, so be sure to freshen up on that material before moving on.

Part One: State-Space + Game Tree Complexity

Historically, mathematicians have focused solely on abstract games. This is because the rules are simple and the tightly bound, board dimensions are static, player options are limited, and players alternate taking singular moves. These factors help make the immense calculations a bit simple. There are, however, a choice group of academics exploring modern board games as well We will explore their research and extend their principles to Carcassonne, Agricola, and Through the Ages.

The dissertation, "Implementing a Computer Player for Carcassonne" was written by Cathleen Heyden for her 2009 Masters of Science of Artificial Intelligence at Maastricht University (Netherlands). Heyden begins with the concept by which the state-space for Carcassonne can be calculated. First count the number of unique shapes which can be formed with the seventy-two tiles, ignoring the contents of tiles within said shapes. Then determine the different ways tiles can be arranged and rotated within each shape, and lastly accounting for how meeples could be placed on each shape and tile configuration.

Since this portion of Heyden's thesis is to assert that Carcassonne cannot be solved with a brute force program, she does not need to establish a precise state-space calculation. She instead uses the number of free polyominoes (unique board shapes, accounting for symmetries) as a "highly underestimated" lower-bound state-space for Carcassonne. The number of free polyominoes alone creates a state-space complexity of 40 (slightly lower than chess), but this ignores the "very complicated" next steps of calculating the placement of tiles and meeples within the polyominoes.

This value is a highly underestimated lower bound of the state-space complexity. Due to the facts that games with such high state-space complexity are unsolvable and the calculation of the next steps (placement of tiles and meeples) are very complicated, this result is sufficient.

We'll pick up the research here, and consider tile and meeple placements in our state-space assessment. The equation below represents Carcassonne's state-space as a product of free polyominoes (Hayden's figure), tile placement combinations, and meeple placement combinations. This equation inflates Heyden's low estimate of 40 to 138 (for a two player game). Going a step further to accommodate the full four-player count, rather than the head-to-head scenario Heyden studied, the state-space rises to 162. It should be noted that this figure is an upper-bound for Carcassonne, since the tile placement figure includes illegal placements, and the meeple placement figure assumes that all meeples have been placed on the board.

Heyden's game-tree complexity equation inserts an additional term into the equation we used in part one of this series. In games of pure strategy a player makes evaluations on the board state alone, and has access to perfect information. But in games with elements of chance, players do not have perfect information and must instead weigh their evaluations against the chances of various inputs. Since Carcassonne has chance elements, due to the drawing of tiles, Heyden expands the game-tree complexity equation to include this random element; referred to as chance nodes.

The first term we are familiar with; the branching factor raised to the power of game length, and the second term is similar with c representing the branching factor of chance nodes.

This calculation conceptualizes is a common phenomenon in board games; risk mitigation. Players can play out a few scenarios in their head, assigning point values to each, then weigh each scenario against the probability of it actually occurring. This is closely related to what probability theory calls expected value.

Continuing to refine her game-tree measure, Heyden then defines the chance complexity term. She determines the number unique of tile types to be twenty-four (this figure was later corroborated in a 2012 paper by Lucie Karna which applies combinatorics and graph theory to Carcassonne).

For the branching factor of chance events an average can be taken. There are 24 different tiles and totaling 71 tiles. That means on average after 3 plies the number of different tiles decreases by 1. So the average branching factor of chance events is:

The equation above uses Pi Notation, also known as Product Notation, and indicates repeated multiplication, in this case representing the randomness of drawing tiles.

Now we'll tackle the more familiar terms; average branching factor and number of plies. Carcassonne contains 71 tiles (excluding the starting tile), so the game therefore has 71 plies. Heyden estimates a branching factor of 55, which was determined by leveraging computer simulation (in this case two thousand simulated plays). Completing the equation, Heyden determines Carcassonne's game-tree complexity to be 195, beating out chess (123), but falling far short of Go (360).

The main contributors to Carcassonne's game-tree size are the chance nodes. The random element of drawing tiles exceeds the standard branching factor. It is for this same reason that Stratego, a game where a player's pieces remain hidden from their opponent, ranks so highly in this measure. So while a human might not exhaustively evaluate chance nodes as a part of their decision making process, doing so is required for truly optimal play, which we will explore in the final part of this series.

Within the tabletop hobby it is safe to categorize Carcassonne, as a medium-light game, in regard to complexity. Yet, when compared to abstract games, Carcassonne ranks on the higher side. One game does not a proper sample-size make, but modern board games have clearly escalated the board game genre to new heights. But, instead of calling it quits and waiting for the next Cathleen Heyden, let's flex our brains and see if we can find a game to surpass Go as the king of complexity.

Now, I will admit that there are already games that have been proven more complex (in game-tree terms) than Go; namely Arimaa and Stratego, but I wouldn't classify either as a modern board game. For the purposes of analysis we will use Agricola, and Through the Ages: A New Story if Civilization, as our two contenders. Both rank highly in BGG's weight (read: complexity) score; 3.4, and 4.4 respectively, and are quite popular within the hobby.

Agricola is certainly a modern classic. Even those who have not played it are surely familiar with it, if only by name. It launched Uwe Rosenberg to fame and received a special award by the Spiel des Jahres jury in 2008, along with several other awards. Agricola is also one of the more complex modern board games to have a wide reach across the industry, and will act as a strong benchmark for the industry.

Starting with state-space complexity, we can identify four key sources of variability; occupation cards, minor improvement cards, round action cards, and worker placements. To simplify the calculations we are going to ignore major improvements, resources and livestock, and player boards.

Calculating the permutations of different starting hands is fairly straight-forward. First we take the factorial of the number of cards in the deck, and divide by the factorial of cards remaining. However, permutations are order-specific, and since the order of a hand of cards is irrelevant, we must divide by the factorial of hand-size for each player. This is identical to the approach Claude Shannon used to determine the state-space of chess, which we discussed in part one of this series.

Moving on to the round action cards, we simply multiply the possible combinations of each of the six stages together. The first stage has four action cards, the second has three, and the rest have two each, except for the sixth stage which only has one.

The most complicated part of Agricola's state-space measure is determining the number of unique worker placements. For simplicity's sake we will assume that each player the same number of workers for the duration of the game. Based on our analysis of Agricola, we estimate that each player dispatches an average of 2.8 workers per round.

Using the equation above, we can now simply plug in our numbers, and evaluate our equation. Note the dependence on player count in three of our four terms. As would be expected, increasing the player count dramatically increases the complexity.

Even at two players, the count at which all our other examples have been calculated, Agricola earns relatively high marks. A game of Go has more board states than a two player game of Agricola, but things change quickly with the inclusion of additional players. At five players, Agricola's state-space complexity nears the game-tree complexity of Go, which is quite surprising.

To calculate game-tree complexity of Agricola, we do not have the privilege of running thousands of computer simulations as Heyden did for Carcassonne. Luckily, the number or plies in Agricola is directly linked to player count making it simple to calculate. Each player plays all fourteen rounds and places all their workers each round. If we consider each Harvest phase as one ply per player, a five player game has 226 plies (90 in a two player game).

Based on our analysis of Agricola's action spaces, we estimate the branching factor to be 80 in a five player game (60 in a two player game). In real terms, the branching factor increases with each round, as more actions become available, but our straight average will suffice for a lower-bound. Inserting these values into our game-tree complexity equation we determine that Agricola has a game-tree complexity of 430 (160 for two players).

While a full player game of Agricola is more complex than a similar game of Carcassonne, the two games are neck and neck in the two-player space. And in this two-player space, Go still proves more complex than both of our modern contenders. It's only with the inclusion of additional players that our modern board games exceed Go. But, Vlaada Chvátil has something to say about that.

Vlaada Chvátil's Through the Ages (TtA) engine certainly deserves our consideration, as it is the second heaviest game in BGGs top 100 (as of this writing). Through the Ages has been melting heads since 2006, and has since been reimplemented in 2015, and ported to digital in 2017. The game is card driven, with over three hundred cards distributed throughout eight decks. Leveraging our previous complexity equations we can quickly define TtA's complexity, again ignoring player board and the like.

While the above equation is visually busy, it's simple in its premise. First we determine the order in which each of the decks can be drawn, multiplying each Age together. We then account for duplicate cards, the three different sections of the card row, and the contents of each player's hand.

In our conversation with Matúš Kotry, the developer of the Through the Ages mobile app and designer of Alchemists, he estimates an average civil hand limit of six, and we can estimate a military hand size of three. Applying these estimates to a four player game of Through the Ages we calculate a resulting state-space of 299 (239 with two players).

Even ignoring the development of technologies or wonders, the yellow or blue banks, military tactics and strength, happiness, territories, etc, the state-space complexity of Through the Ages is about on par with Agricola at the same player count.

Having analyzed several full-AI games of Through the Ages, Matúš Kotry determined that each civil action can be executed in at least eighteen different ways, but believes this number is actually closer twenty-three in games with human players. Based on Kotry's conservative estimate, there are over three million legal uses for a player's civil actions alone.

Account for military actions and event card play, and this number explodes to 226 billion. Assuming a game length of seventy-six, the resulting game-tree complexity is 863 when playing with a full accompaniment (431 with two players).

It's worth mentioning that if we instead considered each action in Through the Ages (civil and military) as a single ply (rather than a full turn as one ply) the game-tree complexity calculation would yield an identical result, at least ideally. In our simplified analysis, rounding and averaging errors introduce a small variance, but both methods are valid. In this alternate scenario the total number of plies would increase to 760, but the branching factor would reduce to about fourteen, resulting in a game-tree complexity of 871 (which is quite close to our original calculation of 863). But, regardless of viewing a single turn as choosing between two hundred billion possibilities once, or as choosing between fourteen possibilities ten consecutive times, Through the Ages proves a colossal challenge.

Zooming back out, let's consider all of the games discussed thus far. Plotting all of these games based on their two complexity measurements, we can easily see that modern board games are becoming increasingly complex. While Go and Arimaa are notable champions of abstract games, modern board games such as Agricola and Carcassonne can hold their own, while Through the Ages represents a colossal step forward in complexity.

These complexity calculations identify a key factor contributing to the recent growth of the modern board game industry. Despite the complexity of designer games, they are largely more accessible than Go and other abstracts. Abstract games are more difficult to initially grasp because they hold little connection to the real world, failing to contextualize the decision-making process. Chess and Go exist in a space that lacks context, making the games harder to comprehend, whereas Agricola utilizes the recognizable themes and tropes of agriculture to provide a familiar structure in which to frame the rule set. That is not to say that all modern games are accessible to a general audience, Through the Ages proving a great example, but even the idea of building a civilization, a common historical phenomenon, has elements most people can use to internalize the rules and strategy.

In the final entry in this series, we will pit mind against the machine, and explore the world of artificial intelligence, and discuss how game complexity has become the benchmark for computational decision-making.

Special thanks to Matúš Kotry and the folks at Czech Games Edition for providing some of the data from the Through the Ages app which empowered our complexity calculations. Be sure to check out the amazing Through the Ages app (iOS, Android) and Kotry's own Alchemists. CGE did not in any way sponsor this article.

Note: In a 2018 paper regarding the complexity of Kingdomino, the 2017 Spiel des Jahres winner, Tomologic AB calculates its game-tree complexity to be 106. The research does not provide a state-space complexity evaluation and as such is not discussed in detail in this article.

Part Three: Artificial Intelligence

References:

Arts, A.F.C. “Competitive Play in Stratego.” Maastricht University, 2010.

Gedda, Magnus, et al. “Monte Carlo Methods for the Game Kingdomino.” Tomologic, 15 July 2018.

Heyden, Cathleen. “Implementing a Computer Player for Carcassonne.” Maastricht University, 2009.

Karna, Lucie. “Carcassonne - Description of the Game.” Czech Technical University, Conference Applications of Mathematics 2012, 2012, pp. 107–116.

Kotry, Matus. 2018.

Wu, David Jian. “Move Ranking and Evaluation in the Game of Arimaa.” Harvard, 2011.