Playing Guess Who with your kids: Code-word strategy against adversaries

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

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2024-11, Vol.1016, p.114766, Article 114766
Main Authors: Paz, Ami, Peterfreund, Liat
Format: Article
Language:English
Subjects:
Binary search
Computer Science
Distributed, Parallel, and Cluster Computing
Erasure codes
Error correcting codes
Guess Who?
Rényi-Ulam games
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2024.114766