Ulam's game

For Ulam's topological game where players alternate choosing binary digits, see binary game.

Ulam's game, or the Rényi–Ulam game, is a mathematical game similar to the popular game of twenty questions where one attempts to guess an unnamed object with yes-no questions, but where some of the answers may be wrong.[1] Alfréd Rényi (1961) introduced the game, though his paper was overlooked for many years. Rényi [69] reported the following story about the Jew Bar Kochba in 135 CE, who defended his fortress against the Romans. It is also said that Bar Kochba sent out a scout to the Roman camp who was captured and tortured, having his tongue cut out. He escaped from captivity and reported back to Bar Kochba, but being unable to talk, he could not tell in words what he had seen. Bar Kochba accordingly asked him questions which he could answer by nodding or shaking his head. Thus he acquired from his mute scout the information he needed to defend the fortress. It occurred to me that, if the story of Bar Kochba were true, then he would have been the forefather of information theory. Stanislaw Ulam (1976, p. 281) rediscovered the game, presenting the idea that there are a million objects and the answer to one question can be wrong. Pelc (2002) gave a survey of similar games and their relation to information theory.

References

  1. ↑ "How to Play Ulam's Game" (PDF). Retrieved 13 June 2013.
This article is issued from Wikipedia - version of the Friday, July 11, 2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.