Random Ballmer

def choose_random_optimal(n_min, n_max):

    n_guesses_left = math.ceil(math.log2(n_max - n_min + 2))

    guess_min = max(n_max-2**(n_guesses_left-1)+1, n_min-1+2**(n_guesses_left-2))
    guess_max = min(n_min-1+2**(n_guesses_left-1), n_max-2**(n_guesses_left-2)+1)

    return np.random.randint(guess_min, guess_max+1)

def choose_random_suboptimal(n_min, n_max):
    n_guesses_left = math.ceil(math.log2(n_max - n_min + 2))

    guess_min = max(n_max-2**(n_guesses_left-1)+1, n_min-1+2**(n_guesses_left-2))
    guess_max = min(n_min-1+2**(n_guesses_left-1), n_max-2**(n_guesses_left-2)+1)

    n_extra = (n_max - n_min) - (guess_max - guess_min)

    if np.random.uniform() > 0.99**n_extra:
        guess = np.random.randint(n_extra) + n_min
        if guess >= guess_min:
            guess+=guess_max-guess_min+1
        return guess

    else:
        return np.random.randint(guess_min, guess_max+1)

def prepare_strategies(n):
    named_strategies = {}

    named_strategies.update({f'random optimal {np.random.randint(1e9)}':
                             predict_wins_binsearch(n, choose_random_optimal(0,99), choose_random_optimal) for x in range(10000)})
    named_strategies.update({f'random suboptimal{np.random.randint(1e9)}':
                             predict_wins_binsearch(n, choose_random_suboptimal(0,99), choose_random_suboptimal) for x in range(10000)})

    strategy_names = {}
    strategies = []
    for name, wins in named_strategies.items():
        strategy_names[tuple(wins)] = name
        strategies.append(wins)

    return strategies, strategy_names