The Aaronson Oracle

The story

Two machines in a corridor at Bell Labs

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

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."²

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:

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

He knew exactly how to beat it

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:

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.

The two machines played each other

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

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

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

Fifty years later, in a lecture hall

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:

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.

Where our version departs

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.

How it works, in English

What just happened to you

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.

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.

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.

How it works, actually

Counting, and knowing when to stop

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 2⁵ = 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 of two is doing real work. Without it, a run seen a single time, a 1–0 count, would outrank a two-press context seen forty times as 30–10, purely because it was longer. That is the classic sparse-data failure, and it makes the model noisier than counting alone would be.

Aaronson described his original in almost these terms. Asked what the Berkeley program did, he replied:

Note the hedge, "there might have been." He is suggesting backoff, not recalling it. Our threshold and our backoff are our own choices, taken on his suggestion, and not a reconstruction of the program he ran in that lecture hall.

Read the machine

The entire program

Below is the predictor, in full. Not a summary of it, not a cleaned up version for the article, but the file this page loaded and ran while you were playing. It is a few dozen lines long, and its shortness is the lesson: this is all it takes.

Loading oracle.js…

Two functions. record writes one press into every context length at once; predict walks from the longest context to the shortest and returns the first one it trusts. There is no training phase, no parameters fitted in advance, no model of you beyond the tally it has built during this one session. It arrived knowing nothing.

What it says about us

Why you lost

A program this small should not be able to do this. It wins because of something about you, and that something has been measured for decades.

The task you were given, producing a sequence with no pattern in it, is called random sequence generation, and it is one of the more studied failures in experimental psychology. A 2023 review states the finding without hedging: "A common finding of RSG studies is that people are bad randomizers."⁷

The most reliable way people fail is the one Aaronson named in passing when he said players "have too many alternations." The same review calls it the alternation bias: "the avoidance of repetitions, also called negative recency effect or alternation bias, where an excess of alternations and suppression of repeating choices can be observed."⁷ Asked to be random, people switch too often and repeat too seldom. A fair coin produces a run of five identical flips more often than feels acceptable, and so people who are imitating a coin trim those runs away.

It goes deeper than switching too much. Analysing sequences people produced when asked to be random, one study concluded that they "avoid number repetitions and systematically deviate from mathematical randomness," and that the results "emphasize the idea of a complex hidden Markov rule system that underlies humanly generated random number sequences."⁸ That phrase is worth pausing on. A hidden rule system with memory is more or less exactly what an n-gram model is built to find. The oracle is not a general mind-reader; it is a device shaped to fit a specific defect, and the defect is real.

The bias also runs in the other direction. People not only produce too many alternations, they believe too many alternations look random: shown binary sequences to judge, participants rate the ones with the most switching as the most likely, with the peak somewhere around a 0.6 to 0.8 rate of alternation against a true value of 0.5.⁹ Sequences with more structure, HHHHH rather than HTTHT, are judged less probable.¹⁰ We generate wrongly and we grade wrongly, in the same direction.

The instruction itself hurt you

Here is the part that ought to bother you, and it is why the two experiments on this page are not equivalent. That 2023 review also reports: "if randomness is not overtly requested but rather an implicit requirement, as in competitive games such as matching pennies, randomness seems to be higher."⁷

Shannon's players were playing a game and trying to win. You were told to be random. The literature says the second framing is the worse one, and that consciously attempting randomness makes you more predictable than simply trying to beat an opponent. The instruction at the top of this page was, in a small way, working against you.

The rematch

Now that you know

You have read the source. You know it counts runs of up to five, that it needs to have seen a run twice before trusting it, that it never forgets, and that it falls back to a coin flip when it has nothing.

Play it again.

Most people do about as badly the second time, and the two people best placed to know said so first. Shannon, having published the exact method for beating his machine three-to-one, noted that it was "extremely difficult to carry out this program mentally." Aaronson, having written his, said flatly: "I couldn't even beat my own program, knowing exactly how it worked."

Knowing the algorithm gives you nothing, because the algorithm was never the hard part. The hard part is generating the sequence, and you are the one generating it, with the same machinery that produced the biases in the first place. Understanding a bias from the outside does not switch it off from the inside.

The reliable methods
all amount to the same move: take the decision out of your own head

If you do beat it, the interesting question is how. The reliable answers all have one thing in common: they take the decision out of your head. Poundstone, playing a modern implementation, found he did better when he stopped watching the score. "I found I did better when I tried to ignore the feedback, and better yet when I made sure I couldn't see the bars"⁴, and better again when he deliberately repeated choices his instincts wanted to alternate. Others read digits off something external, or run a rule in their head that is cheap to compute but hard to detect.

Which brings back Aaronson's student, the one the program predicted exactly 50% of the time and who said he "just used his free will." We have no record of what he actually did. But whatever it was, it was a method, a way of choosing that his own habits could not reach. That is not a smaller thing than free will. It is just a more useful description of it: not the absence of a cause, but the ability to hand the decision to something other than your reflexes.

The machine below is the same file, with the same rules, sealing its guess before every press.

References

Sources

Every factual claim above traces to one of these. Where an original was behind a paywall, the quotation is taken from a source that reproduces it, and that is said plainly.

1. Claude E. Shannon, "A Mind-Reading (?) Machine," Bell Laboratories Memorandum, 18 March 1953; reprinted in Claude Elwood Shannon: Collected Papers, IEEE Press, 1993, pp. 688–690. Full text (PDF).
2. D. W. Hagelbarger, "SEER, A SEquence Extrapolating Robot," IRE Transactions on Electronic Computers, EC-5(1), 1956, pp. 1–7. We could not obtain the original; both quotations here are reproduced from reference 3, which marks its quotations explicitly.
3. Macarie Breazu, Daniel Volovici, Daniel I. Morariu, Radu G. Crețulescu, "On Hagelbarger's and Shannon's matching pennies playing machines," International Journal of Advanced Statistics and IT&C for Economics and Life Sciences, 2020, pp. 56–66. PDF.
4. William Poundstone, "How I Beat the Mind-Reading Machine," 30 July 2015. Article.
5. Scott Aaronson, Quantum Computing Since Democritus, Cambridge University Press, 2013, Chapter 18 ("Free Will"). The passage also appears in the freely available lecture notes the book grew from: Lecture 18.
6. Scott Aaronson, personal communication to Nick Merrill, reproduced in the aaronson-oracle README. Not a published source. Repository. Aaronson links that implementation himself, and uses the name "the Aaronson Oracle," in his reply to Roger Penrose.
7. Maja Guseva, Carsten Bogler, Carsten Allefeld, John-Dylan Haynes, "Instruction effects on randomness in sequence generation," Frontiers in Psychology, 14:1113654, 2023. Open access.
8. Marc-Andre Schulz, Barbara Schmalbach, Peter Brugger, Karsten Witt, "Analysing humanly generated random number sequences: A pattern-based approach," PLOS ONE 7(7): e41531, 2012. Open access. Its headline prediction figures concern nine-option digit sequences, not two-key sequences, and are not quoted here.
9. Giorgio Gronchi, Marco Raglianti, Stefano Noventa, Alessandro Lazzeri, Andrea Guazzini, "Modeling the overalternating bias with an asymmetric entropy measure," Frontiers in Psychology, 7:1027, 2016. Open access. These figures describe how people judge sequences, not how they produce them.
10. Stian Reimers, Chris Donkin, Mike E. Le Pelley, "Perceptions of randomness in binary sequences: Normative, heuristic, or both?" Cognition, 172, 2018, pp. 11–25. DOI · accepted version (PDF).