Optimal Strategy in "Guess Who?"

Mihai Nica

Published 2015-09-08Version 1

"Guess Who?" is a popular two player game where players ask "Yes" or "No" questions to search for their opponent's secret identity from a pool of possible candidates. We model this as a simple stochastic game under the assumption that the opponent's secret identity is uniformly distributed. Using this model, we explicitly find the optimal strategy and prove it is optimal for both players and for all possible candidate pool sizes. Contrary to popular belief, performing a binary search is not the optimal strategy for both players. Instead, the optimal strategy for the player who trails is to make certain bold plays in an attempt catch up. We also find an interesting log-periodic behavior that naturally arises in the landscape of this game. The findings here can be used to balance the starting position of the game in order to offset first turn advantage.