*With your numerous settlements and cities built *around* the island, your nascent empire is gaining momentum. Every turn, you receive plenty of resources, and your extensive road network establishes your domination of the land. But just as you were about to do your final move and reap a well-deserved victory, your adversary brings out his army and crush your dreams with his palace, university, and library… Did you pick the wrong *strategy?

***Latest update: Someone pointed to me that one victory condition is unattainable. One cannot achieve a 12 points victory without actually constructing a new settlement. Which, aside from being completely true, also brings back the total count to 142!!*

***Update: I received a lot of feedback, and some careful readers have spotted some errors! *

*My analysis apparently missed some possible victories: The title should be The 143-ways to win at Catan (a bit embarrassing, I know!). *

*I’ve made the adjustment to the data to reflect this.*

*The main graph shows the 114 normal ways to win at Catan for the moment, but the full list of victory now includes 143 victories, with all the explanations.*

*Thanks for all the feedback! *

## What to expect from this post

Since Catan is a strategy game, it is always good to have some basic strategy at the start of the game that should guide your early decision making.

After playing a bit with different aspects of the game, I decided to have a look at the victory condition of Catan… And how to reach them!

So we will start today by a making an exhaustive list of all the ways you can win at Catan, with a breakdown of the elements involved in each victory… And their cost!

For those who are already familiar with Catan, here is a quick preview of the results. But you will have to read further down to get the juicy details, with all the information needed to understand what is going on here…

This is the first part of a three-part article, so here what to expect:

- We are starting today with the
**Minimum cost involved in each victory**. - Next time I’ll present you the
**Expected Cost of winning**, taking into account the true cost of randomness for each win. - The third article will attack the even more important aspect:
**How quickly can each victory be achieved**.

**But enough with the preview, let’s start analyzing!**

Today I will present to you **the multiple ways of winning at Catan**, independently of the initial board conditions. While any strategy must take into account the initial board placement, maybe we can find interesting strategies to tilt the chances in our favor, and the astute reader will only need to select the best strategy fitting the opportunity the board offers at the beginning of the game!

And since this blog intends to be as much about data science, math, and programming than about board games, I will give you a detailed account on how I arrived at my conclusions. In this article, you’ll be able to expand textbox with technical details that may be of interest to you (the math, the code, and longer definition and tables). So feel free to explore (or not), the content of those boxes!

The first example of this would be a description of the game itself, for those who have never played and wants a better understanding of the game:

[accordion tag=h3 clicktoclose=”true” style=”accordion-container” style=”accordion-style1″]

[accordion-item title=”+ **For those unfamiliar with the game**” id=unfamiliar-with-the-game-catan-001 state=closed style=”accordion-style1″]

Settlers of Catan is a family game for 2 to 4 players aged 10 or more. But I’ve played with 8 years old without any problems.

Here is the gameplay description, taken from the Wikipedia Catan page.

*The players in the game represent the settlers establishing colonies on the island of Catan. Players build settlements, cities, and roads to connect them as they settle the island. The game board, which represents the island, is composed of hexagonal tiles of different land types, which are laid out randomly at the beginning of each game. Newer editions of the game began to depict a fixed layout in their manual, which has been proven to be fairly even-handed by computer simulations, and recommend this to be used by beginners. In 2016, editions of the game were released with a conventional fixed layout board in this configuration, the hexes of which cannot be rearranged.*

*Players build by spending resources (brick, lumber, wool, grain, and ore), represented by resource cards; each land type, with the exception of the unproductive desert, produces a specific resource. On each player’s turn, two six-sided dice are rolled to determine which hexes produce resources. Any players with settlements or cities adjacent to hexes marked with the number rolled receive resource cards of the appropriate type. There is also a robber token, initially on the desert; if a player rolls 7, the robber must be moved to another hex, which will no longer produce resources until the robber is moved again; the player may also steal a resource card from another player. In addition, when a 7 is rolled, all players with more than 7 resource cards must discard half of their cards, rounded down. However, the player gets to choose which half of their resource cards they must discard. For example, a player with 11 resource cards must discard any five cards when a 7 is rolled.*

*Players can trade resource cards among each other; players may also trade off-island (in effect, with the non-player bank) at a ratio of four of one resource for one of any other. By building settlements in certain spots on the edge of the board (ports), players may trade with the bank at three-to-one (3 of any single resource type) or two-to-one (two of a specific resource) ratios, determined by the port’s location.*

*The goal of the game is to reach 10 victory points. Players score one point for each settlement they own and two for each city. Various other achievements, such as establishing the longest road and the largest army (by playing the most knight cards), grant a player additional victory points.*

*Resource cards can also be spent to buy a development card. Three types of development cards include cards worth one victory point; knight cards (or soldier cards), which allow the player to move the robber as if they had rolled a 7 (but without the remove-half rule); and a third set of cards which allow the player one of three abilities when played.*

[/accordion-item]

[/accordion]

## How to win at Catan

With all the randomization and elements of chance involved, it is safe to assume that no two Catan game will ever be the same.

But winning is decided by points, the winner being the first player to score at least 10 points. (I say at least because for some winning combinations you end up scoring 11 points).

There are only 5 different ways of scoring points in a game of Catan

**The Longest Road**score 2 points (requires at least 5 continuous road segments)**The Biggest Army**score 2 points (require at least 3 knights development cards)**Cities**: 2 points each**Settlements**: 1 point each**Victory Point Cards**: 1 point per card (from purchased development cards)

