3
\$\begingroup\$

I have a dice mechanic where players roll a number of D10s and have a different number of re-rolls they can use to maximize the total.

For example: The player has 3D10 and 2 re-rolls.
They roll 9,6,3 and choose to keep the 9 and re-roll the 6,3
The first re-roll gives 7,5. They choose to keep the 7.
The second re-roll gives a 4.

The total is therefore: 9+7+4 = 20.

I would like to be able to model this is something like AnyDice but I can't get my head around it.

To clarify a few points from the comments. The re-rolls are optional and the player can choose to stop at any time. They are trying to maximize their result because it represents the amount of money they earn from an exchange.

Based on this question on Math.SE and the answer by @theoza the optimal strategy is:

  • 1 re-roll : keep 6+
  • 2 re-rolls: keep 7+
  • 3-4 re-rolls: keep 8+
  • 5-8 re-rolls: keep 9+
  • 10+ re-rolls: keep 10
\$\endgroup\$
  • 1
    \$\begingroup\$ How do they choose what to keep? Could you articulate the logic flow here? \$\endgroup\$ – Brian Ballsun-Stanton May 26 '15 at 4:37
  • 4
    \$\begingroup\$ I'm going to let my vote to close stick: you don't know what you want to model, so we can't really help you model it. That is probably the part you're having trouble getting your head around. The model for chances of reaching a particular number differ and involve strategy as well as statistics. The model for odds of getting various numbers is not meaningful, because of player decision making involved in rerolls. \$\endgroup\$ – doppelgreener May 26 '15 at 5:24
  • 3
    \$\begingroup\$ @Ben Yes, but you don't know how your player will decide whether to reroll. I can write a function to model whichever strategy your player is using, but I can't include all of the functions for every single possible strategy your player might use in a single answer. \$\endgroup\$ – Miniman May 26 '15 at 5:46
  • 1
    \$\begingroup\$ @Ben The way to get the biggest score is to reroll & risk everything until you get 30, but that's not useful to examine. Working out the optimum strategy is a whole other ballpark to working out how to model it, and there are different optimum strategies when engaging in different situations. In-game you'll never be trying to get the biggest number (too unlikely): you might be simply trying to beat an opposition of 14, or you might be trying to get a reasonably high number (but it's okay if you don't get "the biggest"). It's kinda jumping the gun to try to model a strategy we don't know yet. \$\endgroup\$ – doppelgreener May 26 '15 at 5:53
  • 3
    \$\begingroup\$ Even if we assume the goal of just trying to maximise your expected value, a) as doppelgreener points out, this isn't actually what that players will want to be doing most of the time and b) this is sadly not a trivial problem. The interaction between the amount of value you lose by rerolling a die and having it come out lower, and the amount of expected value you gain by rerolling a die and having it come out lower, are... awkward. That said if you want to make a question about what the optimal strategy is for MD10 and N rerolls, it would probably fit in fairly well on Math.SE \$\endgroup\$ – a computing pun May 26 '15 at 6:03
3
\$\begingroup\$

Let's assume that we are simply trying to maximize the expected value of our roll. (As discussed this might not be a realistic representation of actual gameplay, but we can work it out anyway.) Then the rolls on any of the dice don't affect our decisions to reroll for other dice - that is, any one die's rolls and strategy is independent of other dice and we can work out expected value as the expected value for one die times the number of dice.

Now for the expected value of a N-sided die with R rerolls, we can establish a recurrence relation.

Starting with 0 rerolls, this is the normal expected value for a single die:

$$ E = \dfrac{1+N}{2} $$

Given \$E\$ as the expected value for R rerolls, we calculate \$E'\$ for R+1 rerolls:

$$ E' = P(reroll) \cdot E + P(keep) \cdot (average keep) $$

Now the decision to reroll is based on whether our expected value with R rerolls is higher than our current roll. Let \$\lfloor{E}\rfloor\$ be the floor of \$E'\$ (i.e. \$E'\$ rounded down to the nearest whole number - the highest number we will want to reroll), then:

