OPTIMAL STRATEGY IN “GUESS WHO?”: BEYOND BINARY SEARCH

DOI10.1017/S026996481600022XMaRDI QIDQ5358097zbMATH OpenFDO

Authors

Publication date 19 September 2017

Published in Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.03327

zbMATH Keywords

stochastic gametwo-player gameoptimal search strategy

Mathematics Subject Classification ID

Searching and sorting (68P10) Software, source code, etc. for problems pertaining to game theory, economics, and finance (91-04) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Probabilistic games; gambling (91A60)

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.

Recommendations

• On the optimal strategy in a random game
• Optimal strategies for a model of combinatorial two-sided search
• Optimal Search on Some Game Trees
• Optimal comparison strategies in Ulam's searching game with two errors
• Optimal strategies for random tournament games
• Optimal guessing: choice in complex environments
• scientific article; zbMATH DE number 4179170
• Finding Optimal Strategies of Almost Acyclic Simple Stochastic Games
• Optimal Strategies for a Generalized "Scissors, Paper, and Stone" Game
• Optimal strategy in games with chance nodes

Cites work

• scientific article; zbMATH DE number 3216771 (Why is no real title available?)
• A REAL-WORLD STOCHASTIC TWO-PERSON GAME
• Optimal strategy in a dice game
• Stochastic Games
• The asymptotic probability of a tie for first place
• The asymptotics of group Russian roulette
• The complexity of stochastic games
• Two new models for the two-person red-and-black game
• Two-person red-and-black stochastic games
• Two-person red-and-black with bet-dependent win probabilities

Cited in

(2)

• Playing Guess Who with your kids: code-word strategy against adversaries
• Optimal comparison strategies in Ulam's searching game with two errors

This page was built for publication: OPTIMAL STRATEGY IN “GUESS WHO?”: BEYOND BINARY SEARCH

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5358097)