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.

The Office, Parks and Recreation, and the National Pathos

In January 2009, I gathered with my classmates in high-school to watch the inauguration of Barack Obama. There was a collective anticipation in the air that things are about to seriously change. One of the principles that Obama ran on was that change through political action was possible, the government wasn’t some immobile beast only set on bailing out banks as it had the months prior, it could work for the people too.

Four months later Parks and Recreation (P&R) began airing on NBC. The first season was a little rough, but by the second season the show really hits its stride (if you have never seen it I recommend simply starting at the second season). P&R introduced the American public to Leslie Knope, an ever optimist busy-body who was the very embodiment of what people thought Obama would bring to American politics. Played by Amy Poehler, she was a refreshing redefinition of what it means to be a boss in the workplace, especially compared to her predecessor: Michael Scott of The Office and what he represented to America.

Adapted from the popular British version, The Office began airing on NBC in March of 2005, three months after the second inauguration of George W. Bush. By this point Bush had already introduced such words as “misunderestimate” and “nucular” to American English as well as a slew of phrases today coined as Bushisms. He was a president who would often stumble over his own words in the manner in which one would read a speech off hastily written notecards. In these aspects, and many more, he embodied everyone’s incompetent boss across the country. In television, this manifested in the ever awkward and inept Michael Scott, as played by Steve Carrel. The Office was a huge success from the start.

Michael Scott was everything people laughed and cringed at in their bosses. Nary is there a moment for the viewer to breathe—either from laughter or embarrassment—when Scott would attempt offensive impersonations, make an absurd request, or just crack a bad joke.

The Office continued for nine seasons until 2013, well into the Obama years. In 2011, during the seventh season, Steve Carrel and thus Michael Scott left the show. Carrel’s contract was up mid-season, but the show’s tone had also changed. It was the hapless existence portrayed in The Office’s first four to five seasons that extruded comedy and made the show so successful. The seasons just before–and after–Michael’s departure are largely forgettable as the show shifted its narrative from the foibles and follies of Michael to Jim and Pam getting married and building a family. I believe this shift was in some part due to the pathos of the incompetent American leader fading and being replaced by a more positive, capable, one as embodied Obama and reflected in the character of Leslie Knope. Overall, we can read this as a shift from a negative to a positive outlook.

Parks and Recreation ran seven seasons ending in 2014 with the final season taking place in the year of 2017. The ever optimistic outlook of the show displayed a parallel universe where the nature of congress wasn’t obstructionist and where, in more than one episode, challenges could be overcome through compromise and mutual agreement.

The Office has been making a resurgence in the recent years. The show’s subreddit, /r/dundermifflin, is surprisingly active despite the show being off the air for over five years. I think a large part of it is the meme-able and gif-able moments but also that we have another—only more grossly—incompetent leader at the helm of America. It’s fun to laugh at despair and The Office provides a cultural baseline through which to do that. P&R provides meme-able moments too but they frequently carry a positive voice.

These shows were both media reflections of the national pathos, the feelings for those times. I posit here that the extremely popular late 90’s sitcom “Friends” backs this up more by how it embodied the complacent “end of history” attitude of the 90’s. Other posts about Friends have been written with this direction. The Office could only have been successful during the Bush years via a character like Michael Scott. P&R could have only been successful during the Obama years, where the protagonist is optimistic and charismatic. When a future candidate from the left party makes it to the White House it would be interesting to see if P&R ever makes a resurgence. Until then, what show could possibly better define the years we are in today?

Towards Emotional Machines

While the vast community of AI is focused on getting machines to recognize everyday objects there is a small faction figuring out how to get machines to meaningfully communicate with us. The following are three ethical points that should be considered in the endeavor of emotional machines.

Deception

