The Aaronson Oracle

Gelişmenin Ayrıntıları ve Kapsamı

c. 1951Bell Telephone LaboratoriesMurray Hill, New Jersey

Some time in the early 1950s, at Bell Laboratories, an engineer named David Hagelbarger built a machine to play matching pennies against his colleagues. Two players each choose heads or tails in secret; one wins if the choices match, the other if they differ. Played against someone truly unpredictable, it is a coin flip and nothing more. Hagelbarger called his machine SEER, for SEquence Extrapolating Robot.2

SEER did not model you in any deep way. It tracked three facts about the last two rounds: whether it had won or lost the play before last, whether it had played the same or differently, and whether it had won or lost the last play. Three yes-or-no facts give eight possible situations, and for each of the eight the machine remembered whether playing the same had been working. It counted that on a small reversible counter that stopped at plus and minus three, which Hagelbarger described with a phrase worth keeping: the stops "in effect make the machine forget ancient history."2

Claude Shannon, who worked down the hall, took note and built his own. His memorandum of 18 March 1953 opens by giving Hagelbarger the credit plainly, and then makes a comparison that tells you exactly what kind of machine this is:

This machine is a somewhat simplified model of a machine designed by D. W. Hagelbarger. It plays what is essentially the old game of matching pennies or "odds and evens." This game has been discussed from the game theoretic angle by von Neumann and Morgenstern, and from the psychological point of view by Edgar Allen Poe in the "The Purloined Letter." Oddly enough, the machine is aimed more nearly at Poe's method of play than von Neumann's.

That is the whole idea in one sentence. Game theory tells you the correct way to play matching pennies: flip a mental coin, be genuinely random, and no opponent can beat you over time. Poe's detective does something else entirely. He studies his opponent and guesses what sort of person would choose what. Shannon built the detective, because the detective wins. Not against an ideal player. Against an actual one.

Shannon's machine looked for patterns and, in his words, "assumes that the player will follow the patterns the next time the same situation arises." When it had not seen a pattern repeat at least twice, it moved at random, and the randomness came from a commutator spinning about ten times a second, sampled at the moment you pressed the button. Its unpredictability was harvested from the jitter in your own timing.1

What makes Shannon's memo remarkable is that he did not oversell it. He worked out how beatable the machine was and published the method:

A mathematical analysis of the strategy used in this machine shows that it can be beaten by the best possible play in the ratio 3:1. To do this it is necessary to keep track of the contents of all the memory cells in the machine. […] It is extremely difficult to carry out this program mentally because of the amount of memory and calculation necessary.

Recep Usta OS — Sistem & Mühendislik Değerlendirmesi