How to model a dice pool with re-rolls mechanic? [closed]

Question

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

Answer 1

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.

Answer 2

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!)