Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-28T16:07:23.441Z Has data issue: false hasContentIssue false
  • English
  • Français

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

Published online by Cambridge University Press:  28 June 2016

Mihai Nica
Mihai Nica*
Affiliation:
Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY 10012-1185, USA E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 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.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 30 , Issue 4 , October 2016 , pp. 576 - 592
Copyright
Copyright © Cambridge University Press 2016 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Chen, M.-R. & Hsiau, S.-R. (2010). Two new models for the two-person red-and-black game. Journal of Applied Probability 47: 97–108.Google Scholar
2. Condon, A. (1992). The complexity of stochastic games. Information and Computation 96: 203–224.Google Scholar
3. Dubins, L.E. & Savage, L.J. (1965). How to Gamble If You Must: Inequalities for Stochastic Processes. New York, NY, USA: McGraw-Hill New York, Inc.Google Scholar
4. Eisenberg, B., Stengle, G., & Strang, G. (1993). The asymptotic probability of a tie for first place. Annals of Applied Probability 3: 731–745.Google Scholar
5. Haigh, J. & Roters, M. (2000). Optimal strategy in a dice game. Journal of Applied Probability 37: 1110–1116.Google Scholar
6. Neller, T. & Presser, C. (2010). Practical play of the dice game pig. The UMAP Journal 31: 5–19.Google Scholar
7. Pontiggia, L. (2005). Two-person red-and-black with bet-dependent win probabilities. Advances in Applied Probability 37: 75–89.Google Scholar
8. Secchi, P. (1997). Two-person red-and-black stochastic games. Journals of Applied Probability 34: 107–126.Google Scholar
9. Shapley, L.S. (1953). Stochastic games. Proceedings of the National Academy of Sciences of the United States of America 39: 1095–1100.Google Scholar
10. Tijms, H. & van der Wal, J. (2006). A real-world stochastic two-person game. Probability in the Engineering and Informational Sciences 20: 599–608.Google Scholar
11. van de Brug, T., Kager, W., & Meester, R. (2015). The Asymptotics of Group Russian Roulette. arXiv 1507.03805. Preprint. http://arxiv.org/abs/1507.03805 Google Scholar
12. Wikipedia (2015). Guess Who? — Wikipedia, the free encyclopedia. http://en.wikipedia.org/w/index.php?title=Guess%20Who%3F Google Scholar