# How to calculate the optimal placements for settlements in Catan without an ML algorithm?

Is it possible to calculate the best possible placements for settlements in Catan without using an ML algorithm?

While it is trivial to simply add up the numbers surrounding the settlement (highest point location), I'm looking to build a deeper analysis of the settlement locations. For example, if the highest point location is around a sheep-sheep-sheep, it might be better to go to a lower point location for better resource access. It could also weight for complementary resources, blocking other players from resources, and being closer to ports.

It seems feasible to program arithmetically, yet some friends said this is an ML problem. If it is ML, how would one go about training, as the gameboard changes every game?

• Could you be a little clearer on your definition of "best"? There are a few choices, but ones suitable for analysis usually focus on a precisely-defined measure. If your measure is "most likely to win the game ultimately" then that is a hard problem and there are lots of dependencies - critical is how the agent you are deciding for and the other players intend to play the game. Often an assumption of optimal play throughout is used, but is hard to define for games with greater than 2 players. – Neil Slater Oct 23 '19 at 8:30
• The "The Settlers of Catan" game can be formalized in a simulation, for example with SmartSettlers. The next step is to inject domain knowledge in an abstract game. The advantage is, that this helps to reduce the game tree and explores possible macro actions. Then, a Monte-Carlo Tree Search gets started to find the optimal policy. – Manuel Rodriguez Oct 23 '19 at 9:10

Catan is actually a much more complicated game than the simple rules would suggest, and an exact solution is probably beyond the scope of current AI techniques.

Monte Carlo Tree Search or Expectiminimax techniques seem like they could help, but are intended for games of perfect information. Catan is not a game of perfect information (the development cards are hidden), and also has a phase that occurs without a regular turn sequence (trading).

To solve Catan properly, I think you're going to need both algorithms for solving POMDPs (like CFR+), and algorithms for negotiation (like Kraus' Diplomat). I'm not certain that these have been combined before in formal analysis, so this might actually be a good PhD thesis for someone.

That said, you can probably get a good player using self-play techniques, because Catan has randomization, and a relatively small set of moves, like Backgammon. These may or may not offer simple rules about how-best to play the game. Your friends are right to think about this as, at root, an ML problem.

• Is it not inaccurate to say that the game has imperfect information? You can keep track of what development cards the other players have, by paying attention to their yields and expenses, could you not? – Krrrl Oct 27 '19 at 21:16
• @Krrrl You can keep track of how many cards they have, but the cards are drawn randomly from a deck, and then concealed in players' hands. You can track how many cards of each kind have been played, and so you can guess at what a card in someone's hand might be, based on that and on what they might be trying to buy or not. However, since you can't know for sure until the card is played, this is a game of imperfect information (that's the definition). – John Doucette Oct 27 '19 at 22:28
• I know the definition, but I am still arguing that since both die roll and settlement location is known at all times, you can infer what cards are in the other players hands at all time. Example: If exactly one turn has passed - where the value rolled was 6 - then you know that players with settlements on a "6" hex has received development cards for that area, lets say brick. If none of those players proceed to build something that requires brick that turn, you now know that their hand contains 1 brick, and so on. Could it be that we are talking about different versions of Catan? – Krrrl Oct 27 '19 at 23:26
• @Krrrl It sounds like you have confused resource cards with development cards. Resource cards are awarded when dice are rolled. Development cards are purchased, and drawn face down from a shuffled deck. They are present in the base game, and all expansions. – John Doucette Oct 27 '19 at 23:49
• Ah, indeed I have! I also completely forgot about the variety of development cards(non-victory points ones). I concur with your statement about imperfect information, my apologies! – Krrrl Oct 28 '19 at 0:24

Historically, the non-ML approach would be an expert system. This is typically a rules-based decision system, falling under the umbrella of symbolic AI.

These systems can have strong utility in limited contexts, but are generally "brittle" in that parameters not previously defined or accounted will produce no-compute or weak utility. Because the rules of a game are fully definable, the main concern is utility, which relates to the degree to which the game has been solved.

