Analysis of adversarial binary search game
possiblywrong.wordpress.com
possiblywrong.wordpress.com
The exact analysis for n=13 (instead of n=100) is presented--or rather, just the answer from the exhaustive search. The answer for n=100 is still unknown.
This is... exactly how the floor function is defined to behave!
The graphs would be much more enlightening if the artificial step function were removed. Instead of subtracting from floor(lg N), subtract from plain old lg N — or even don't subtract from anything at all, and just graph the number of guesses required.
The intent here is to reasonably compare hypothetical job interview questions for different N. If N=100, then Ballmer offers 6 dollars in exchange for one dollar per guess, and the linked Gukov article shows that Ballmer's expected return is negative.
What if he instead challenged an interview candidate with N=127? What about N=255, or N=511, etc.? He presumably wouldn't continue to offer only 6 dollars to play in these cases, but also presumably a similarly nice round number of dollars... and now the question/conjecture is interesting: from the updated graph, it looks like Ballmer's expected return decreases as N=2^k-1 increases, but does it always remain positive? Or is there some sufficiently large key space beyond which even an optimal guesser can't ever win on average?
To me, this question seems easier to ask when the expected return is presented in this way. That is, does each sawtooth interval always span zero expected return?
If I know the EV of 1 and 2 choices, then the 3 number situation is the same as whatever weight I assign to choosing the first number multipled by Ballmer's strategy multiplied by the EV of the 1 case when I pick 2, and the 2 case if I pick 1 or 3. Run this as a Counter Factual Regret minimization problem for each value from 3 through 100 with some sort of error threshold and you have a good enough answer.
I'm not 100% sure of that though. Perhaps there's a dependency in the two steps that confounds this approach?
Also I'd be keen to see a web ui where you can play against an ai. Not quite sure how the ai would work though. You don't necessarily want the ai to play optimally (if the optimal strategy were even known) because the fun is in working out how to exploit the other player's flaws.
Notably the size 13 case enumerated in the post, choosing 1 as the Chooser will always take 3 guesses (the most possible). Even in an iteration of a mixed strategy the Guesser will never guess 1 in fewer than 3. This is also true for 13.
And in a Chooser-always-chooses-1-or-13 strategy, the Guesser has a trivial strategy ("guess 1, then guess 13") that takes much less than 3 guesses on average.