Analysis of adversarial binary search game
The analysis of a guessing game between Alice and Bob reveals optimal strategies for both players, emphasizing Alice's random number selection and Bob's complex guessing methods, influencing game outcomes significantly.
Read original article
The analysis discusses a game between Alice and Bob, where Alice selects a secret integer and Bob attempts to guess it, paying Alice for each guess. The game is inspired by a similar scenario used in job interviews, notably by Steve Ballmer. The strategic dynamics of the game are explored, particularly how Alice can choose her number adversarially, potentially giving her an advantage. The author employs Mathematica to compute optimal strategies for both players, revealing that Alice's best approach is to select numbers almost uniformly at random, favoring edge values. Bob's optimal strategy is more complex, involving a mix of various guessing strategies, with a significant probability assigned to starting with the midpoint guess. The expected returns for Alice are analyzed, suggesting that predicting her financial outcome is challenging due to the game's complexity. The findings indicate that both players can employ strategies that significantly influence the game's outcome, making it a rich area for further exploration in game theory.
- Alice's optimal strategy involves selecting numbers almost uniformly at random, with a bias towards edge values.
- Bob's strategy is complex, utilizing a mix of guessing methods, primarily starting with the midpoint.
- The game dynamics allow for significant strategic advantages for both players.
- Predicting Alice's expected returns is complicated due to the game's inherent complexity.
- The analysis highlights the interplay of strategy and randomness in adversarial games.
Related
Professional Poker Players Know the Optimal Strategy but Don't Always Use It
Professional poker players balance game theory optimal strategies with exploitative play to outsmart opponents. AI advancements challenge traditional approaches, pushing players to blend defensive and aggressive tactics for competitive success in evolving poker dynamics.
How to Cheat with Math – The Russian Cards Problem
The Russian Cards Problem is a logical puzzle where Alice and Bob communicate their card hands without revealing information to Eve, relying on mutual knowledge and strategic statements to succeed.
Perplexing the Web, One Probability Puzzle at a Time
Mathematician Daniel Litt's engaging probability puzzles reveal misconceptions in mathematical intuition, with only 22% answering correctly. His work fosters discussions and insights among mathematicians and enthusiasts, promoting a supportive online community.
Steve Ballmer's incorrect binary search interview question
Steve Ballmer's interview question about a guessing game has been criticized for miscalculating expected value. Analysis shows the game's expected value is positive, highlighting the importance of accurate calculations in game theory.
The expected value of the game is positive regardless of Ballmer’s strategy
Steve Ballmer's number guessing game has a negative expected value, but John Graham-Cumming argues it can be positive with random choices. A mixed strategy can improve outcomes, yielding average wins of $0.12 and $0.07.
7 commentsThe 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.
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.
Related
Professional Poker Players Know the Optimal Strategy but Don't Always Use It
Professional poker players balance game theory optimal strategies with exploitative play to outsmart opponents. AI advancements challenge traditional approaches, pushing players to blend defensive and aggressive tactics for competitive success in evolving poker dynamics.
How to Cheat with Math – The Russian Cards Problem
The Russian Cards Problem is a logical puzzle where Alice and Bob communicate their card hands without revealing information to Eve, relying on mutual knowledge and strategic statements to succeed.
Perplexing the Web, One Probability Puzzle at a Time
Mathematician Daniel Litt's engaging probability puzzles reveal misconceptions in mathematical intuition, with only 22% answering correctly. His work fosters discussions and insights among mathematicians and enthusiasts, promoting a supportive online community.
Steve Ballmer's incorrect binary search interview question
Steve Ballmer's interview question about a guessing game has been criticized for miscalculating expected value. Analysis shows the game's expected value is positive, highlighting the importance of accurate calculations in game theory.
The expected value of the game is positive regardless of Ballmer’s strategy
Steve Ballmer's number guessing game has a negative expected value, but John Graham-Cumming argues it can be positive with random choices. A mixed strategy can improve outcomes, yielding average wins of $0.12 and $0.07.