In order to list all the possible ways to win, I decided to apply a bit of programming to the problem, and with some tweaking of the useful knapsack problem algorithm, I arrived at the following conclusion:

**There are only 114 different possible combinations of points for the winning player!**

If you are interested to know how I determined the possible victories, feel free to open the following textboxs:

[accordion tag=h3 clicktoclose=”true” style=”accordion-container” style=”accordion-style1″]

[accordion-item title=”+ **The knapsack problem**” id=knapsack-problem-catan-001 state=closed style=”accordion-style1″]

As its name indicates, the knapsack problem is about a bag, and more specifically, about how to fill it.

It is a recurrent real-life problem. May it be a knapsack, a suitcase, or the cargo bay of a transatlantic ship, you probably want to fill it at maximum capacity, while maximizing some variable. It may be the weight, the cash value, or the shipping cost, depending on the situation at hand.

Generally, in the knapsack problem, we do not care about the ordering of the items. Your intention can be either:

- Enumerate how many different ways you can fill it
- Find the best way to fill it in term of space, weight, or value of items you put into it

In the second case, you are probably looking for **the best combination** of items for your purpose, so you need to establish the official metric you will use to compare solutions. It could be, for example, that you want to fill all the space in your truck, but with the lightest load. So the weight would be your measure, and you would evaluate each combination of items that fill your truck to see which one is the lightest.

It is good to note that the knapsack problem is a **np-hard** problem. This means that to the best of our knowledge, the only way to find the best solution is to try and measure all possible solutions. No rule of thumb will help you, there is no shortcut possible, you have to try all solutions one by one if you want to be sure you have the absolute best option.

### Catan victory as knapsack filling

For our purpose, you can think of a Catan victory as a knapsack you fill with victory points. This specific bag is a 10 victory points bag, and you fill it with elements taking 1 or 2 victory point space.

In our case, however, the bag is a bit special, it can sometimes contain 11 victory points, but only if you put into it a two victory point element as the last item, when there is already 9 points in the bag.

In our knapsack problem, we will assume that you put it last without worrying about the actual ordering of items. We will simply only accept 11 points solutions if they contain one of the two following 2-points victory item: **The longest road** or **the biggest army**.

Note: **Cities** are two-points victory items also, but they are actually an upgrade of a settlement. So you can only score one point at a time with a city, impossible then to jump from 9 to 11 in one go. So in a real game, you would stop at 10, with no need to actually upgrade your settlement to win.

### Are we optimizing anything?

In Catan, you could very well decide to optimize for the solution that needs the fewer resources. It is what we are implicitly after here. However, since we want to further compare the victories with other criteria, we will enumerate all possible ways to fill the victory knapsack.

Another thing we could decide to optimize for is to go after the victory necessitating the smallest amount of a specific resource. Maybe because only low probabilities are attached to certain resources. Only your imagination limits the thing you can optimize for!

In our case, we are interested in listing all solutions, which will hopefully allow for some nice graph to be drawn! One thing that allows us to do that here is the small number of possible outcomes.

Only 114 ways… If the bag was larger, with more elements to choose from, the list of possible options would grow extremely fast, and making an exhaustive listing of all possibilities would be very expensive in terms of computer time and space!

### So what is the knapsack algorithm?

It is an ordered way to try all the combinations of adding elements in the knapsack, in order to not miss any. And it uses one useful trick of programming to limit the actual code we have to write: recursion!

This means we write a single central function that will place elements in our metaphorical bag, and then call itself again, as if the remaining space in our bag was a new smaller bag to fill, with less items available to be put into it.

Since there is one function calling itself, we also need to check each time if the bag is full, with a correct solution. And if so, we simply add the current solution to the official list, without calling itself again.

Here is a small example with a toy problem:

- We want to fill a bag with 6 spaces
- 4 types of blocks
- One green rectangle (taking 2 spaces)
- One purple rectangle (taking 2 spaces)
- One reddish oval (taking 2 spaces)
- Four blue blocks (taking 1 space)

The algorithm will produce an exploration tree a bit like the following one, each layer being deeper in the recursion:

In this particular case, there are only 7 solutions. I have only shown the valid paths.

Note that the tree would also produce invalid solutions (partially filled bags with no blocks left to add) that are weeded out as we encounter them… But I did not include them here for the sake of clarity.

Ok. I don’t know if this makes sense to you… If not, let me know, I’ll try to do better!

For now, let’s go back to the interesting part: **What are those 114 ways to win at Catan…**

[/accordion-item]

[accordion-item title=”+ **I want to see some code**” id=knapsack-problem-sample-code-catan-001 state=closed style=”accordion-style1″]

As a test for this blog, I decided to include some **Java code** showing how to obtain all the winning combinations involved.

This is my implementation of the knapsack problem algorithm. You should be able to use this code as-is, to obtain a list of all possible victory.

Let me know if you have issues! And let me know if you find this useful or interesting!

Since code is always controversial, I’m pretty sure I’ll offend a ton of people, no matter what, so be kind and skip this if you don’t like my code! Or send me some suggestions for improving it!

I’ve tried to format it so it displays nicely in the given space.

