Continuing the discussion from LC without cluttering that thread.
Here’s some python code I wrote to try to get an exact solution:
def probability_equals(result, sides, max_reroll):
second_roll_chance = (max_reroll / sides) * (1 / sides)
if result <= max_reroll:
return second_roll_chance
else:
return second_roll_chance + (1 / sides)
def probability_above(result, sides, max_reroll):
inverse_probability = 0
for i in range(1, result + 1):
inverse_probability += probability_equals(i, sides, max_reroll)
return 1 - inverse_probability
def expected_win(sides, own_max_reroll, opponent_max_reroll):
frequency = 0
for result in range(1, sides + 1):
weight = probability_equals(result, sides, opponent_max_reroll)
conditional_win = probability_above(result, sides, own_max_reroll)
frequency += weight * conditional_win
return frequency
def best_response(sides, opponent_max_reroll):
best_own_reroll = 0
best_expected_win = 0
for own_max_reroll in range(0, sides+1):
win = expected_win(sides, own_max_reroll, opponent_max_reroll)
if win > best_expected_win:
best_expected_win = win
best_own_reroll = own_max_reroll
return best_own_reroll
The best_response() function finds the maximum re-roll value that has the highest expected win rate against an opponent’s fixed maximum re-roll value.
Some interesting results here:
The best response to 61 is 62, but the best response to 62 is 61. This suggests that the real optimal strategy is a mixed strategy that involves re-rolling some fraction of the time on 61 (or possibly on 62).
My results seem a little different from Fabian’s. That’s probably due to my treatment of ties. I’m treating the payoff to winning as 1 and the payoff to tying and losing as 0.
Oh dang I should click LC more often. I found the original post describing the problem:
Can any maths nerd help solve an argument? Imagine a game where 2 people roll a D100 and independently choose (without knowledge what the other is doing) whether to keep their roll or reroll it. After the choice the highest number wins.
So the basic strat seems to be reroll 50 or less and stick on 51+ because you are expected to hit a lower roll if you reroll 51. But it doesn’t matter how much you lose by and you know your opponent is likely rerolling 50 or less and keeping 51+ so their average number is going to be higher than 50 (right?)
Should you maximise score EV or go for the win with more extreme variance?
I might get a chance to try it Monday if it’s not a closed case by then.
Can any maths nerd help solve an argument? Imagine a game where 2 people roll a D100 and independently choose (without knowledge what the other is doing) whether to keep their roll or reroll it. After the choice the highest number wins.
So the basic strat seems to be reroll 50 or less and stick on 51+ because you are expected to hit a lower roll if you reroll 51. But it doesn’t matter how much you lose by and you know your opponent is likely rerolling 50 or less and keeping 51+ so their average number is going to be higher than 50 (right?)
Should you maximise score EV or go for the win with more extreme variance?
Without thinking about it, my gut is that your re-roll threshold should be higher because you opponent has two chances to roll above 50. But it’s probably not that much higher.
If your opponent keeps 51+, then half of the time, they have an average value of 75.5 and the other half 50.5, so their average number should be 63.
Since margin of victory doesn’t matter, you need to beat his median rather than mean score, which means, I think, you need to target 67 or higher. If you reroll 66 and under, I think you win about 56% of the time.
Ancillary question, does your strategy change if you and your opponent can have say 5 rerolls max? Or still sticking at 51+? Each roll is an independent event right so it shouldn’t matter but it feels wrong to take 51 on the first roll.
I’m pretty sure this is wrong because you’re opponent doesn’t have a uniform distribution.
The poker analogy is that against a polarized range of bluffs and strong hands, you want the hands with the best blockers to strong hands rather than the highest possible hand to bluff catch with.
I think rugby was right and I think I solved it by calculating the expectation, taking the derivative and solving for zero to find the maximum. I think.
I am pretty confident that 51 is only right for your 4th roll if you can roll 5 times as the solution needs to converge to only stopping at 100 when you have a million rolls left.
the python
