Skip to content

Instantly share code, notes, and snippets.

@sriprasanna
Created December 20, 2010 23:03
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save sriprasanna/749181 to your computer and use it in GitHub Desktop.
Save sriprasanna/749181 to your computer and use it in GitHub Desktop.
The Race - 232 Euler Project
@game = {}
@p1_success_probability = 1.to_f / 2
@p1_failure_probability = 1 - @p1_success_probability
def game(p1_points_to_win,p2_points_to_win)
return @game[[p1_points_to_win,p2_points_to_win]] if @game[[p1_points_to_win,p2_points_to_win]]
return 1 if p2_points_to_win <= 0
return 0 if p2_points_to_win > 0 and p1_points_to_win <= 0
strategies = [2]
while strategies.last < 2*p2_points_to_win
strategies << strategies.last * 2
end
probabilities = strategies.collect do |t|
p2_success_probability = 1.to_f / t
p2_failure_probability = 1 - p2_success_probability
p2_win_value = t / 2
p1_upperhand = @p1_success_probability * (p2_success_probability * game( p1_points_to_win-1, p2_points_to_win - p2_win_value ) + p2_failure_probability * game( p1_points_to_win-1, p2_points_to_win ))
p2_upplerhand = @p1_failure_probability * p2_success_probability * game( p1_points_to_win, p2_points_to_win - p2_win_value )
failure_factor = ( 1 - @p1_failure_probability * p2_failure_probability )
(p1_upperhand + p2_upplerhand) / failure_factor
end
@game[[p1_points_to_win,p2_points_to_win]] = probabilities.max
end
printf("%.8f", 0.5 * game(100,100) + 0.5 * game(99,100)) # => 0.83648556
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment