HackerPapers

arXiv:1509.03327math.PR

Optimal Strategy in "Guess Who?": Beyond Binary Search

Mihai Nica

Abstract

"Guess Who?" is a popular two player game where players ask "Yes"/"No" questions to search for their opponent's secret identity from a pool of possible candidates. This is modeled as a simple stochastic game. Using this model, the optimal strategy is explicitly found. Contrary to popular belief, performing a binary search is \emph{not} always optimal. Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up. This is discovered by first analyzing a continuous version of the game where players play indefinitely and the winner is never decided after finitely many rounds.

arXiv comments
13 pages, 3 figures. Figures updated for the 10 year anniversary. Recorded narrative of how the result was found available at https://youtu.be/_3RNB8eOSx0
Journal reference
Prob. Eng. Inf. Sci. 30 (2016) 576-592
DOI
doi:10.1017/S026996481600022X
Subjects
math.PRProbability cs.GTComputer Science and Game Theory math.OCOptimization and Control

On Hacker News

Linked by 2 identifiable commenters in 2 comments across 2 threads, from Nov 2025 to Apr 2026.

Comments linking this paper, per year.

Discussed in comments2 threads

  1. You can beat the binary search 1 comment

    • I thought this would be about how you can beat binary search in the 'Guess Who?' game. There's a cool math paper about it [0] and an approachable video by the author. [1] [0] https://arxiv.org/abs/1509.03327 [1] https://www.youtube.com/watch?v=_3RNB8eOSx0

      gobdovanView on HNParent context

  2. I mathematically proved the best "Guess Who?" strategy [video] 1 comment

    • The idea is that if you're winning you can just do a binary search, but if you're losing, it's better to take some risks by making narrower guesses. For example, let's say it's the last turn and your opponent is about to win. Say you may have 2 options but your opponent has 4…

      abetuskView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.