The Aaronson Oracle

This experiment is seventy years old, and it was built out of relays before it was ever written as software.

c. 1951 Bell Telephone Laboratories Murray 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

EIGHT SITUATIONS, EIGHT COUNTERS, EACH STOPPING AT ±3

PlateSEER's whole memory. Three yes-or-no facts about the last two rounds give eight situations, and each situation keeps one small counter of whether playing the same has been working. The stops at plus and minus three are what Hagelbarger meant by making the machine forget ancient history.

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.

The machine is not unbeatable. It is beatable three times out of four, on paper. You simply cannot run the method in your head while playing. That gap, between what is possible in principle and what a person can actually do in the moment, is the entire subject of this page, and Shannon named it in 1953.

Inevitably, someone wondered which machine was better. Hagelbarger recorded what happened:

After much discussion an umpire machine was built which connected the two machines, and they were allowed to play several thousand games. The agility of the small machine triumphed, and it beat the larger one about 55-45.

HAGELBARGER SEER THE LARGER ONE

UMPIRE MACHINE

SHANNON THE SMALLER ONE

44.2 55.8

SEVERAL THOUSAND GAMES, 1950s · RECHECKED IN SOFTWARE, 2020

PlateThe two machines were wired to a third that refereed between them. The scores shown are from the 2020 software replication, averaged over games of a hundred plays; Hagelbarger's own report of the original match put it at about 55 to 45.3

Shannon's simpler machine, built with about half as many relays, beat the more elaborate one. In 2020 a group at Sibiu reimplemented both in software and played them against each other ten times. Averaged over games of a hundred plays, Shannon's won 55.8 to 44.2. A sixty-year-old piece of laboratory folklore, checked and confirmed.3

Player 3507 Machine 5010 the lifetime score on the exhibit

Shannon's machine still exists. William Poundstone went to see it at the MIT Museum's storage facility and did not play it, because "that would have been almost impious," he wrote, "for it recorded a final score: Player 3507. Machine 5010." Across every person who ever sat down with it, the machine won about 59% of the time. That is a lifetime tally on an exhibit rather than a controlled experiment, and it is the only machine-against-humans number that survives at all.4

The version you just played comes from Scott Aaronson, who wrote it for a class he taught at Berkeley and describes it in Quantum Computing Since Democritus:

I wrote a simple little program that would let people type either "f" or "d" and would predict which key they were going to push next. It's actually very easy to write a program that will make the right prediction about 70% of the time. Most people don't really know how to type randomly. They'll have too many alternations and so on. […] I couldn't even beat my own program, knowing exactly how it worked. I challenged people to try this and the program was getting between 70% and 80% prediction rates. Then, we found one student that the program predicted exactly 50% of the time. We asked him what his secret was and he responded that he "just used his free will."

Hold on to two things there. The first is that Aaronson could not beat his own program while knowing its source code, the same admission Shannon made about his relays. The second is the student, whom we will come back to at the end, because how he did it is the point rather than the exception.

Ours is not a copy of either machine. Shannon's tracked whether it was winning and whether you had changed your choice, giving it eight situations and no memory of your actual sequence. Ours ignores winning and losing entirely and simply counts what you pressed after each recent run of presses. Aaronson's used runs of five, and so does ours. His forgot nothing; Hagelbarger's deliberately forgot; ours also never forgets, so a habit you drop early keeps counting against you for the rest of the session.

There is no model of psychology in this program, and nothing about free will. It keeps a notebook.

Every time you press a key, it writes down what you had just pressed beforehand, and what you pressed next. Not once, but at six different lengths at the same time. Suppose your last five presses were F, D, D, F, F, and then you press D. The notebook gains six entries: after FDDFF you pressed D; after DDFF you pressed D; after DFF you pressed D; after FF you pressed D; after F you pressed D; and, ignoring context entirely, you pressed D.

SIX ENTRIES, WRITTEN AT ONCE

FDDFFDDFF DFFFF F

NO CONTEXT

→ D→ D → D→ D → D→ D

PlateOne press, six entries. The notebook records the same event at every context length at once, from the full run of five down to no context at all. Nothing else is stored: no timing, no history of who was winning, no model of you.

To guess your next press, it reads the notebook backwards. It takes your last five presses and asks: have I seen this exact run before, and if so, what did you do next? If it has seen that run at least twice and you did not do both things equally often, it answers with whichever you did more. If the run is new, or it has only seen it once, or you split evenly, then it shortens the question. What about the last four presses? The last three? Two? One? And if all of that fails, it flips a coin, and that coin flip counts against its score like any other guess.

That shortening is the only clever thing in the program, and it is worth understanding, because it is where most naive versions go wrong. A long run is a specific match: it tells you a lot when it applies. But early in a session you have not produced many five-press runs, so most of them have been seen exactly once, and a single observation is not evidence. It is a coincidence. A short run is vaguer but far better attested. The program prefers the longest run it has seen often enough to trust, and slides down to shorter, better-supported questions when the specific ones are thin.

That notebook is the drawing you have been playing against. The bands at the top of the page are the six questions the machine asks, stacked: your last five presses at the top, down to no context at all — every press you have ever made — at the bottom. Every grain in a band is one time you produced that run and then pressed something. Grains sit left of the centre line if you followed the run with D and right of it if you followed it with F. So how wide a band is says how much the machine knows, and how lopsided it is says what it knows.

The guess falls down the centre. A run it has never seen is an empty band and holds nothing. A run seen exactly once is a single grain, which is a coincidence rather than evidence. A run you followed with F exactly as often as with D is perfectly symmetrical, and the crack down its middle is open. The guess drops through every one of those and comes to rest on the first band that is neither empty, nor thin, nor even — then leans the way that band leans. That fall is backoff. It is the only clever thing in the program, and it happens in front of you on every single press.

Notice that the bands get wider as they get shallower, and that this is not a drawing decision. The top band asks about one exact run of five and has almost nothing in it; the bottom band counts every press you have ever made. Evidence thins as the question gets more specific, always, and that is the entire reason the machine has to be willing to give up on its best question and ask a worse one.

Notice what this means. The machine is not clever and it is not reading you. It is asking, over and over, one question: last time things looked like this, what did you do? Everything else on this page is a consequence of the fact that you keep answering.

The proper name for the notebook is an n-gram frequency model. An n-gram is just a run of n symbols. Here the symbols are your two keys, so there are 25 = 32 possible runs of five, 16 of four, and so on down to the empty run, which is the count of every press you have ever made.

Write c for a run of presses, called the context, and N(c, F) for the number of times you pressed F immediately after that run. The prediction rule is: take the longest context c matching your recent presses such that

N(c, F) + N(c, D) ≥ 2 and N(c, F) ≠ N(c, D),

and answer with whichever of F or D is larger. If no context qualifies, answer at random. Dropping to a shorter context when a longer one is unavailable or unreliable is called backoff, and it is standard practice in statistical language modelling, where the same problem appears: specific evidence is better, but specific evidence is rare.

Backoff prefer the longest run you have seen often enough to trust

The threshold