*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?

***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:

### + **For those unfamiliar with the game**

## 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:

### + **The knapsack problem**

### + **I want to see some code**

## 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 !!!**

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

**+** Click to see all the possibles victories

## 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 114 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.

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!)