euler-0232.cpp

// ////////////////////////////////////////////////////////
// # 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 <iostream>
#include <iomanip>
#include <vector>

// 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<double> 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;
}