The whole premise of the
Rock, Scissors, Paper program is that a human player
does not generate a truly random sequence of choices, but tends to fall into
certain patterns that are repeated over time. The program looks for these
patterns and makes its choices accordingly.
The Rock, Scissors, Paper
algorithm keeps statistics on how often the player has made each possible four
choice sequence. (There are 81 possible four choice sequences: 34 =
81.) The program makes its choice by looking at the number of previous
occurrences of each of the three possible four-choice sequences, given the
player’s last three choices. These three numbers of occurrences, normalized,
are taken to be the probabilities of the player’s next choice. The program then
makes a pseudo-random choice weighted by these probabilities but shifted so the
computer choice will beat the expected player choice.
To be more specific, the four
latest player choices are kept in a four-position shift register. The shift
register is updated each time the player makes a choice, the contents of the
shift register are converted to an address in an 81 place statistics register,
and the value at that address is incremented. Over time, the number stored in
an address indicates how often the player has chosen the corresponding four
choice sequence. To make its choice, the program
extrapolates by regarding the player’s last three choices as the first three
choices of a four choice sequence. It then looks in the three addresses that
would be given if the next choice were Rock,
Scissors, or Paper. The values at these three addresses indicate how often the
player has chosen Rock, Scissors, or Paper in the past, given the previous three choices. These values
are each divided by their sum to normalize them to probabilities, call them pR, pS, and pP
with pR + pS + pP = 1. The program then selects a pseudo-random number, n,
from a population uniformly distributed between 0 and 1. If n < pR, the program assumes the player’s next choice will be Rock. If pR
< n < pR + pS, the
next choice is assumed to be Scissors.
If pR + pS < n, the next
choice is assumed to be Paper. If the
assumed next choice of the player is Rock,
the program will choose Paper. If it
is Scissors, the program will choose Rock, and if it is Paper, the program will choose Scissors.
A concrete example: The last
four plays were RPSP. The program increments the value at
address RPSP. To make the next program choice, the values at PSPR, PSPS,
and PSPP are retrieved. Assume them to be 4, 7, 2. The
probabilities that the player’s next choice will be R, S, P
are taken to be 4/13, 7/13, 2/13. Now a pseudo-random number is generated.
Assume it to be 0.634. Since it lies between 4/13 and 11/13, the program
assumes that the player’s next guess will be Scissors, so it chooses Rock
(Rock breaks Scissors).
Doubtless there are other
algorithms that would work as well or better than this. For instance, this
algorithm ignores whether the player wins or loses, while it seems likely that
a player’s choices will be influenced by winning or losing. Nevertheless,
in limited testing, the method given here results in the program winning well
in excess of 50% of its games. It ain’t perfect, but it’s good enough
that you shouldn’t bet against it.
EEE 1/12/04