We need to look no further than science fiction for reasons for pause about fully developing emotional systems. The 2012 film “Prometheus”, features an android named David who’s ulterior motives and ability to lie kill the majority of the human characters in the film. On the opposite end of this spectrum, the 2013 film “Her” features a fully developed relationship between a human and a non-corporeal, artificial, digital assistant: Samantha. While David can lift boulders and Samantha is trapped in a machine, we should not discount either of their capability to manipulate and evoke a spectrum of emotions, from anger to love. Feelings are real and we should be careful in developing artificial systems which have the power to manipulate them.

It is not out of the realm of imagination that, in a zero-sum scenario, our pipeline [a machine learning model which takes an image of the face and identifies emotions] could be used to exploit human actors involved in the scenario. By analyzing the emotion on an actor’s face, with a simple “scheming” module, our pipeline could deliver an expression that could trick or deceive the human. We must not make any mistake here, the machine does not feel “happy.” Last winter, an AI avatar received criticism for joking about destroying humanity. In response, the creator had this to say:

“Many of the comments would be good fun if they didn’t reveal the fact that many people are being deceived into thinking that this (mechanically sophisticated) animatronic puppet is intelligent. It’s not. It has no feeling, no opinions, and zero understanding of what it says. It’s not hurt. It’s a puppet.”

“Facebook’s head of AI really hates Sophia the robot (and with good reason)”, James Vincent, The Verge, Jan 2018. (URL)

Though the Muppets are puppets too, their nature is more observable, the puppet master is often nearby and we can see his or her lips moving subtly. They are transparently built and controlled for the purpose of entertainment. Until we can reasonably establish a framework for whether a being has emotions which it can reason about, we must keep the above warning in mind.

Relationships

When does a personal assistant become capable of being in a more emotional relationship? When does Andrew, the Bicentennial Man cease to become merely a robot? When does Siri become Samantha? Personal assistants can remember every quantifiable piece of information about us, our names, our birthdays, our calendar appointments; but they have no agency. When will they ask us if we want to buy tickets to a movie we might like or recommend a grocery item for a dish we might like?

If they can be in a relationship they must be responsive within the context of one. Today, emotional robots and agents are primarily built for the purposes of research (personal assistants are not yet emotional). If and when they reach some emotionally functional pinnacle and they are deployed in the real world, will we be nice to them? Without any repercussions we permit ourselves to yell in frustration at Alexa and Siri for not understanding us, will emotional agents change our behavior if they can react to our anger? Should a personal assistant refused to give us answers–or provided less efficient routes to our destinations–if we were regularly rude to them? This brings in some contextual questions about the relationship too; with the agent: are we roommates, are they an old friend, or have we just decided to get serious and move in together? How should they behave when two people do actually move in together?

Today agents such as Siri or Alexa are individual per phone or Amazon account, isolated from other instances of themselves. If we are to see them more as coherent individuals that we care about they should be unified across our computing devices, like Jarvis from Marvel’s Ironman.

Perception

How can we change the way we treat machines if all we see are machines? Sophia, the subject of the quote above from The Verge, can exhibit an impressive range of emotions. However, ignoring the abrasive effect of the Uncanny Valley, to anyone who can recognize its her façade (the cluster of wires on the back of her head are sometimes covered with a wig) will never see anything but a robot.

Without some heavy investment in robotics as well as the material sciences, it will be quite difficult to make an android which will not trigger some disconcerting uncanny valley effect. For this reason we should be focusing on the digital realm to make machines more human-like. We now delve very closely to the subject of the 1950 paper “The Imitation Game” by Alan Turing.

“No engineer or chemist claims to be able to produce a material which is indistinguishable from the human skin. It is possible that at some time this might be done, but even supposing this invention available we should feel there was little point in trying to make a ‘thinking machine’ more human by dressing it up in such artificial flesh.”

The Imitation Game, Alan Turing, 1950

Machines must be able to think as we do–rather unidentifiably machine as Turing states–before we should make efforts to give them some corporeal form.

Thanks for reading. “Deception” section adapted from a project paper for Intelligent Interactive Systems (Spring 2018). (PDF of report)