betting.py

import random
from math import sqrt, floor

"""
Guessing game. When playing, the game picks a random value from i to j
and each time a guess g is made, g is added to the previous running cost
of playing this game.
"""
cache = {}
class Game:
  def __init__(self, i, j):
    self.i = i
    self.j = j

  """
  The expected cost of playing this game, calculated using a simulation.
  """
  def sim_cost(self, max_games=5000):
    return sum([self._play(strat=Game._random_guess) for _ in range(0, max_games)])/max_games
  
  """
  The expected cost of playing this game when each new guess is based on
  guessing the value between i and j such that the sum of values to the left
  of the guess is the same as the sum of values to the right of the guess.
  """
  def best_cost(self, max_games=5000):
    return sum([self._play(strat=Game._best_guess) for _ in range(0, max_games)])/max_games

  """
  The expected cost of playing the game, calculated using dynamic programming. 
  """
  def true_guess(self, max_games=5000):
    return sum([self._play(strat=Game._true_guess) for _ in range(0, max_games)])/max_games

  def _true_guess(i, j):
    if (i, j) in cache:
      return cache[(i, j)]
    elif i == j:
      return i
    elif i > j:
      return 0

    min_cost = j
    min_s = j
    n = j - (i - 1)
    for s in range(i, j):
      cost = s/n + (s-1-(i-1))/n*Game._true_guess(i, s-1) + (j-s)/n*Game._true_guess(s+1, j)
      if cost < min_cost:
        min_s = s
        min_cost = cost
    cache[(i, j)] = min_s
    return cache[(i, j)]

  def _random_guess(i, j):
    return random.randint(i, j)

  def _best_guess(i, j):
    return floor(sqrt((j**2+j+(i**2-i))/2))

  def _play(self, strat):
    k = random.randint(self.i, self.j)

    low = self.i
    high = self.j
    guess = strat(low, high)
    cost = guess

    while guess != k:
      if guess < k:
        low = guess + 1
      else:
        high = guess - 1
      guess = strat(low, high)
      cost += guess

    return cost


if __name__ == '__main__':
  game = Game(1, 100)
  print(game.sim_cost())
  print(game.best_cost())
  print(game.true_guess())