Informing a heuristic system in this case requires analysis of the game in in the sense of game theory and combinatorial game theory, since Catan involves both imperfect information and combinatorial elements. The complexity is high indeed, not only per imperfect information, branching factors, stochasticity, players > 2, but, as you note, the game board itself has a very high number of potential configurations, so solving the game is presumed to be extremely difficult to impossible. (Possibly NEXPTIME if finite and undecidable otherwise.)

The paper Game strategies for The Settlers of Catan suggests that the game tree for Catan is not surveyable b/c the options for trade negotiation in natural language aren't bounded:

One response to this is to develop a symbolic model consisting of heuristic strategies for playing the game. Developing such models potentially has two advantages. First, a symbolic model can in principle lead to an interpretable model of human expert play ... Second, a symbolic model can provide a prior distribution over which next move is likely to be optimal...

The paper mentions this second part to relation to machine learning, where "the posterior distribution over optimal actions acquired through training improves on the baseline prior distribution."

Especially where the game is unsolved and intractable, machine learning has demonstrated strong utility for an increasing number of games, so it is unlikely not to be an optimal component for truly strong play. However, such a system can be a combination of ML and domain specific knowledge, such as in informed search.

The Optimizing UCT for Settlers of Catan goes into this in detail, and also provides reference to prior work.

If your primary requirement is strong utility, some form of machine learning is likely optimal. But it can be fun to attempt to solve games and cobble together sets of heuristics.

• Nice answer. I'm not sure about the claim of NEXPTIME though. I can easily see how it is in NP, but apart from the Natural Language component, it's not clear to me that we can be sure about the hardness of the game. – John Doucette Oct 26 '19 at 1:23
• @JohnDoucette Yeah, I was just making a guess based on Constraint Logic for an imperfect information team game (here "team" b/c player >2, which can result in coalitions.) I suspect proving it would be daunting indeed, and it doesn't even show up on this wiki chart of hardness of popular games! – DukeZhou Oct 26 '19 at 18:52

From the way you have phrased your question one can derive a couple of strong assumptions which simplify the problem tremendously and make it feasable:

1. We do not look for an agent being able to play the game but only an evaluation of settlement options (no other agents to be considered)
2. The evaluation of settlement options is static (i.e. does not change over time) and is independent of other settlements

From that two simple ideas come to my mind:

1. the ML approach Look at historical game data and see which settlement options led to a win. So basically look at tuples of (X,y) with X being something like (W8, C2, O6) meaning that the settlement give access to wood with an 8, clay with a 2 and ore with a 6. And y indicating a win or loss. To make it a bit dynamic you could differentiate between initial settlements (being placed at the beginning) and the ones during the game. So for each of these two categories you would derive basically a score for the possible settlements.

If you can compute all the possible combinations you will not even need ML since you can simply run the math once and then look it up. Might be doable in this case as the assumptions mentioned above simplify the problem a lot (compared to fully "solving" the game). Thinking through the possible combinations for a given settlement location (selecting 3 fields with A possible resources and B possible numbers) will quickly give you an idea about that.

2. The classy symbolic approach What comes to my mind right away is linear programming as it offers a convenient way to model the strategic aspects you have mentioned. You could develop a target function to maximize using scores for different resources and numbers (e.g. you could give clay higher importance than wool). Besides that constraints can capture additional aspects of game strategies like "always make sure to have access to clay" or "do not settle where the 3 resources are the same" etc.

My very first idea to model this is using decision variables like X_(i,j) with X being 0 or 1, i representing the resources out of {clay, wood, ..., desert} (side note: do not forget the water and different ports here) and j modelling the numbers out of {2,...12}. The constraints would need to model the fact that you need to select 3 of those X_(i,j) for every settlement.

If you want to calculate this for a given game you would need to feed the model the possible settlement options based on the layout of that specific game. Then run the optimization and it gives you the best settlement option (i.e. the 3 feasable X_(i,j) maximizing your goal function).

Qua definition you need to bring in game knowledge for this approach. And probably talking to someone who is really good at the game would help to understand what matters.