A 70-year-old idea still beats people at being random: the Aaronson Oracle guesses your next keypress

A small program can guess which key you will press next, F or D, and it is right far more often than a coin flip would be. It does this by keeping a count of what you did after each short run of presses.

The idea is older than software. Around 1951, at Bell Telephone Laboratories in Murray Hill, New Jersey, an engineer named David Hagelbarger built a machine to play matching pennies against colleagues. In that game, two players secretly pick heads or tails. One wins if the picks match, the other if they differ. Hagelbarger called his machine SEER, short for SEquence Extrapolating Robot.

SEER looked at only a few facts about the last two rounds. Those were 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. That gives eight possible situations. For each one, the machine kept a small counter showing whether playing the same had been working. The counter stopped at plus and minus three, which Hagelbarger said made the machine "forget ancient history."

Claude Shannon, who worked down the hall, built a simpler version. His memo of 18 March 1953 credits Hagelbarger and says the machine is aimed more at Edgar Allan Poe's method of play than at the game theory of von Neumann and Morgenstern. Game theory says the right way to play is to be truly random. Poe's detective instead studies his opponent. Shannon's machine did the second thing.

Shannon's machine looked for patterns and assumed the player would repeat them in the same situation. If it had not seen a pattern at least twice, it moved at random. It got that randomness from a commutator, a spinning part, sampled at the moment the player pressed the button.

Shannon was open about its weakness. His analysis showed the machine could be beaten by the best possible play in a ratio of 3:1. But that would mean tracking every memory cell in the machine, which he called extremely difficult to do in your head.

The two machines were also played against each other, through a third machine acting as umpire. Hagelbarger reported that the smaller machine, Shannon's, won about 55 to 45 over several thousand games. In 2020, a group at Sibiu rebuilt both in software and played them ten times. Averaged over games of a hundred plays, Shannon's won 55.8 to 44.2.

Shannon's machine still exists. William Poundstone went to see it in the MIT Museum's storage facility. The exhibit's lifetime score read Player 3507, Machine 5010, so the machine won about 59% of the time. That is a running tally on an exhibit, not a controlled experiment.

The version on this page comes from Scott Aaronson, who wrote a similar program for a class at Berkeley. In his book Quantum Computing Since Democritus, he says it predicted people's keys 70% to 80% of the time. He also says he could not beat his own program even though he knew exactly how it worked. One student was predicted only 50% of the time. Asked his secret, the student said he "just used his free will."

The program does not model your mind. It keeps a notebook. Each time you press a key, it records what came next after your last five presses, your last four, and so on down to no context at all. That is six entries per press. Programmers call this an n-gram model, where an n-gram is just a run of n symbols.

To guess, it takes your last five presses and checks whether it has seen that exact run at least twice, with one next key more common than the other. If so, it picks the more common key. If not, it drops to the last four presses, then three, and so on. If nothing qualifies, it flips a coin, and that guess counts against its score. This step is called backoff. It matters because a run seen only once is a coincidence, not evidence.

The page prints the whole predictor, 52 lines of JavaScript, and says it is the same file the page runs. The code has two functions. One records each press at every context length, and the other walks from the longest context to the shortest and returns the first one it trusts. There is no training phase. It starts knowing nothing.

The page's version differs from the old machines. It ignores winning and losing and counts only what you pressed. It uses runs of up to five presses, which gives 63 situations. It never forgets, so a habit you drop early keeps counting against you. The page notes that the details of its threshold and backoff are its own choices, and not a reconstruction of Aaronson's original program.

The reason it works is that people are poor at being random. A 2023 review the page cites says it plainly: "A common finding of RSG studies is that people are bad randomizers." RSG means random sequence generation. The most common error is alternation bias. People switch too often and repeat too seldom, trimming away the long runs a real coin would produce.

The bias also affects judgment. When people are shown binary sequences, they rate those with the most switching as most likely to be random. The peak is around a 0.6 to 0.8 rate of alternation, while a fair coin alternates at 0.5. We produce and judge randomness wrongly, in the same direction.

The page also points to a catch in how the task is framed. The same review says randomness seems to be higher when it is only an implicit requirement, as in competitive games like matching pennies. So being told to be random may make you easier to predict than simply trying to beat an opponent.

Knowing how the machine works does not seem to help much. Shannon said his method was too hard to run mentally, and Aaronson said he could not beat his own program. The page offers a rematch with the same predictor, now that you have read the code.

What does help, the page says, is taking the decision out of your own head. Poundstone, playing a modern implementation, said he did better when he ignored the feedback, and better still when he could not see the bars. He also did better when he deliberately repeated choices his instincts wanted to alternate. The page says others read digits off something external or run a simple rule in their heads. It adds that nobody knows what Aaronson's 50% student actually did.