import java.util.HashMap; import java.util.Map; enum VictoryPointType { LONGEST_ROAD(2), BIGGEST_ARMY(2), CITY(2), CARDS(1), SETTLEMENT(1); public int points; VictoryPointType(int points){ this.points = points; } } public class WinningCombinations { public static void main(String[] args){ WinningCombinations winning = new WinningCombinations(); int[] victoryPointTypeUsed = new int[]{0, 0, 0, 0, 0}; int[] victoryPointPossible = new int[]{1, 1, 4, 5, 5}; int totalCount = winning.getCombinationCount(victoryPointTypeUsed, victoryPointPossible); System.out.println("Found winning Combinations: " + totalCount + "\n"); for(int[] solution: winning.allVictorySolutions.values()){ System.out.println(solution[0] + " Longest Road\t" + solution[1] + " Biggest Army\t" + solution[2] + " Cities\t" + solution[3] + " Settlements\t" + solution[4] + " VP Cards\t" ); } } static VictoryPointType[] listOfVictoryPointType = new VictoryPointType[]{ VictoryPointType.LONGEST_ROAD, VictoryPointType.BIGGEST_ARMY, VictoryPointType.CITY, VictoryPointType.SETTLEMENT, VictoryPointType.CARDS }; static private int longestRoadIndex = 0; static private int biggestArmyIndex = 1; static private int citiesIndex = 2; static private int settlementIndex = 3; static private int vpCardsIndex = 4; //This will keep track of all found solutions to the problem Map&amp;lt;String, int[]&amp;gt; allVictorySolutions = new HashMap&amp;lt;&amp;gt;(); /** * This is a recursive function. * It starts with an empty solution, and explore all combinations by * adding possible items to the solution * When it reach a solution, it saves it to the Solution HashMap * * @param victoryToDate Array containing what was added up to * this point. * (Needed to verify the final solution) * @param victoryItemLeft Array containing what can still be added * @return The total number of found acceptable combinations */ public int getCombinationCount(int[] victoryToDate, int[] victoryItemLeft) { //How many victory points in the current solution ? int victoryPoints = calculatePoints(victoryToDate); //If we have more than 11 victory points, it's too many if(victoryPoints &amp;gt; 11) { return 0; } //If we have reached 10 points (or 11 points) then //this is a valid final solution. if(victoryPoints &amp;gt;= 10) { //We introduce this check to invalidate solution //But allowing to continue in case we miss a 11-pt solution boolean validSolution = true; //We do not accept solution with less than 2 city+settlement // (as players start with 2 settlements each) if(victoryToDate[2] + victoryToDate[3] &amp;lt; 2) validSolution = false; //Special case //We exclude 11 points solution if it does not include //One of Biggest Army or Longest Road. //Those are the only way to score 2 points at once in the game //Allowing you to go from 9 to 11 victory points if(victoryPoints == 11 &amp;amp;&amp;amp; (victoryToDate[0] + victoryToDate[1]) == 0) return 0; //Simpler to use a String as Key for the HashMap String victoryString = getVictoryString(victoryToDate); //Saved found solution!! if(validSolution &amp;amp;&amp;amp; !allVictorySolutions.containsKey(victoryString)){ allVictorySolutions.put(victoryString,victoryToDate); return 1; } //We will allow solution at 10 points to continue in case it would // prevents us to find a valid 11 point solution } //If we reach this point, //we are now expanding a not yet complete solution. //We need to add new victory points from the ones //still available. //Keep track of the number of found solutions int accumulatedCount = 0; //We Consider adding in turn all the types of items for (int i = 0; i &amp;lt; victoryItemLeft.length; ++i) { //We consider all the ways to add each type of items. // From 0 to n of them. //Then we are be done for this type item for (int j = 1; j &amp;lt;= victoryItemLeft[i]; ++j) { //Make a copy of the current partial victory condition int[] nextVictoryToDate = new int[victoryToDate.length]; System.arraycopy(victoryToDate, 0, nextVictoryToDate, 0, nextVictoryToDate.length); //Add n considered victory point elements for this item nextVictoryToDate[i] += j; //Make a copy of the current Possibilities left int[] nextVictoryItemLeft = new int[victoryItemLeft.length]; System.arraycopy(victoryItemLeft, 0, nextVictoryItemLeft, 0, nextVictoryItemLeft.length); //Adjust copy accordingly to the victory item we just used nextVictoryItemLeft[i] -= j; //Recursive call to function // Exploring all possible options spawning // from the current partial solution. accumulatedCount += getCombinationCount(nextVictoryToDate, nextVictoryItemLeft); } //Make the explored item zero. //This avoid coming back to this item in the following //recursive calls. victoryItemLeft[i] = 0; } //Return number of found solutions return accumulatedCount; } /** * Calculate how many victory points there is in a solution * * @param victoryToDate * @return Number of victory points in a solution */ public static int calculatePoints(int[] victoryToDate) { int points = 0; for (int i = 0; i &amp;lt; victoryToDate.length; ++i) { points += victoryToDate[i] * listOfVictoryPointType[i].points; } return points; } /** * This transform an Array containing a victory into a string format * * @param victoryToDate * @return victory array in a tab separated String eg: "1 0 0 0" */ private String getVictoryString(int[] victoryToDate) { String victoryString = ""; for (int i = 0; i &amp;lt; victoryToDate.length; ++i) { if (i &amp;gt; 0) victoryString += "\t"; victoryString += victoryToDate[i]; } return victoryString; } }[/accordion-item]

[/accordion]

## Are all the wins born equals?

Since each winning combination depends on buying/constructing different elements in the game, and in Catan you buy stuff with resource cards, the total resource cards needed to win for each particular victory combination will differ.

We can then calculate how much resources are needed for each victory path… And determine which one is the least costly to achieve!

If we take the very optimistic approach that everything will go perfectly and that you will only receive the cards you need, at the right time, we can determine the minimum cost of achieving each victory.

This is for sure a big assumption, after all, the resource cards are distributed based on the result of dice rolls. And if you can exchange resources with other players, often you’ll have to exchange more than one card to get the one you want.

But since this remains true, not matter which victory path you take, the minimum cost should be a good comparison point for the real-life cost of each victory. At least it is a very good baseline for comparing victories!

## What is the cost of a victory?

The cost of the different elements in the game is the following

- Buying a new settlement: 4 resource cards
- Upgrading a settlement: 5 resource cards
- Constructing a road segment: 2 resource cards
- Buying a development card (drawn from a shuffled deck): 3 resource cards

At the start of the game, each player is given, at no cost, 2 settlements, each with one attached road segment. Those two settlements do not need to be linked to each other by road, but every other settlement built by a player will need to be attached to one of his existing road networks.

There will be at most 2 groups of settlements with their distinct road network for each player (And one network if the player links them together with roads during the game).

To calculate the cost of the victory, I assumed a perfectly optimized play:

- The
**longest road**will make use of the 2 given road segments at the start (if it makes sense) - The
**longest road**and**biggest army**are achieved with the minimum requirements (**5 roads,****3 knights**) - Cities and settlement are built at the minimum distance(2) from each other (reducing the road segments needed)
- The road network built by the player is optimized for the victory scenario.
- The resource cards received by the player are the one needed.
**The cards drawn from the development deck are the one needed for the victory***

*I will come back to this bit further

### Road Optimization?

Road optimization is important because it minimizes the quantity of road you need to build to achieve your victory.

For example, you can build 4 settlements (or cities) using a minimum of 4 road segments.

For fetching the Longest Road Victory points, by requirement, you’ll need a minimum of 5 road segments

But if you want the longest road victory points AND 4 settlements, you’ll need at least 6 road segments. No way around it!

**OR**

## Update, Road optimization

*Road optimization is indeed very important!*

*I had actually missed part of the possible optimizations for roads, and some careful readers pointed that to me. There was also another mistake adding some resources that I corrected at the same time*

*Thanks for all the nice comments I received, I was able to correct and update my mistakes.*

Following those good comments, I decided to add here the minimum amount of road needed for your settlements, depending on the number of building you have (those can be cities or settlement).

- The first column show an optimal road network for a given number of settlements
- The second shows the same thing, but with the additional constraint that you need a path of at least 5 continuous road segment to get the longest road Victory points

**So what is the cheapest victory?**

This cheapest win can be achieved with the following components:

- Two settlement (given at the start)
- Having the longest road (with 5 road segment)
- Having the Biggest Army special card, obtained by playing 3 knight cards
- Having four of the Victory points development cards

And it turns out that one can win while having received **only 23 resource cards!**

Actually to obtain all those, **a player would have to spend 27 resource cards**, but since, a player is allowed to “steal” one resource card from another player each time he plays a knight card, and since building the biggest army involve playing at least 3 development cards, we can lower the actual cost by 3 resource cards!

Additionally, if a lucky player was to buy a development card and it happens to be the **R****oad Builder card**, it would give him 2 road segments, a reduction of one resource card on the price of having to build them directly! (Some solutions even allow a really lucky player to use two of those cards).

So you have a cost of **9 resources** for the 3 knight cards (costing 3 resources each), **12 resources** for the 4 victory point cards (costing 3 resources each), **6 resources** to build the needed additional 3 road segments, with a **discount of 1** for the Road Development card, and a **discount of 3** for playing the knight cards.

**9 + 12 +6 – 3 -1 = 23 resources**

**And the most expensive victory?**

This most expensive win can be achieved with the following components:

- Biggest Army (Obtained by buying 3 development cards)
- 2 Cities (Upgraded 2 settlements)
- 5 settlements (With the associated road network)

So the cost would be **9 resources** card for the biggest army, **10 for the upgraded cities**, and **20 for the settlements** plus an additional **12 for the roads**.

**Minus the 3 biggest army stolen cards**, **minus two** for the lucky drawing of the Road Builder development card.

**9+10+20+12 -3 -2 = 46**

There is a list of un-optimal thing with this win.

First, it is an **11 point** win, so not the most efficient.

It implies that the player received the “biggest army” at the end, a 2 victory point item, which pushed him from 9 to 11 points.

If the player had got it earlier in the game, he would have reached 10 points by upgrading a settlement to a city, or building a new settlement!

It would then have ended up at 10 points with **4 settlements and 2 cities**, and this would be considered a different victory. (By the way, this victory is listed and cost only 38 resource cards to achieve!)

**In short, he had to buy one additional thing to win.**

Not only that, here we see that the player has 7 buildings, and do not have the longest road achievement points. So either someone would have beat the player to the punch for the Longest Road, or the player is inefficient in his road efforts.

One of such inefficiently built road network for 7 building is the following:

But let’s not get judgmental… Sometimes a game evolves in strange ways, and a win is a win!

*Second update*

Since I want this to be an *exhaustive* list of all the ways to win at Catan, I am thankful to a reader to have pointed me to an edge case that allows you to score **12 points** in a game of Catan!!

To do that, however, you need specific pre-conditions:

- You need an adversary having the longest road, with a vulnerable network
- You need to be at 9 victory points yourself
- You need to have the second longest road in the game with your road network
- You need to be able to build a settlement at the right point to break your opponent road network

In Catan, your longest continuous road cannot have an opponent settlement along it. And since the island is built with hexagonal tiles, the road’s intersection can connect 3 road segment together.

So if your opponent is not careful, and build a network vulnerable to such an attack, you could “break” his continuous road, fetch the victory points from him (if you have the longest continuous road. And since you did that by building a settlement, you end up scoring **3 victory points** with one action. And from this, you can go from 9 to 12! If you do this from 7, or 8 previously won victory points, you still win, but with 10 or 11 victory points, and those victories were already included in the list.

**Example of the red player breaking the blue player road network**

This is quite an edge case, and does not affect the rest of the analysis (with the exception of the now costliest victory being 47 instead of 46) but it will happen, so I decided to include those as well in the list. They are indicated by a * in the victory Cost column.

**And this brings the total potential victory to 143 !!!**

***Update: Actually 142, since one condition in the list has shown to be impossible, namely the 12 points victory with 1 city and 1 settlement, I will not rebuild the tables, but be warned!*

To see all the victory costs for all the possible victories, simply click to open the drop-box below:

[accordion tag=h3 clicktoclose=”true” style=”accordion-container” style=”accordion-style1″]

[accordion-item title=”**+** Click to see all the possibles victories” id=102-way-to-win-at-catan-all-simple-list state=closed style=”accordion-style1″]

Here are all the 143 ways to wins at Catan.

- Each row represents a unique way to win.
- Each column indicates the composition of the win.
- The last column shows the minimum amount of cards one have to spend to achieve this win.
- The
*****indicate 12 points victory

*Note: you can sort the column by clicking on the column header!*

Longest Road | Biggest Army | Cities | Settlements | Victory Pt Cards | Victory Cost |
---|---|---|---|---|---|

yes | no | 2 | 5 | 0 | 42 |

yes | no | 2 | 5 | 1 | 45 * |

no | yes | 2 | 0 | 4 | 28 |

no | no | 2 | 4 | 2 | 38 |

no | yes | 2 | 0 | 5 | 31 |

yes | yes | 2 | 0 | 3 | 30 |

yes | yes | 2 | 0 | 2 | 27 |

no | no | 2 | 5 | 1 | 43 |

no | yes | 2 | 5 | 0 | 46 |

no | yes | 1 | 2 | 5 | 32 |

no | yes | 1 | 2 | 4 | 29 |

no | yes | 1 | 1 | 5 | 26 |

yes | yes | 1 | 5 | 1 | 40 * |

yes | yes | 1 | 5 | 0 | 37 |

no | yes | 3 | 0 | 3 | 36 |

no | yes | 3 | 0 | 2 | 33 |

no | no | 2 | 3 | 3 | 36 |

no | yes | 0 | 4 | 4 | 29 |

no | yes | 0 | 4 | 5 | 32 |

no | yes | 0 | 3 | 5 | 27 |

no | yes | 1 | 5 | 1 | 36 |

no | yes | 1 | 5 | 2 | 39 |

no | no | 2 | 2 | 4 | 33 |

no | yes | 4 | 1 | 0 | 43 |

no | yes | 1 | 3 | 4 | 34 |

no | yes | 1 | 3 | 3 | 31 |

no | yes | 3 | 1 | 1 | 35 |

no | no | 3 | 1 | 3 | 35 |

no | yes | 3 | 1 | 2 | 38 |

yes | no | 4 | 2 | 0 | 46 * |

no | yes | 3 | 2 | 0 | 38 |

no | no | 3 | 0 | 4 | 33 |

no | yes | 3 | 2 | 1 | 41 |

no | no | 2 | 1 | 5 | 31 |

no | yes | 1 | 4 | 3 | 37 |

no | yes | 1 | 4 | 2 | 34 |

no | yes | 0 | 5 | 3 | 32 |

yes | no | 4 | 0 | 0 | 34 |

yes | yes | 2 | 2 | 1 | 33 |

yes | yes | 2 | 2 | 0 | 30 |

no | yes | 0 | 5 | 4 | 35 |

yes | no | 4 | 0 | 1 | 37 |

yes | yes | 2 | 2 | 2 | 36 * |

no | no | 3 | 4 | 0 | 45 |

yes | no | 3 | 4 | 0 | 47 * |

no | no | 3 | 2 | 2 | 38 |

yes | yes | 0 | 5 | 3 | 35 * |

yes | yes | 0 | 5 | 2 | 32 |

yes | yes | 0 | 5 | 1 | 29 |

no | no | 3 | 3 | 1 | 40 |

yes | yes | 2 | 4 | 0 | 42 * |

yes | yes | 1 | 3 | 1 | 28 |

yes | no | 2 | 3 | 1 | 33 |

no | no | 1 | 3 | 5 | 31 |

yes | yes | 1 | 3 | 3 | 34 * |

yes | no | 2 | 3 | 3 | 39 * |

yes | yes | 1 | 3 | 2 | 31 |

yes | no | 2 | 3 | 2 | 36 |

yes | no | 2 | 2 | 4 | 36 * |

yes | no | 2 | 2 | 3 | 33 |

yes | no | 2 | 2 | 2 | 30 |

no | no | 0 | 5 | 5 | 32 |

yes | no | 2 | 0 | 5 | 30 |

yes | no | 3 | 2 | 2 | 41 * |

yes | no | 3 | 2 | 1 | 38 |

yes | no | 3 | 2 | 0 | 35 |

no | no | 1 | 4 | 4 | 34 |

yes | no | 2 | 0 | 4 | 27 |

yes | yes | 3 | 1 | 0 | 35 |

yes | yes | 3 | 1 | 1 | 38 * |

no | no | 1 | 5 | 3 | 36 |

yes | no | 2 | 1 | 3 | 28 |

yes | no | 2 | 1 | 4 | 31 |

yes | no | 2 | 1 | 5 | 34 * |

yes | no | 3 | 0 | 2 | 30 |

yes | no | 3 | 0 | 3 | 33 |

yes | no | 0 | 4 | 5 | 29 |

yes | no | 0 | 4 | 4 | 26 |

yes | no | 3 | 1 | 3 | 38 * |

yes | no | 0 | 5 | 4 | 32 |

yes | no | 0 | 5 | 5 | 35 * |

yes | no | 0 | 5 | 3 | 29 |

yes | no | 3 | 1 | 1 | 32 |

yes | no | 3 | 1 | 2 | 35 |

yes | yes | 1 | 1 | 4 | 28 |

yes | yes | 1 | 1 | 5 | 31 * |

yes | yes | 1 | 1 | 3 | 25 |

yes | yes | 1 | 2 | 2 | 26 |

yes | no | 2 | 4 | 0 | 36 |

yes | yes | 1 | 4 | 1 | 34 |

yes | yes | 1 | 4 | 2 | 37 * |

yes | yes | 1 | 4 | 0 | 31 |

yes | yes | 1 | 2 | 3 | 29 |

yes | no | 2 | 4 | 1 | 39 |

yes | yes | 1 | 2 | 4 | 32 * |

yes | no | 2 | 4 | 2 | 42 * |

yes | no | 0 | 3 | 5 | 24 |

yes | yes | 0 | 3 | 3 | 24 |

yes | yes | 0 | 3 | 4 | 27 |

yes | no | 1 | 4 | 4 | 37 * |

yes | yes | 0 | 3 | 5 | 30 * |

yes | no | 1 | 4 | 3 | 34 |

no | no | 4 | 1 | 1 | 40 |

yes | no | 1 | 4 | 2 | 31 |

yes | yes | 0 | 4 | 2 | 26 |

yes | yes | 0 | 4 | 3 | 29 |

yes | no | 1 | 5 | 3 | 40 * |

yes | yes | 0 | 4 | 4 | 32 * |

yes | no | 1 | 5 | 2 | 37 |

no | no | 4 | 0 | 2 | 37 |

yes | no | 1 | 5 | 1 | 34 |

yes | yes | 0 | 2 | 5 | 26 |

yes | no | 1 | 3 | 5 | 34 * |

yes | yes | 0 | 2 | 4 | 23 |

no | no | 4 | 2 | 0 | 42 |

yes | no | 1 | 3 | 3 | 28 |

yes | no | 1 | 3 | 4 | 31 |

yes | no | 4 | 1 | 0 | 40 |

yes | no | 4 | 1 | 1 | 43 * |

yes | no | 1 | 2 | 4 | 26 |

yes | no | 1 | 2 | 5 | 29 |

yes | yes | 2 | 3 | 1 | 39 * |

no | yes | 3 | 3 | 0 | 43 |

yes | yes | 2 | 3 | 0 | 36 |

no | yes | 4 | 0 | 0 | 37 |

yes | no | 3 | 3 | 0 | 41 |

no | yes | 4 | 0 | 1 | 40 |

yes | no | 3 | 3 | 1 | 44 * |

yes | no | 1 | 1 | 5 | 25 |

no | yes | 2 | 1 | 3 | 31 |

no | yes | 2 | 1 | 4 | 34 |

yes | yes | 3 | 2 | 0 | 41 * |

no | yes | 2 | 2 | 3 | 36 |

no | yes | 2 | 2 | 2 | 33 |

no | yes | 2 | 4 | 1 | 41 |

no | yes | 2 | 4 | 0 | 38 |

yes | yes | 2 | 1 | 3 | 34 * |

no | yes | 2 | 3 | 1 | 36 |

no | yes | 2 | 3 | 2 | 39 |

yes | yes | 2 | 1 | 1 | 28 |

yes | yes | 2 | 1 | 2 | 31 |

yes | yes | 3 | 0 | 1 | 33 |

yes | yes | 3 | 0 | 0 | 30 |

[/accordion-item]

[/accordion]

## Revisiting the Breakdown Graph

At the beginning of this article, I have shown the breakdown cost of all victories. So now that you have all the details, here it is again:

I made a few assumptions here, mainly, I decided that the Longest Road would have a minimum cost of 4 when involved in a victory. Otherwise, it’s kind of arbitrary to distribute its cost between the settlements and the longest road component (when they are both involved). Additionally, we would not be able to see the longest road in the breakdown graph when there is more than 4 settlements or cities in a victory, since no additional road segment would be needed.

Second, all the settlements cost are shown in the settlement part, cities only show the upgrade cost of settlements. This is an arbitrary choice as well.

That being said, we can see how victory points are mainly used in low-cost victories, and the costlier victories all involve building a lot of road and settlements… Without using the longest road victory points.

This is not surprising since there is a synergy between some components to attain the victory. The longest road benefits from building settlements that need a road anyway… So any victory that failed to use this synergy is bound to end up costing more than those who do!

The same could be said about the biggest army and victory points cards, but our current approach fails to show this… We will need a different approach!

## What about the resources cards involved in a victory?

While I simplified the minimum cost by considering all resources cards being equal, of course, they are not! Each component you buy demands a specific list of resources, so each 142 victory demands its own blend of resources!

While I intend to come back to this topic in a future blog post, examining the resource type composition of the cheapest victory shows us why this question is also important.

Consider this: the **29 resource cards** that will have to be played in our cheapest victory (including the 3 cards stolen from other players) are the following:

- 10 Grain
- 8 Wool
- 11 Ore
- (No Lumber, No Bricks needed)

The player has to buy 8 development cards (at the cost of **1 Wool**, **1 Grain** and **1 Ore** each), and upgrade one city (costing **2 Grains** and **3 Ore**).

This is interesting because we clearly see that depending on your strategy, you can almost completely ignore some types of resources and concentrate on the one you need!

In a real game, the thinking would probably be the other way around: Depending on the initial board and the choices available to you, you would probably select your strategy according to the resources more readily available to you. Some resources are also a bit rarer than others by design, this can also influence your game strategy!

But we can play with the resources requirement in all kinds of ways… So I’ll leave that for another time! (Sorry for the tease).

## But is the cheapest victory the best strategy?

The astute reader will see a damning flaw in the cheapest victory approach: It involves drawing 8 specific development cards from a shuffled deck of 25… Hoping to only receive the cards you wish for!

**It is literally wishful thinking!!!**

So to evaluate the real-life cost of a victory, we have to consider the **Expected Cost** of the victory. This means that we need to evaluate, given the probabilities involved, on average, what will be the real cost of each victory…

And this is exactly what I’ll do. And I will explain all about it…

**Next time** in **The 143 ways to win at Catan – Part II**

**In the meantime, have fun playing games!**

*Hope you did find this first breakdown of victories interesting. *

*Let me know if I missed something, or if you would like more details, explanation about some elements!*

This looks fairly thorough, but I did not see a restriction on maximum number of cities or settlements in your code.

I am a python and R guy, so I may have just missed it, but looking at your results, everything seems to be good just wondering where those restrictions got executed.

The limit for settlements and cities is set in the initial conditions.

When we call the function first, we set the following parameters.

int[] victoryPointTypeUsed = new int[]{0, 0, 0, 0, 0};

int[] victoryPointPossible = new int[]{1, 1, 4, 5, 5};

The 4 is for the cities, and the following 5 for the settlements.

In the code I then only check for minimal amount of city+settlement.

Otherwise, the quantity of both is limited by the victory point total that cannot exceed 10-11.

Hope that answer your question!

Thanks for reading!

Wouldn’t this be less cards

Upgrade to city: 5

Build 1 road: 2

Dev Card road building: 3

3 dev cards largest army: 9

3 dev cards Victory Points: 9

28 total cards, 3 are free from soldiers.

LR 2

LA 2

Settlement 1

City 2

Victory 3

Total 10

I took the liberty of implementing something similar in F#. The code is here: https://gist.github.com/zabracks/f8d62223f1fccc237f12677aecc5f05c

One thing that I noticed is that I’m getting 114 possible solutions instead of 102. One case that mine picks up that I don’t see in your set is (longest road, largest army, 1 city, 4 settlements, 1 card VP == 11 VP). I’m trying to figure out why it wouldn’t appear, but I must be missing something.

It’s kind of embarassing!

In my code there was some 10-points solution hiding valid 11-points solution.

A quick fix gave me 114 solutions as well. I’ll double check and try to update my data in the coming days.

But thank you! The point of this is to learn and have fun.

I’m learning! Hope others are learning too!

I took the time to check your code closer, first time I’m looking at F#.

If I understand correctly, you iterate through all possible count for each elements. So you don’t run in the same problem as I did in my recursive exploration.

For the benefit of others that could ask why I did it this way. I did implement it recursively because in cases of large numbers of items, it allows to use dynamic programming and reduce greatly the number of state to explore.

You can store the results of sub-problems and re-use the stored answers instead of recalculating many times the same partial solutions. Which can speed up tremendously the calculation!

I’m impressed that you took time to re-implement it! Neat implementation too!

Your knapsack analysis missed the 12 point possibilities, namely where the settlement cuts the road and gives you the two points for the longest road AND the point for the settlement.

I actually learned about road cutting possibilities only very recently! It did not occurs to me that you could score 12 points that way.

This is winning strategy difficult to plan since it depends on your adversary developing a vulnerable road network, but since this wants to be an exhaustive list with all the winning possibilities, you are perfectly right, those should be included as well!

This will be easy to add to the list, and I’ll add them to my analysis.

Thanks for the comment!

looking forward to part 2 of this! 🙂

have you considered doing similar analysis with extensions and expansions?

I was thinking at looking at the expansion after having a look at the base game.

Since I should be rather easy to adapt what I did, depending how they change the base rules.

But I want to analyze other games too, so I’ll probably come around to do it, but I do not know when for the moment!

I also must admit I’m not too familiar with Catan expansions, never having played any of them.

Which one do you think would be interesting to do first?

I would suggest starting with 5-6 player extension of the base game.

I have been playing Seafarers expansion since it is supposed to be the most popular one. It adds a lot of different scenarios which requires significant change in strategy.

cities and knights or seafarers

Interesting article – are you planning on looking at the affect that extra settlements / upgrading to cities has on gaining resources?

Does a strategy that includes gaining lots of settlements while being more costly end up better due to resource collection compared to the cheaper routes to victory that rely on development cards and road building?

Thanks!

Yes, the third part: The fastest Way to win. Will all be about how building cities and settlements change at what speed you receive resources. And how many turns it takes to win, depending on this and individual victory costs.

I’m currently finishing the second part on the expected cost of each victory, based on the probability of drawing the correct development cards you need for each victory. Because this has also a serious impact on real victory cost.

Hopefully I post that before the end of the week!

Thanks for reading!

Cool, I’ve book marked and look forward to the further instalments.

Keep up the good work man. Very interesting read…

Thanks! I’ll try to release the second part very soon!

Great article!

Can’t you drastically reduce the minimum amount of cards by getting (if you’re extremely lucky) the two Monopoly Cards? and using them for getting 2/3 of the resources needed for the other required Development Cards (assuming that, lucky again, your opponents the amount of resources needed)

Thanks!

For the monopoly card question: Yes, monopoly card can reduce greatly a victory cost, but this is victory independent. All victories can benefit from it, so it does not change the ranking in the case on the minimum achievable cost.

In practice, considering the monopoly card only make sense for victories where you are buying development cards for other purpose (since you only have 8% of chance of drawing one).

In the next part I attribute a cost reduction effect to it, but a limited one.

Maybe I could try to make a good statistical analysis of the expected return of a monopoly card if played optimally! (But this will be for another article!)

Great articles man…

One question though…

Aren’t those 12VP victories already included in the “win by making a settlement for the 10th VP” scenario?

If you already have 9 VP, building a settlement will give you a win regardless of the placement of that settlement, if you break somebody’s road and claim 2 additional VP, it would not matter, those 2 points do not influence the outcome of the game?

Thanks!

The 12 point victory analysis is a bit like hair splitting since it’s rather rare. But while the longest road here is redundant, scoring the longest road impose some restrictions on the road network (see the optimal road image in the post). So from this point of view it makes sense to consider it as different for the minimum cost point of view than a 10 point victory without the longest road.

I mostly included those victory for the sake of completeness, since they are differents, but I would be curious to know how often a game ends up that way!

could you post a table where not only can we can sort by one column but we can also rank sorting methods? example, I want to sort by victory points, look at all the rows where the number of victory points is 1, then have those sorted by longest road, look at all the ones where longest road == no, then sort those by minimum number of resources, etc…

Interesting article. Although I do hope that in the future you realise that women play games too. Might need to cut back on the gendered words with regards to the player.

Hi! I’ll try to keep an eye on that in future articles. English is a second language for me, so hopefully you can excuse the occasional errors in my articles!

Great article!

I was also interested in the number of ways to win a Catan game, so I am pleased to find someone who dedicated time to find it out.

Your research seems quite thorough, but I think the correct number of ways to win is 142, instead of 143.

In your list,

[Longest Road]Yes [Biggest Army]Yes [Cities]1 [Settlements]1 [Victory Pt Cards]5 [Victory Cost]31

with 12 points victory seems impossible.

The reason is that the game starts with 2 settlements, and 12 points win condition relies on building 1 settlement to break someone else’s longest road, which makes the total number of settlements + cities larger than 3.

I solved inequalities to came up with the answer, and it was 142.

Though I can’t quite write down everything, the key is that when

Number of settlement =S

Number of cities =C

then

S+C≥2 for 10 or 11 points win conditions

S+C≥3 AND S≥1 for 12 points win conditions.

The latter inequalities exclude the impossible one.

It’s a very rare case, but I just wanted to point it out for the completeness of your article.

Again, great article.

You are right! It is a good catch. In this special case, the road needs to be broken by a new settlement, which cannot be achieved with only the 2 initial settlement locations on the board.

I will try to add a note for the sake of completeness, (but I will not regenerate all tables).

Thanks for finding this. Even if I try to get it right, I’m glad that people get interested enough to catch subtle errors in my analysis!

Very cool article. I love this kind of analysis.

I think it is a mistake to overlook the true cost of cities. To get a city, the cost is really settlement + city (9 cards), not just city (5 cards). So any solution that requires a city as a victory condition, is short 4 cards in reality.

The very first condition in the graph looks like it doesn’t use villages or cities, but I didn’t see that scenario in the results table. I was going to point out that without any way to get resource, it would be impossible to win. I am sure the constraint is there, but you of course need a min of 2 settlements to have any victory.

Hi! Thanks for your comment.

While I cannot guarantee there is no error left in my analysis:

Rest assured, in all the solutions, the full cost of settlement needed prior to the city upgrade is considered!

(Except solution with no settlements, the first 2 cities only need to be upgraded from the initial 2 free settlements!)

Also, the two first settlement have no cost associated to them, and the initial graph is a representation of the cost of the victory, so some solutions have no settlement cost associated to them (4 victory points cards, longest road, biggest army, plus the 2 free settlement = 10 victory points, without building a settlement!)

But thanks for writing, Without readers comment this article would not be as complete as it is at the moment 🙂 And, as I said, there is always the possibility of some error left!