// ////////////////////////////////////////////////////////
// # Title
// The Race
//
// # URL
// https://projecteuler.net/problem=232
// http://euler.stephan-brumme.com/232/
//
// # Problem
// Two players share an unbiased coin and take it in turns to play "The Race".
// On Player 1's turn, he tosses the coin once: if it comes up Heads, he scores one point; if it comes up Tails, he scores nothing.
// On Player 2's turn, she chooses a positive integer T and tosses the coin `T` times: if it comes up all Heads, she scores `2^{T-1}` points; otherwise, she scores nothing.
// Player 1 goes first. The winner is the first to 100 or more points.
//
// On each turn Player 2 selects the number, `T`, of coin tosses that maximises the probability of her winning.
//
// What is the probability that Player 2 wins?
//
// Give your answer rounded to eight decimal places in the form 0.abcdefgh .
//
// # Solved by
// Stephan Brumme
// July 2017
//
// # Algorithm
// My solution follows the standard Dynamic Programming pattern:
// the solution is found recursively with aggressive caching of partial results.
//
// The function ''twoWins'' considers only player 2's move. Its parameter is the number of remaining points:
// - if zero points left for player 2, then player 2 won
// - if zero points left for player 1, then player 1 won
// - in any other case, all possible moves of player 2 are analyzed and the best is chosen
//
// Each "round" consists of one turn of player 2 followed by one turn of player 1.
// There are four cases:
// 1. player 2 has all heads up, player 1 has heads up as well
// 2. player 2 has all heads up, player 1 has tails
// 3. player 2 has tosses tails at least once, player 1 has heads up
// 4. both players toss tails
//
// The probabilities of cases 1 to 3 are well defined (''win1'' and ''win2'').
// The only "tricky" case is case 4 where basically nothing changes.
//
// Since ''twoWins'' focuses on player 2, I have to manually play the first turn of player 1 in ''main'' and
// add the probabilities for both (equally likely) outcomes of player 1's first turn.
//
// # Note
// I was sure to have a correct solution but was rejected by the Project Euler website.
// A simple Monte-Carlo simulation told me that my result should be okay, too (considering a certain error margin).
// It took me quite some time to figure out that I have to switch the order of the first lines in ''twoWins'':
// check first whether player 2 won, only then check player 1. That was a nasty mistake.
#include
#include
#include
// the first player with 100 points wins
unsigned int maxScore = 100;
// fixed probabilities of player one
const double win1 = 0.5;
const double lose1 = 1 - win1; // = 0.5
// return chance of winning for player 2 when it's his/her turn
double twoWins(unsigned int needPointsOne, unsigned int needPointsTwo)
{
// player two won
if (needPointsTwo == 0)
return 1;
// player one won
if (needPointsOne == 0)
return 0;
// memoize
const double Unknown = -1;
static std::vector cache(maxScore * maxScore, Unknown);
auto id = (needPointsOne - 1) * maxScore + needPointsTwo - 1;
if (cache[id] != Unknown)
return cache[id];
// find highest chance of winning
double best = 0;
// current bet (observation: betting more than 2^3 = 8 never seems profitable)
unsigned int bet = 1;
while (true)
{
// probabilities
auto win2 = 0.5 / bet; // 2^(bet-1)
auto lose2 = 1 - win2;
// in case player two scores he shall not exceed the maximum score
auto nextPointsTwo = (needPointsTwo < bet) ? 0 : needPointsTwo - bet;
// at least one player scored a point
auto current = win1 * win2 * twoWins(needPointsOne - 1, nextPointsTwo) +
lose1 * win2 * twoWins(needPointsOne, nextPointsTwo) +
win1 * lose2 * twoWins(needPointsOne - 1, needPointsTwo);
// both players lost, stay in same state
current /= 1 - lose1 * lose2;
// better than before ?
if (best < current)
best = current;
// no use in further increasing the risk of player 2 ?
if (nextPointsTwo == 0)
break;
// twice the risk, twice the reward ...
bet *= 2;
}
cache[id] = best;
return best;
}
int main()
{
std::cin >> maxScore;
// player one moves first
// two options: he/she score one point or not
// => add both states (multiplied by their probability)
auto result = win1 * twoWins(maxScore - 1, maxScore) +
lose1 * twoWins(maxScore, maxScore);
std::cout << std::fixed << std::setprecision(8)
<< result << std::endl;
return 0;
}