Settlers of Catan (SoC) is a German board game from the mid 90’s that found mainstream success in America in the late–00’s. To summarize the game: the board consists of 19 hexagonal resources tiles and these tiles get numbered markers (2–12). There are five resources, lumber, sheep, ore, brick, and wheat. These are used to build towns, roads, cities; or earn “development cards” with special abilities or points. The gameplay consists of placing towns and roads on the vertices and edges of the tiles. Dice are rolled each turn and any player who has a town on a vertex adjacent to a numbered marker collects the resource of that marker. Players earn points by expanding their settlements, the first player to ten points wins.
An element of the game that greatly affects how it plays is the resource tile layout and the distribution of the numbered markers on the resources. By the mid to late game it becomes evident that some players have some significant leverage on game-winning resources and others are severely constrained by the lack of a resource. This likely comes through their initial town placement and subsequent expansions.
Manually balancing the board is inherently difficult as you have to keep in mind resource proximity through tile layout and resource scarcity through marker placement. Players who recognize an imbalance in the board are likely to win or handicap others from winning by blocking others from building on important vertices. If only there was a way to make a board with evenly distributed markers and where no two of the same resources are adjacent and the markers were evenly distributed. Roads are a significant source of points in the game, with two points going to the player with the longest road greater than five segments. It would be nice if roads, which cost one lumber and one brick, were a little harder to build. With these constraints in mind let’s look at a way to solve this.
Constraint programming
I was recently introduced to constraint modeling and constraint programming (CP) through one of my graduate courses. In short, CP is the closest thing to magic in the realm of computer science that I know of. You can use it in a low-level language like C++ (GeCode and Chuffed) or you can use it on a higher abstraction where the syntax is concise and neat. One such abstracted language is called MiniZinc.
MiniZinc is a declarative constraint programming language which uses lower level constraint solvers through a common abstracted layer called FlatZinc. Once you grasp the syntax, complicated problems can be solved in mere lines of code. A simple example that I think demonstrates the power of MiniZinc is the magic square problem.
The magic square is a puzzle where with numbers 1 through 9 fill a 3 by 3 grid so that the sums of all rows, columns, and 3-length diagonals are equal. In MiniZinc we declare such a grid as an array of decision variables:
array [1..9] of var 1..9: sq;where square is the array, for simplicity it is 1-dimensional. The contents of sq will be modified in the search for a valid puzzle solution. Now the constraints which describe the puzzle:
constraint alldifferent(s);This lets the solver know that every number in sq must be distinct. Otherwise solutions like ([1,1,1,1,1,1,1,1,1] would be generated. Next constraining the row and column sums: (arrays in MiniZinc are 1-indexed):
% rows
constraint sum(sq[1..3]) = sum(sq[4..6]);
constraint sum(sq[4..6]) = sum(sq[7..9]);
% columns
constraint sq[1]+sq[4]+sq[7] = sq[2]+sq[5]+sq[8];
constraint sq[2]+sq[5]+sq[8] = sq[3]+sq[6]+sq[9];
% diagonals
constraint sq[1]+sq[5]+sq[9] = sq[3] + sq[5] + sq[7];
Finally, MiniZinc needs to know what the objective is, for other problems we can maximize or minimize some value. Here we just want any solution:
solve satisfy;and that’s it! Running the program gives this result:
Compiling magic-square.mzn
Running magic-square.mzn
sq = array1d(1..9, [8, 1, 6, 3, 5, 7, 4, 9, 2]);
----------
Finished in 169msecJust to make it more readable:
output[ "\(sq[1..3])\n" ];
output[ "\(sq[4..6])\n" ];
output[ "\(sq[7..9])\n" ];and rerunning it:
...
[8, 1, 6]
[3, 5, 7]
[4, 9, 2]
----------
Finished in 163msecIf you’re following along in the MiniZinc IDE and this is your first time using MiniZinc take a moment to reflect on all the time you may have spent solving this by hand and feel the wind on your face as you stand on the shoulders of giants. But wait, there’s more!
There are some improvements to be made. Firstly, this square can be rotated and reflected to create seven other solutions. This is called symmetry and it is a large component of constraint problem/programming research. In the configuration editor in the MiniZinc IDE change output settings: check ‘Output statistics for solving’ and under ‘User-defined behavior’ check ‘Print intermediate solutions’. Also change ‘Stop after this many solutions’ to 0. Rerun the model.
%%%mzn-stat initTime=0.000778
%%%mzn-stat solveTime=0.007776
%%%mzn-stat solutions=8
%%%mzn-stat variables=9
%%%mzn-stat propagators=6
%%%mzn-stat propagations=19399
%%%mzn-stat nodes=2659
%%%mzn-stat failures=1322
%%%mzn-stat restarts=0
%%%mzn-stat peakDepth=14
%%%mzn-stat-endThis is more information that we may want, the key line is 8 solutions. To elaborate on the rest of the output nodes reflect the count of nodes in the search tree and peakDepth refers to the depth of the tree. propagators and propagations refers to how the solver is iterating through this problem. Propagation is the mechanism by which the solution space is reduced each step and is another large part of CP research. Redundant solutions can be cut down by adding more constraints. By removing redundant solutions we also remove redundant non-solutions and reduce the overall search space. Let’s make it so that the number in the top left corner is 9.
constraint sq[1] = 2; ... [2, 9, 4] [7, 5, 3] [6, 1, 8] ---------- [2, 7, 6] [9, 5, 1] [4, 3, 8] ---------- %%%mzn-stat solutions=2
These final two solutions are diagonal reflections of each other, how can this be limited to just a single solution? Of course, just constrain the position of another corner.
constraint sq[3] = 4;
...
[2, 9, 4]
[7, 5, 3]
[6, 1, 8]
...
...
%%%mzn-stat solutions=1
...
%%%mzn-stat nodes=31
...
%%%mzn-stat peakDepth=5
%%%mzn-stat-endThrough the addition of our symmetry breaking constraints the search space has been drastically reduced. The nodes statistic has been reduced from 2659 to just 31 and the overall search tree has also been reduced from peakDepth of 14 to 5. The magic square is a toy problem but is useful in demonstrating the concepts of symmetry breaking to reduce the search space and using constraints to solve some layout puzzle.
If you’re following along and want to keep playing with this model, what do solutions look like when the diagonal constraint isn’t necessary? What is a good way to get that down to just one solution? And, what does a 4×4 magic square look like? This model is just scratching the surface of what is possible in MiniZinc, they have some great documentation if you would like to read more. Let’s go back to our Settlers of Catan problem.
Optimal board layout
It should be clear that MiniZinc can be used to generate more balanced boards and markers for Settlers of Catan. To review the desired constraints:
- No two of the same resources are adjacent
- Lumber and brick are not adjacent
- Markers distributed such that 6 and 8 are not next to one another
- The four 6 and 8 markers are each on different resources
This is much more than the magic square problem. For simplicity this should be two separate models, one for the tiles and another for the markers. Otherwise, the board will stay the same and the markers will cycle through every possible permutation before a different board is generated, so they will be addressed one at a time.
Board
To start, some decision variables and constants are declared.
% Parameters
% Board size
int: nRows = 5;
int: nCols = 5;
set of int: Rows = 1..nRows;
set of int: Cols = 1..nCols;
% Resources
% 1 2 3 4 5 6 7
% enum Resource={Water, Desert, Brick, Grain, Sheep, Stone, Lumber};
set of int: Resources = 1..7;
array[Resources] of int: ResourceCounts = [6, 1, 3, 4, 4, 3, 4];Resources are represented on the board as numbers 1 through 7. ResourceCounts is the number of that resource to be placed on the board. The board is square so we need to represent water as a resource, there are six of them. There is the desert, resource lacking, tile which the thief starts on. The rest of the array is the count for the primary resources.
% Decision Variables
array[Rows, Cols] of var Resources: Board;This is the decision variable the model will be modifying in the search for a solution. Now for constraints.
% Resource counts
constraint forall(re in Resources)(
sum(r in Rows)(count(Board[r,..], re)) = ResourceCounts[re]
);The forall predicate is being used here to constrain that for each resource re the sum of the count of the re on the board is equal to the count in ResourceCount.
% No two of the same resources are adjacent
constraint forall(r in 1..nRows-1) (
forall(c in 1..nCols-1) (
alldifferent_except_0([Board[r,c]-1, Board[r, c+1]-1,
Board[r+1, c]-1, Board[r+1,c+1]-1])
)
);This one is more complicated. There are two forall predicates here with an alldifferent_except_0 constraint. The foralls iterate and constrain over every element in the board until the second to last row and column. Recall that this is declarative, forall is shorthand for generating multiple constraints at once. For each tile, its value is constrained so that it is different than its neighboring tiles unless the value–1 is 0 (recall that oceans are 1). To constrain lumber and brick from neighboring each other the alldifferent_except_0 constraint cannot be used.
% Lumber and brick cannot be adjacent
% constraint right and bottom right diagonal
constraint forall(r in 1..nRows - 1)(
forall(c in 1..nCols where Board[r,c] in {3, 7}) (
not(Board[r+1, c] in {3, 7})
)
/\ % and
forall(c in 1..nCols - 1 where Board[r,c] in {3, 7})(
not(Board[r+1, c+1] in {3, 7})
)
);
% constraint bottom
constraint forall(r in 1..nRows) (
forall(c in 1..nCols - 1 where Board[r,c] in {3, 7})(
not(Board[r, c+1] in {3, 7})
)
);Two features called reification and set notation are used here. Reification can be a performance foot shotgun sometimes and makes the lower-level models more complex, use this carefully. The set is used to check that a tile value is not in the set {brick(3), lumber(7)}. Reification is used in the inner foralls with where Board[r,c] in {3, 7}. This is saying only “iterate over tiles which are lumber and brick.” The inner-most constraint not(Board[r+1, c] in {3, 7}) checks that a neighboring tile is neither lumber nor brick.
If the model is run now ocean tiles will be everywhere, they need to be on the edges.
% Place the water on the edges
constraint Board[1,4] = 1;
constraint Board[1,5] = 1;
constraint Board[2,5] = 1;
constraint Board[4,1] = 1;
constraint Board[5,2] = 1;
constraint Board[5,1] = 1;To reduce the search space three corners of the island are constrained to be descending in value.
% break rotational symm
constraint Board[1,1] < Board[3,5];
constraint Board[1,1] < Board[5,3];
constraint Board[3,5] < Board[5,3];And finally, solve to satisfaction and output the board:
% Objective
solve satisfy;
% output[show2d(Board)];
output[ " \(Board[1,1..3])\n" ];
output[ " \(Board[2,1..4])\n" ];
output[ "\(Board[3,..])\n" ];
output[ " \(Board[4,2..])\n" ];
output[ " \(Board[5,3..])\n" ];The output is staggered to look like how the tiles are actually laid out. Let’s see what it gives us!
[2, 7, 5]
[3, 4, 6, 7]
[6, 5, 3, 5, 4]
[7, 4, 6, 3]
[5, 7, 4]
% time elapsed: 0.13 s
----------
==========
%%%mzn-stat initTime=0.013395
%%%mzn-stat solveTime=0.12374
%%%mzn-stat solutions=96
%%%mzn-stat variables=110
%%%mzn-stat propagators=135
%%%mzn-stat propagations=610914
%%%mzn-stat nodes=12549
%%%mzn-stat failures=6179
%%%mzn-stat restarts=0
%%%mzn-stat peakDepth=21
%%%mzn-stat-end96 “optimal” boards to chose from! With output[show2d(Board)]; the raw 2D array is output. Did I mention MiniZinc can be run from the command line and can output to JSON? This output can easily be piped and interpreted in Python. With some matplotlib hacking the board can be visualized.
For those who have just learned about SoC, the colors may be unfamiliar. Above, brick is red, sheep is green, wheat is yellow, ore is gray, forest is dark green, and the desert is orange. One interesting attribute for this solution is that for this set of constraints the desert tile is (almost) always in a corner. This seems to be a by product of the lumber/brick adjacency constraints.
Markers
The markers model is largely the same and won’t be repeated here. Instead of tiles it makes sure that no two numbers are adjacent and the 6’s and 8’s—the most probable resource gaining numbers—are also not adjacent.
set of int: Number = 1..12;
% 1 2 3 4 5 6 7 8 9 10 11 12
array[Number] of int: MarkerCounts = [6,1,2,2,2,2, 1, 2,2, 2, 2, 1];1’s cannot be rolled so they will be assigned to oceans, 7 will be assigned to the desert tile. This model takes Board from the previous model as input to make sure that the 7 is placed on the desert.
% Place the 7 on the Desert
constraint forall(r in Rows)(
forall(c in Cols where Board[r,c] = 2) (
Marker[r,c] = 7
)
);Since Board is a parameter not a decision variable there is no refification going on here. When writing constraints stating the constraint in simple English and they codifying it is often the best approach. For example: “each resource of each type must have have all different markers.” Which is translated as so:
% All resources have different markers
constraint forall(res in {3,4,5,6,7}) (
% all markers different
all_different([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ])
/\
% only one 6 or 8 per resource
count([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ], 8) +
count([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ], 6) <= 1
);
[7, 8, 11]
[6, 12, 10, 5]
[3, 9, 11, 8, 9]
[10, 6, 5, 4]
[4, 3, 2]The all_different constraint is being applied to the array of decision variables Marker.
The marker distribution can be improved more. Something to note about the marker solutions above is how there are some very weak vertices on the board. I’m looking at 5,4,2, and the 12,10,11 vertices, can the number of these vertices reduced? Let’s try setting a threshold on the sum of neighboring values.
% distribute markers
constraint forall(r in 1..nRows-1)(
forall(c in 1..nCols-1 where Marker[r,c] > 1) (
Marker[r,c] + Marker[r+1,c] + Marker[r+1, c+1] < 23
/\
Marker[r,c] + Marker[r,c+1] + Marker[r+1, c+1] < 23
)
);
...
[7, 11, 8]
[6, 4, 3, 9]
[10, 5, 12, 4, 8]
[6, 3, 2, 9]
[11, 5, 10]
This iterates over each tile checking the vertices with two other neighbors. The threshold is sensitive. If it’s 21 or less there exist no solutions, when it’s 22 there is just 1 solution. In about half a minute with a threshold of 23 I can find that there are 11,753 solutions. Most vertices are improved but some weak ones remain such as 3,2,5 and 2,4,12. There are 11,752 other configurations that might have more even vertices.
It may be impractical to reduce the search space without forcing certain markers on certain tiles. Unlike the five types of tiles there are ten (2–12, excluding 7) types of markers to shuffle around. That said I think the marker permutations this last constraint generates looks a little better than before. A little more matplotlib hacking and we get the board in a neat picture, markers included.
With a board layout and markers distributed across them there’s only one thing left to do: play the game!
Play testing
I got some friends together to play using a board generated with these models. With an optimal tile and marker layout and I couldn’t have been more excited to truly see what a balanced Settlers of Catan game feels like.
The pace of the game can only be described as glacial. The game was declared a draw three hours in due to nobody having much fun, for reference most games are usually around 60 minutes. The advantages each player had were marginal due to such equal access to resources. I recall the highest pointed player had seven points and most of it was through development cards.
This is an illustrative example of how fun in games emerges from complexity and competition rather than strict rigidity and equality. For example professional Starcraft or DotA would not be as interesting if everyone was forced to play the same race or the same standard set of five heroes.
It turns out that tournament SoC maps frequently have common resources adjacent as well as 6’s and 8’s on common resources. 6’s and 8’s are never adjacent though. I could not find a site for tournament boards for this post (if they are published please reach out to me) but browsed through a few final games on YouTube. This Reddit thread has some comments from tournament goers on board setup, this comment from implosionsinapie is interesting:
For the U.S. national qualifiers the boards are what I like to call semi-constructed. They completely randomize numbers and resources and then adjust accordingly so there aren’t any 6–8–5 spots or too heavy a concentration of a certain resource. It’s all up to whoever is running the tournament, though, they can make boards as simple or as difficult as they like. […]
Further work
Ports are an important part of gameplay. Ports allow players to trade two resources of a certain type for one of any other resource (a 2:1 ratio), there are also open ports where the ratio is 3 of the same type for 1. In the several dozen games I have ever played only in a handful did port access win the game, it is something that has to be planned from turn one. Strictly speaking though, it is a part of the board layout and so this model is incomplete without port placement and port placement is left up to us humans.
There exist several expansions for SoC which increase the board size, make a whole separate island, and introduce new tiles. I have actually never played them though and so I cannot speak for what sort of imbalances CP could address or if they are worthwhile to.
Conclusion
In summary, optimal boards are not more fun. CP can certainly create a board with the desired constraints but the boards aren’t fun to play on, extending the total game time more than two-fold. To modify the question: what sorts of constraints make more fun board layouts?
Source code
All presented MiniZinc code available in this GitHub repository.