# Stickered Dice Game

You and your friend play a game.

To begin with, each of you has an unlabelled die. On the table laid in front of you are 12 stickers labelled 1-12.

The first player chooses one of the stickers and places it on their die. For each subsequent turn, the next player must keep sticking a number on their die until the sum of all their chosen numbers exceeds that of their opponent's sum.

When one player has stickered all the sides of their die, the other player makes use of the remaining stickers. Finally, both of you roll your dice and the player with the greater number wins.

Is this a fair game? Or would you rather go first/second? What would your strategy be?

Assuming you know your friend always takes a greedy approach (i.e. takes the highest number available), is there a strategy you can use to secure a win?

• Is a player limited to 6 stickers? (If a player has 6 stickers, not all stickers are chosen, and still has less than their opponent, what happens?) Apr 22, 2023 at 11:26
• @ralphmerridew Yes. In that case, the opponent is forced to choose the rest of the stickers. I apologise for the unclear prompt :] Edited! Apr 22, 2023 at 11:32
• If I end my turn without exceeding my opponent's sum, what does my opponent do on his turn? Apr 22, 2023 at 16:21
• @AxiomaticSystem Hmm. I was thinking: if you have an equal sum (thus not exceeding your opponents) then you can end your turn. Otherwise, your opponent wouldn't be able to make a move. But also, if both players stall forever that wouldn't be very nice. Apr 22, 2023 at 16:28
• @AxiomaticSystem I feel as though the best way to resolve this is to force each player to keep choosing numbers until their sum is greater. I'll make an edit once again. Sorry to everyone that was working on the original problem! Apr 22, 2023 at 16:40

The game is a draw. Specifically, with six-sided dice, the best winning probability that the first player can guarantee is $$0.5$$.

Assume that Aethelred and Brunhilde are playing the game with $$n$$-sided dice with Aethelred going first.

After the two players have finished picking their stickers, Aethelred has a length-$$n$$ subset $$A$$ of $$\{1, \dotsc, 2n\}$$ while Brunhilde has the complementary subset $$B$$. A game then consists of chosing $$i$$ from $$A$$ and $$j$$ from $$B$$ and checking which is bigger. Since all such pairs occur with equal probability $$1/n^2$$, the probability that Aethelred wins is \begin{align*}\frac{\# \{(i, j) : i > j, i \in A, j \in B\}}{n^2}\end{align*} (notice that draws are impossible, since $$A$$ and $$B$$ have no elements in common).

So for example, if $$n=3$$, one possible way in which the game plays out ends with $$A = \{1, 4, 5\}, B = \{2, 3, 6\}$$, in which case $$\Pr(\text{Aethelred wins}) = 4/9$$.

Using this idea, we can build a minimax tree for the game. We encode a game state as a disjoint partition $$(S_1, S_2, R)$$ of $$\{1, \dotsc, 2n\}$$, where $$S_1$$ is the current set of labels of the player that is about to take their turn, $$S_2$$ the other player's set of labels and $$R$$ is the set of remaining labels.

A move then consists of the current player taking a subset $$T$$ of the remaining indices, adding them to their own set, and then switching the turn. That is, the game enters the state $$(S_2, S_1 \cup T, R \setminus T)$$.

To score the game, we'll say that in a final position with no remaining labels \begin{align*} \mathsf{score}(S_1, S_2, \{\}) &= \# \{(i, j) : i > j, i \in S_1, j \in S_2\} - \# \{(i, j) : i < j, i \in S_1, j \in S_2\} \\ &= n^2(2\Pr(\text{Current player wins from state } (S_1, S_2, \{\})) - 1) \end{align*} so that the probability of the current player winning from state $$(S_1, S_2, \{\})$$ is $$\frac{1}{2} + \frac{\mathsf{score}(S_1, S_2, \{\})}{2n^2}$$ and so that $$\mathsf{score}(S_2, S_1, \{\}) = -\mathsf{score}(S_1, S_2, \{\})$$.

Positions with a nonempty $$R$$ are scored under the assumption that the opponent always plays perfectly, maximising their position's score. That is, after a valid move $$T$$, the current player's score is $$-\mathsf{score}(S_2, S_1 \cup T, R\setminus T)$$, so the current player maximises score according to $$\mathsf{score}(S_1, S_2, R) = \max_{T \text{ is a valid move}} [-\mathsf{score}(S_2, S_1 \cup T, R\setminus T)].$$

This is now a standard minimax problem that can be solved using a minimax search tree. I've implemented a (very badly optimised) version here, abailable on Try it Online.

Running the above code with $$n = 6$$, we find that the score of the initial position $$(\{\}, \{\}, \{1, \dotsc, 12\})$$ is $$0$$, and so the first player (Aethelred) has a probability of $$0.5$$ of winning assuming perfect play. One possible perfect game consists of Aethelred and Brunhilde each selecting one sticker at a time, resulting in \begin{align*}A &= \{5, 3, 12, 2, 10, 7\}\\B &= \{6, 4, 11, 8, 9, 1\},\end{align*} where each label is picked in the order presented. Notice that there are many possible perfect games.

• you say for n=3, A chance to win is lower than B, the. you generalize it is 50%?
– Oray
Apr 24, 2023 at 7:44
• moreover, A would choose 12, and B would go for 11/10 in my opinion for the best case scenario.
– Oray
Apr 24, 2023 at 7:45
• The $n=3$ example I had was only to illustrate the probabilities in one possible game state, not the optimal strategy. If A and B play optimally with $n=3$, then A wins with probability $5/9$ (the probability of winning cannot be $0.5$ when $n$ is odd). Apr 24, 2023 at 9:25
• Also, as I said, there are many different optimal strategies. A starting with 12, then B with 10, 11 is also a draw, with the game ending with $A = \{12; 3, 8; 6; 9; 1\}, B = \{10, 11; 4; 5; 7, 2\}$ (labels chosen in the same turn are separated by a comma, in a different turn by a semicolon) Apr 24, 2023 at 9:27