Developing a heuristic for maximizing the "covering" of a distribution

Question

Context

There's a board-game called Settlers of Catan in which players compete to be the first to gain 10 victory points by trading various resources in exchange for pieces (or cards) worth victory points. A player gains resources when the dice are rolled and they own a particular piece (a settlement) adjacent to a resource tile that corresponds to the roll. For example, I have a settlement adjacent to an ore resource tile labeled $8$, in all cases that an $8$ is rolled, I gain one ore.

In the beginning of the game, players take turns choosing where their first two settlements will be on the map. This can be an important part of the game, as a player's first placement will affect their starting momentum, ultimately affecting how they play in the middle- and end-games.

Here is an illustrative example of the board. Notice, the maximum tiles one settlement can touch is three, at the vertex created by the sides of three hexagons.

Aside

In my experience of playing, I've found that by placing settlements that simply maximizes my expected return, I'm not as likely to win. For example, if my first two settlements I've placed are on vertices $\{5,8,10\}$ and $\{5,8,11\}$, despite the fact that these rolls are likely, because I've "doubled-up" on $5$s and $8$s, the outcome of my game tends to be worse.

This is in contrast to placing settlements on say $\{5,8,10\}$ and $\{4,9,11\}$. Although these are less likely to be rolled, by spreading my coverage of the distribution, I reduce the risk of turns where I don't gain a resource.

The Problem

We'd like to develop a heuristic to aid a player in picking the spots on which they should place their first two settlements, only taking into account the number labels of the resources (not the resources themselves, or ports, etc.).

So Far

There should likely be two functions, $f_1$ and $f_2$, that correspond to the placing of the first settlement and the second, respectively.

$f_1$ is easy to define, it takes a set of three, $x,y,z$, representing the three labels on the adjacent resource tiles (we'll assume every placement will be adjacent to three tiles despite the possibility of placing next to two or only one). It is equal to the addition of each of the probabilities of those outcomes, except in the case of a $7$ being rolled, take it as a given that $7$s are bad.

So, we have a modified $p(x)$ that has a domain of $[2,12]\setminus\{7\}$ with the following image:

• $p(2)=p(12)=\frac{1}{36}$
• $p(3)=p(11)=\frac{2}{36}$
• $p(4)=p(10)=\frac{3}{36}$
• $p(5)=p(9)=\frac{4}{36}$
• $p(6)=p(8)=\frac{5}{36}$

Note: We've removed $7$ from the domain because within the game, there are no resources labeled $7$.

Then $f_1(\{x,y,z\})=p(x)+p(y)+p(z)$

The More Interesting $f_2$

Now we get to define $f_2$ which represents the player's second settlement placement. As I alluded to in the aside, we should take into account the player's previous placement such that $f_2$ depends on two sets each of three values, $\{x_1,y_1,z_1\}\{x_2,y_2,z_2\}$.

The Questions

My ultimate question is, how do we codify the intuition of "spreading out the values"? I'm thinking that either there should be a penalty for "doubling up" or a bonus for "spreading out", the former at first glance seeming easier.

However, I'm not sure how to do this in a function.

• How, using mathematical notation, do I say, "the length of the intersection of these sets"? (That's at least what I'm thinking, the penalty will be proportional to the number of shared elements between the two sets.)
  • Is this a good start? $f_2(\{x_1,y_1,z_1\},\{x_2,y_2,z_2\})=f_1(s_1)+f_1(s_2)-\alpha\left|s_1\cap s_2\right|$
    • One thing about this, I'm not sure that this is a good penalty since the penalty doesn't take into account the probabilities, that is, doubling-up on $9$s is not as bad as doubling-up on $12$s, but maybe this is already taken care of in the initial use of $f_1$?
• Further, how do I determine a good penalty coefficient?
• Or do I need to? Does there already exist some notion within statistics or math that captures "covering a distribution", that is, ensuring that no matter what the outcome, you have a return.
• Am I going about this all wrong and is there a simple, elegant way to do this?

Answer 1

Sure there's a measure of "covering a distribution". It's called probability!

We can see why ${5,8,10}$ and ${5,8,11}$ together aren't as likely to gain at least one resource as ${5,8,10}$ and ${4,9,11}$ by calculating the probability that we do that -- gain at least one resource.

In the first case:

P(get at least one resource) = P(5)+P(8)+P(10)+P(11) = (4+5+3+2)/36. However, the "36" is a nuisance, so drop it. So P(5)+P(8)+P(10)+P(11) $\propto$ 4+5+3+2 = 14

P(get at least one resource) = P(5)+P(8)+P(10)+P(11)$\,$ +$\,$ P(9)+P(4) $\propto$ 4+5+3+2$\,$ +$\,$ 4+3 = 21

So if we call the thing proportional to the probability "the score" (it's actually 36 times the probability), we should be able to get the "best" outcome (in terms of getting the higher probability of at least one resource).

But this needs to be fast. Can you remember how many ways out of 36 to get a 5? or a 10? Here's a way to work it out fast if you don't have them all memorized:

If the number you're looking at is less than 7, (5, say) subtract 1 (5-1=4). That's it's 'score' (36 times its probability). If the number you're looking at is more than 7 (10, say), subtract it from 13 (13-10=3) to get the score. (But only do this if the number isn't already present.)

If the roll number is <7 you add one less than the number to the total, and if it's greater than 7 you subtract the number from 13 and add it to the total, but only add a given roll in once.

So if you already placed $(5,8,10)$ and the next one is $(5,8,11)$ that can only add 13-11=2, while $(4,9,11)$ must add more (the 11 adds the 2, same as before, but it has more to add). So the second one is better.

This calculation is very fast.

(On the other hand, ${5,8,10}$ and ${5,8,11}$ may actually be a better choice if you're good at trading or can build a road to a port; getting at least one resource isn't the only important thing)

that is, doubling-up on 9s is not as bad as doubling-up on 12s,

If you're interested in something other than P(at least one resource), it might, but if that P(at least one resource) is the thing you want to maximize, then the above score-proportional-to-probability calculation will work perfectly.

Alternatively, you might like to score double-ups as something more than 0; perhaps 1/3 of the score (to represent value potentially gained in trade). So ${5,8,10}$ and ${5,8,11}$ would be worth more than 14; it would be 14 + the extra 1/3 score for the second 5 and 8 = 14 + (4+5)/3 = 17. Still not as good as the other choice, but not so bad.