What is the optimal strategy for deciding dice to reroll when trying to reach a target value?

Question

Let's say that I have N dice (standard d6) and I'm trying to reach a value of x or higher. I roll all of the dice once and I don't get my target value. I can do one reroll and can freely choose which dice to reroll and which to keep as they are, but I have to accept whatever number I get with the reroll.

Is there a a statistically valid way of calculating which dice I should reroll? So for example if I have 3 dice and have a target value of 18 I would want to reroll any die that wasn't a 6. However, what if my target number is a 17 and I have 5's on all dice, I need to reroll one die, but how do I determine how many to reroll?

depending on how difficult it is to determine the optimal rolling strategy I'd also be interested in any shorthand strategy that would allow one to quickly come up with a close approximation to the ideal solution.

ps. I'm asking this here because this situation comes up in so many board games. I know the Math board would likely be better able to give me a quick answer, but I figure the answer is more useful here, this is where other's wanting to know such a strategy are more likely to find it.

Answer 1

You want to go through each of your dice from lowest to highest and, if your chance of success is at least as good if you re-roll that die than if you do not re-roll that die, add that die to your list of re-rolls. As soon as you find a die that worsens your current chance of succeeding, stop, and re-roll all the previous dice in this procedure. If you run out of dice, re-roll everything.

For example, if you roll [4, 5, 5] and are trying to beat a 17, here is what it would look like:

1. Base case, re-roll nothing: chance of success = 0.

2. Consider re-rolling [4]: chance of success = 0. This is the same, so keep going

3. Consider re-rolling [4, 5]: chance of success = 1 / 36. This is better than the previous proposition, so keep going.

4. Consider re-rolling [4, 5, 5]: chance of success 4 / 216. This is worse than the previous proposition, so stop and re-roll the previous proposition, namely [4, 5].

Optimal result: re-roll [4, 5].

The reason that this works is that if re-rolling a given die is not helpful, you won't want to re-roll any die with a higher result as it will be even less beneficial. Similarly, if re-rolling a given die is helpful, you will want to re-roll any die lower than it at least as much, because re-rolling that will be even more beneficial. This assumes all of your dice are the same size (ex. D6s). The analysis is much more complicated with dice of different sizes.

Here's a more formal (i.e. Python) statement of the algorithm:

def find_rerolls(dice, target):
    if sum(dice) >= target:
        # If you are already over the target, don't re-roll anything
        return []

    rerolls = []  # This is the list of dice to be re-rolled, which starts empty
    p = 0  # This is the probability that your current rerolls will be greater than the target value
    for die in sorted(dice):  # for each die, starting with the lowest
        new_rerolls = rerolls + [die]
        # This is the total we would need to beat given the dice we are re-rolling
        reroll_target = target - sum(dice) + sum(new_rerolls)
        new_p = probability_greater_than_target(len(new_rerolls), reroll_target)
        if new_p >= p:
            # re-rolling this die improves your chance of success (or is at least break-even), so do it
            p = new_p
            rerolls = new_rerolls
        else:
            # Re-rolling that die hurts.  Given all other dice are at least as high, stop trying
            return rerolls
    # Re-roll everything
    return rerolls

The only thing missing from this is the implementation of probability_greater_than_target(number_of_dice, target) (i.e. what is the probability that a set of dice will be higher than a target without re-rolls), which is then a well-formed question for math stack exchange.

Answer 2

Expected Value

Expected value is the statistically 'average' result of a random event. That is to say, if you did the randomization action a million times, what would be the average value of your results.

It's calculated as P(R1)*V(R1) + P(R2)*V(R2) + .. + P(Rn)*V(Rn), where P(Ri) is the Probability of Result i, and V(Ri) is the Value of Result i.

For a single die roll this amounts to 1/6 * 1 + 1/6 * 2 + 1/6 * 3 + 1/6 * 4 + 1/6 * 5 + 1/6*6 = 3.5 Notably, you can't actually roll 3.5 on a 6-sided die, but that's the expected value anyways.

For an event with an symmetric distribution like a die roll (or any number of die rolls), the odds of getting the expected value or higher is >= 50%. (Specifically it's 50% + half the probability of rolling exactly the expected value)

If you're looking for a rule of thumb, reroll any dice below the die's expected value. Note that this only is a good rule of thumb for symmetric distributions. If you're playing a lottery where your winnings are 75% $0, 24% 10$ and 1% $1,000,000 then your expected value is $10,002.4, and this rule would indicate that you should reroll for anything under the jackpot - but if you're only playing the game once you're actually probably better off keeping a $10 win rather than gambling for the 1% chance.

There's an old saying that a bird in the hand is worth two in the bush. There's no rule of thumb to help you decide whether you should risk existing results for ones that are statistically better, but not guaranteed to be better. That will always depend on the game state.

The reverse is also possible, where the statistics aren't in your favor, but your current rewards aren't valuable enough to be worth keeping, so there is incentive to stretch into long odds.