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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.