$$ P(reroll) = \dfrac{\lfloor{E}\rfloor}{N} \\ P(keep) = \dfrac{N-\lfloor{E}\rfloor}{N} \\ \text{Average keep} = \dfrac{\lfloor{E}\rfloor+1 + N}{2} $$

This gives us a formula for R+1 rerolls:

$$ \begin{align} E' &= \dfrac{E\lfloor{E}\rfloor}{N} + \dfrac{(N-\lfloor{E}\rfloor)(N+\lfloor{E}\rfloor+1)}{2N} \\ &= \dfrac{2E\lfloor{E}\rfloor + (N-\lfloor{E}\rfloor)(N+\lfloor{E}\rfloor+1)}{2N} \end{align} $$

With an \$\lfloor{E}\rfloor\$ in our final formula, we can't get a nice closed form for any number of rerolls, but we can just calculate the values from the recurrence relation. For example, for your example with \$N=10\$:

$$ \begin{align} E[\text{0 rerolls}] &= 5.5 & (\lfloor{E}\rfloor=5) \\ E[\text{1 reroll}] &= \dfrac{55 + 80}{20} = 6.75 & (\lfloor{E}\rfloor=6) \\ E[\text{2 rerolls}] &= \dfrac{81 + 68}{20} = 7.45 \end{align} $$

For 3D10 with 2 rerolls our expected value is \$(3 \times 7.45) = 22.35\$. Our strategy is to reroll all values 1-6 on our first roll, reroll all values 1-5 on our second roll.

\$\endgroup\$
  • 1
    \$\begingroup\$ I am not sure by what measure you determine this method to be maximizing the expected value of a roll. Mind explaining? What does it mean to maximize the expected roll (considering you tolerate 7's instead of shooting for 9's and 10's), and how can you tell that this strategy does that? \$\endgroup\$ – doppelgreener May 27 '15 at 3:02
9
\$\begingroup\$

This cannot be nicely modeled purely as probability

The issue with this system is that it's not purely a matter of randomness, it's (as you seem to be presenting it) a matter of both randomness and decision-making. A dice rolling program can model the randomness, but not the decision-making (at least, not in a manner that is of much use).

Basically, using a reroll can sometimes improve your total and sometimes reduce your total. The question of whether or not to use a reroll depends upon what the player wants. If we make an assumption about the player's goal, then we can write an expression that assumes they make certain decisions.

If our goal is to get a result of 21 or higher (on 3d10), then the optimal strategy is to always reroll our lowest die until our total is 21 or higher.

This actually produces quite a different curve from the curve where the goal is to get a result of 22 or higher. For example, if we need a 22, we have 7,7,7, and we have 1 reroll, we need to reroll, even though we are likely to end up with a worse result than just keeping.

If our goal is just to get the highest possible score at all times, then the optimal strategy is probably¹ to always reroll your lowest die if it's a 5s or less, otherwise stop rerolling.

(¹Sadly, this isn't actually true, but it's a good approximation when number of rerolls is close to 0. The truth is even more complex!)

\$\endgroup\$
  • 5
    \$\begingroup\$ The lesson here might be: work out what result you're trying to get first before you try to do statistical modelling, or it's going to be really hard to model anything meaningful. \$\endgroup\$ – doppelgreener May 26 '15 at 5:21
  • \$\begingroup\$ I wrote such a beautiful function, but I'm going to have to toss it - you're right on all counts. \$\endgroup\$ – Miniman May 26 '15 at 5:29
  • 1
    \$\begingroup\$ I will accept that this beyond me and go on, diminished, into the west. \$\endgroup\$ – Ben May 26 '15 at 5:51
  • \$\begingroup\$ This is not true. Game theory (rational choice theory) beautifully meshes in the probability of utility and choice. By utilizing expected values and probability it can optimally determine if you should reroll a die or keep it. Since you must take the result even if its worse, the notion of a reroll provides no extra utility gain. The expected value of d10 is always 5.5. Game theory would then dictate that you should keep any roll above and reroll anything below 5.5. (balances risk vs. reward). Rerolling die above it is too risky. Don't reroll die below it and you're playing it too safe. \$\endgroup\$ – Spoo Sep 30 '16 at 15:43

Not the answer you're looking for? Browse other questions tagged or ask your own question.