A computer scientist plays Twenty Questions June 12, 2012Posted by Ezra Resnick in Computer science, Game theory.
“Would you like to play Twenty Questions?”
“Sure, how do we play?”
“I think of a famous person — alive or dead, real or fictional — and you have to guess who it is, in no more than twenty yes-or-no questions.”
“Well… I could use binary search to identify a single letter of the alphabet in 4.7 yes-or-no questions (on average), so nineteen questions should allow me to identify four letters. Why don’t you just tell me the first four letters of your person’s last name, and I’ll guess who it is.”
“Actually, I don’t think I want to play any more.”
“That’s OK — the game is flawed, anyway: it assumes there are no more than 1,048,576 famous people to choose from…”