I'm reading "Rock Breaks Scissors", which describes two "outguessing machines" built at Bell Labs that try to exploit human non-randomness in the game of matching pennies. There was an outguessing machine built by the famous Claude Shannon, and one built by Dave Hagelbarger.
The machines worked like this (quoted from the book):
Suppose you win twice in a row with the same choice. What would you
pick next? You could stick with the choice that's been winning – or
you could switch, perhaps on the grounds that three times in a row
wouldn't be "random."Each time a particular situation occurred, [Shannon's] machine
archived what the player had decided. Every decision was encoded as a
1 or 0 and slotted into one of the machine's 16 precious bits of
memory. For each of the eight given situations, Shannon's machine
cataloged the last two decisions only. That filled the machine's 16
bits.When the machine needed to predict, it looked at what the player had
done the last two times that the same situation had occurred. Whenever
the player's response had been identical both times, the machine
predicted that the player would do the same thing once again.
Otherwise, it guessed randomly from its [random number generator].The main difference between Shannon's machine and Hagelbarger's was
that Shannon's was simpler. Hagelbarger's machine kept track of a
percentage of outcomes for each of the eight situations. The higher
the percentage, the more likely Hagelbarger's machine was to predict a
repeat of the past. This may sound more reasonable and nuanced than
Shannon's all-or-nothing approach, but in practice, Shannon's device
was the better predictor.
Shannon's machine beat humans at a higher rate than Hagelbarger's, and also beat Hagelbarger's machine when they played each other. I don't understand why Shannon's simpler approach was significantly better than Hagelbarger's percentage-based approach.
Best Answer
Why did algorithm S do better at beating humans than algorithm H? Because S was a better model of human behaviour. The obvious difference is that S (Shannon) had a short memory and H (Hagelbarger) had one that was longer. We can hypothesise that humans play this game with more short term than long term consistency. Obviously to check our hypothesis will require more experiments.
Why did algorithm S beat algorithm H? Because it could and it did.
For a game such as this which is fair and for which there is no simple Nash equilibrium, then any algorithm with deterministic features (such as H) can be beaten by another algorithm designed specifically for that purpose. [Shannon acknowledges as much in that reference.] I surmise that S by chance was such an algorithm.
If there exists a full specification of each algorithm it would now be trivial to code the simulation and run a few billion trials to see if the result was inherent in the algorithm, or occurred by chance.