Document Open Access Logo

Playing Guess Who with Your Kids

Authors Ami Paz, Liat Peterfreund

PDF
Thumbnail PDF

File

LIPIcs.FUN.2022.23.pdf
  • Filesize: 0.88 MB
  • 10 pages

Document Identifiers

Author Details

Ami Paz
  • LISN, CNRS & Paris Saclay University, France
Liat Peterfreund
  • LIGM, CNRS & Gustav Eiffel University, Champs-sur-Marne, France

Acknowledgements

The authors are grateful to Yonatan, Yuval and Ari for inspiring this work, and to Ben Lee Volk for discussions on error correcting codes.

Cite AsGet BibTex

Ami Paz and Liat Peterfreund. Playing Guess Who with Your Kids. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 23:1-23:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.FUN.2022.23

Abstract

Guess who is a two-player search game in which each player chooses a character from a deck of 24 cards, and has to infer the other player’s character by asking yes-no questions. A simple binary search strategy allows the starting player find the opponent’s character by asking 5 questions only, when the opponent is honest. Real-life observations show that in more realistic scenarios, the game is played against adversaries that do not strictly follow the rules, e.g., kids. Such players might decide to answer all questions at once, answer only part of the questions as they do not know the answers to all, and even lie occasionally. We devise strategies for such scenarios using techniques from error-correcting and erasure codes. This connects to a recent line of work on search problems on graphs and trees with unreliable auxiliary information, and could be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Representations of games and their complexity
  • Theory of computation → Sorting and searching
  • Theory of computation → Theory and algorithms for application domains
Keywords
  • Guess Who?
  • Binary Search
  • Error Correcting Codes
  • Erasure Codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aaron Berger, Christopher Chute, and Matthew Stone. Query complexity of mastermind variants. Discret. Math., 341(3):665-671, 2018. Google Scholar
  2. Lotte Berghman, Dries R. Goossens, and Roel Leus. Efficient solutions for mastermind using genetic algorithms. Comput. Oper. Res., 36:1880-1885, 2009. Google Scholar
  3. Lucas Boczkowski, Uriel Feige, Amos Korman, and Yoav Rodeh. Navigating in trees with permanently noisy advice. ACM Trans. Algorithms, 17(2):15:1-15:27, 2021. Google Scholar
  4. Marco Console, Paolo Guagliardo, and Leonid Libkin. On querying incomplete information in databases under bag semantics. In IJCAI, volume 17, pages 993-999, 2017. Google Scholar
  5. Carlos Cotta, Juan Julián Merelo Guervós, Antonio Mora García, and Thomas Philip Runarsson. Entropy-driven evolutionary approaches to the mastermind problem. In PPSN, 2010. Google Scholar
  6. Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran. The entropy of lies: Playing twenty questions with a liar. In ITCS, volume 185 of LIPIcs, pages 1:1-1:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. Google Scholar
  7. Claire David, Leonid Libkin, and Filip Murlak. Certain answers for xml queries. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 191-202, 2010. Google Scholar
  8. Dariusz Dereniowski, Daniel Graf, Stefan Tiegel, and Przemyslaw Uzna'nski. A framework for searching in graphs in the presence of errors. In SOSA, 2019. Google Scholar
  9. Julien Gagneur, Markus C. Elze, and Achim Tresch. Selective phenotyping, entropy reduction, and the mastermind game. BMC Bioinformatics, 12:406-406, 2011. Google Scholar
  10. Juan Julián Merelo Guervós, Pedro A. Castillo, Antonio Mora García, and Anna I. Esparcia-Alcázar. Improving evolutionary solutions to the game of mastermind using an entropy-based scoring method. In GECCO '13, 2013. Google Scholar
  11. Juan Julián Merelo Guervós, Antonio Mora García, Pedro A. Castillo, Carlos Cotta, and Mario García Valdez. A search for scalable evolutionary solutions to the game of mastermind. 2013 IEEE Congress on Evolutionary Computation, pages 2298-2305, 2013. Google Scholar
  12. Nicolas Hanusse, David Ilcinkas, Adrian Kosowski, and Nicolas Nisse. Locating a target with an agent guided by unreliable local advice: how to beat the random walk when you have a clock? Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing, 2010. Google Scholar
  13. Nicolas Hanusse, Evangelos Kranakis, and Danny Krizanc. Searching with mobile agents in networks with liars. In Euro-Par, 2000. Google Scholar
  14. Tomasz Imieliński and Witold Lipski Jr. Incomplete information in relational databases. In Readings in Artificial Intelligence and Databases, pages 342-360. Elsevier, 1989. Google Scholar
  15. Donald Ervin Knuth. The computer as master mind. Journal of Recreational Mathematics, 9:1-6, 1977. Google Scholar
  16. Witold Lipski Jr. On databases with incomplete information. Journal of the ACM, 28(1):41-70, 1981. Google Scholar
  17. Florence Jessie MacWilliams and Neil James Alexander Sloane. The theory of error correcting codes, volume 16. Elsevier, 1977. Google Scholar
  18. Mihai Nica. Optimal strategy in “guess who?”: Beyond binary search. Probability in the Engineering and Informational Sciences, 30(4):576-592, 2016. URL: https://doi.org/10.1017/S026996481600022X.
  19. Riccardo Rosati. On the decidability and finite controllability of query processing in databases with incomplete information. In Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 356-365, 2006. Google Scholar
  20. Ron Roth. Introduction to Coding Theory. Cambridge University Press, 2006. URL: https://doi.org/10.1017/CBO9780511808968.
  21. Geoffroy Ville. An optimal mastermind (4,7) strategy and more results in the expected case. ArXiv, abs/1305.1010, 2013. Google Scholar
  22. Jef Wijsen. On the first-order expressibility of computing certain answers to conjunctive queries over uncertain databases. In Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 179-190, 2010. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact