Optimal Catan

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 169msec

Just 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 163msec

If 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-end

This 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-end

Through 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-end

96 “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.

“Game X” Is Only as Fun as…

Keystone gameplay elements, called so because if they’re taken out the game isn’t that much fun anymore. I started thinking about this during a bitter game of Overwatch and I’ve applied it here to bunch of other games:

Player Unknown’s Battlegrounds (PUBG) is only as fun as the loot you find in the first five minutes. If you’re in the top-20 on Miramar without a a scope you’re going to have a difficult time going forward. The same is somewhat true for the Erangel map but there’s much more consistent cover and loot is a little more dense from the start too.

Fortnite is only as fun as the rarity level of the guns you find. Unlike the staggered –textile mixed– loot spawns of PUBG, the potions (armor) and type of weapons you find in the beginning do not so much influence your fun in the long run.

Overwatch is only as fun as your teammates are willing to cooperate. This is independent of game mode, there’s this strange contrast between Quick Play and Competitive game modes. In competitive, people can be resistant to changing characters which put the team at a deficit, even to the point where they’ll spitefully throw the game. In Quick Play, people play the characters they want to play, leading to deficient and unusual compositions of all DPS and tanks or or all DPS and one secondary healer. Usually, the team to take some composition initiative get’s momentum and wins.

DOTA 2, LoL, Heroes of the Storm (MOBA’s) are similarly fun to Overwatch. It’s only as fun as your team mates are willing to cooperate. Unlike Overwatch though, it’s much harder for a single person to carry the team.

Hearthstone is only as fun as the cards you initially get and how well they align with the current meta. However, you will always be outspent by the people who take the game seriously.

World of Warcraft is only as fun as your character’s level and/or your guild’s ability to organize and raid. There are some truly amazing sights through out the game but until you’re of a certain level you’ll never get to see them. The even larger content needs to be done through raids which need a guild to do. Once, I was lucky enough to raid Molten Core with 39 other people and it was very exciting.

Path of Exile is only as fun as the quality of your build. The game has a staggeringly complex skill tree, while most basic builds can work through the first and second difficulty levels the third one will really test it, and it’s usually where I’m forced to scrap my characters. There are plenty of sample builds on the forums but they too often require unique equipment which is extremely expensive and drop very, very, rarely.

Kerbal Space Program is only as fun as the length of your patience and determination to reach other planets or build space stations. With a little experience missions to the Mun and Minmus can become routine. However missions to the Jool and the far outer/inner planets consist of lots of time waiting for comparatively small maneuvers only to get there and find out you don’t have enough fuel to complete the orbital burn or you forgot to deploy the solar panels and you’re out of power. Being honorable, you revert the save to vehicle assembly and redesign your rocket only to go through that whole process again.

Rocket League is only as fun as the mean skill all players compared to your skill individual. If your skill is lower than all other players it can be a bit daunting to have cars of all variety flying around while you drive in circles just trying to get some boost. This does not apply to 4×4 modes, anything can happen there.

Minecraft is only as fun as your desire to explore and create. The caverns are deep and endless, but what is over that hill? The sun is low, the monsters are coming, are there enough torches? To my 1:1 scale model of Helm’s Deep!

Starcraft 2 is only as fun as you know your build order and it’s the right build order to counter your opponent. Contrary to popular belief, unless you’re Master league or higher, the game is not so heavily depended on super-human actions per minute (APM) and micro ability.

X-Com[1] is only as fun as your ability to best position a squad of units against an unknown enemy. Though ultimately, it relies on the secret RNG which determines the actual probability of your shots to hit the target.

Civilization (chose your version I through VI) is only as fun as the AI is able to be even to you point-wise. An experienced player playing on Settler (easiest) difficulty won’t have much fun as they stomp across the globe. On higher difficulties, it feels as though each move is precious and the struggle against your digital strategic equals will not be firmly decided until the last move!

No Man’s Sky is only as fun as you can convince yourself you’re having fun collecting resources in order to build better tools used to collect more resources to collect more tools.

  1. This is only applicable to the current iterations of the game, the original games in the 90’s have some mechanical differences which do not apply.

Alto’s Odyssey Review

I place the first game, Alto’s Adventure, high in the echelons of great iOS games. Alto’s Odyssey builds on the simplicity of Adventure in just the right ways. While I still greatly recommend the first game, after playing all the way through Odyssey I’m starting to think you should skip it entirely.

The core difference between the games is the terrain, there are three new “zones” Dunes, Canyons, and Temples. Each have their own unique set pieces and corresponding tricks you can do in that zone. For some examples: Canyons has cliff faces you can do wall rides on, it’s really satisfying to chain these however if you’re not paying attention you can end up beginning a flip and soon crash. You can only wall ride when in the standing orientation not in the middle of a flip like the wing suit. In the Temple zone there are waterfalls who’s water runoff is similar to the ice flow feature in Adventure. Sometimes, at the end of these flows are pools which act as trampolines if you land in them with enough force. The Dunes are pretty plain but has many air balloons which have lines you can ride between them, being non-fixed points the lines oscillate, making them a little more challenging to land on. The variety of landscapes is simply a joy to endlessly ride through, where going over 20km in Adventure becomes quickly repetitive, 20k in Odyssey is a cool breeze on a hot day.

The next three paragraphs are for if you have played all the way through Adventure. There is a potential spoiler about an unlockable character’s abilities in the second paragraph.

If you have played all the way through Adventure, be prepared to do it all over again with the same characters and similar power-ups. For having completed Adventure you get nothing, I was hoping for maybe some extra currency, maybe half of the power-ups I’ve already grinded for or not having to go through roughly the first 10 levels of essentially the same challenges all over again. (Let’s face it, you won’t use anyone but Maya until you unlock the final character or a challenge requires someone else.)

In the theme with swapping old mechanics for new yet similar ones, instead of disturbing elders who then chase you, there are lemurs you startle. (I guess that cements the game’s setting in Madagascar?) The chases are shorter but more dangerous, the lemurs are a bit faster, can run on rope lines, and will jump at you even if you aren’t on the ground. However, the final character is immune to these leaping lemurs! A great addition to the game, Elder chases are the number one reason why my runs would end in Adventure and it’s a relief I don’t have to pull the same acrobatics to avoid late-game lemurs here.

There are no more llamas and I miss them. Birds of Paradise will fly with you for a minute or two and nearby collect coins, but it’s not the same as wrangling a herd after running over a horn in the first game. A radio beacon replaces the llama horn, running over the radio drops some vessels with coins and power-ups in them, if you level the beacon up twice it can be significantly lucrative.

Adventure is still a joy to play to this day, only until the final character was unlocked did Odyssey replace that for me. I expect I’ll be playing it as much in the coming years. The early drafts of this review were rough on Odyssey, perhaps it was that I could not get fully used to the new and sometimes unfair terrains, or maybe the grind of getting all my characters and power-ups back soured me, but once you get through it Odyssey becomes much more rewarding to play than Adventure. (It’s so tempting to end this review with “See you on the slopes!“ but then again I guess I just did, sorry.)