Rock Paper Scissors

March 07, 2011

Recently, the New York Times released an interactive version of the game Rock Paper Scissors.

RPS is essentially a break-even game. By playing Rocks, Paper, or Scissors randomly, one is guaranteed on average to win as often as ones opponent. Therefore, the only type advantage that one player can have over another would be psychological. In essence, can beat a human opponent by taking advantage of peoples poor ability to generate random numbers. A person, in attempting to be random, or even in an attempt ing to gain a psychological advantage, may fall into patterns that can be exploited.

The New York Times website designed such a program to exploit these tendencies in human opponents. The designers of the Times interactive game claim to use the past history of a persons moves to anticipate and counter that individual's next move. The article explained in general how this works. The opponent computer algorithm builds up in memory a string of a persons move history as he plays the game. It then searches through the persons last few moves and looks for a matching pattern earlier in the game. Based on what the person did after that earlier matching patter, the computer guesses what the person will do as his next move.

For example, lets say that after 10 games a persons history looked like RRSRPSRSRP. The last three moves that this person made were SRP. The algorithm would look through his history for another time that he threw SRP in that order: RRSRPSRSRP. Beginning at the third move, the person threw SRP followed by an S. Therefore, the algorithm would guess that the person is again going to throw an S and, to exploit this potential pattern, the computer would counter with a R (since Rock beats Scissors). The algorithm starts by looking for long strings 5 moves long and then searches for shorter strings if no longer string patterns are matched.

I've coded up my version of the game, which can be played here (and the code can be viewed here.

This algorithm is pretty simple, but apparently somewhat effective. However, since its a fixed algorithm, its perfectly exploitable. Simply put, if one were able to perfectly recreate the algorithm based one ones own moves, one could predict the computers guess for the humans move. With this guess, one knows what the computer will throw, and therefore one can simply throw the hand that beats the computers move. Its simple and quite insidious. So, I set out to do just that. I wrote a short python script that, as best as it was described by the Times, copies the Times algorithm. By knowing the algorithm, I can do my best to beat the machine at its own game. If the computer thinks that Ill throw a Rock, it will throw a Paper. But if I know that the computer think Ill throw a Rock, I know itll throw a paper, and instead I can throw a Scissors.

My Code:RocksPaper

Ive included my python code and an example of how to run it. I chose python because itsinteractive interpreter allows me to use the code to in real time play against the computer. An example of a round I played is as follows: After the 8th round:


Throws so far: ['R', 'R', 'P', 'S', 'S', 'R', 'S', 'S']
Last 4 : ['S', 'R', 'S', 'S']
Matching Plays: []
Last 3 : ['R', 'S', 'S']
Matching Plays: []
Last 2 : ['S', 'S']
Matching Plays: ['R']
Suggested Play: S

As you can see, MY algorithm started by looking at my last 4 throws and seeing if there were any such throws in my history. It found none, and then moved on to 3 and finally 2. My last two throws were S,S. My code found that I had previously thrown SS starting on the 4th round, and after that pair, I had thrown a R. The Times program, based on that, would anticipate that I would throw a R, so it throws a P. But since I know its going to throw a P, I throw a S.

Using this strategy, I overwhelmingly defeated the computer. It was pretty satisfying, actually. I felt a little bad seeing the computer be so wrong so often. But I realized that I was simply doing what the computer was attempting to do to me. The algorithm was attempting to understand the complexities of human psychology and use them against us. I was simply using the simplicity of the computers psychology against it.

After 57 games (when I arbitrarily stopped playing), I had amassed 40 wins to the computers 6, with 11 ties.

As the complete nerd that I am, I wanted to quantify my victory, so I decided to compare that level of victory to the amount of victories that one would expect using a random-only strategy. In Stat-speak, I wanted to calculate the p-value of a random RPS strategy.

Its easy to show that the probability of a particular end-game result of W wins, T ties, and L loses (ignoring order, which isnt important) is given by:

(The brackets indicate the binomial, or "choose," function).

One can then simply preform a sum to calculate the total probability of obtaining as many or more wins minus losses from random chance. Using my numbers, I calculate that the chance of a random strategy doing as well or better as my strategy is 9.26 * 10 ^ -9. This is certainly a statistically significant result (its better than the 5 sigma significance required by higher energy physics, which corresponds to a p value of 5.7 * 10^-7. My value falls somewhere between 5 and 6 sigma.)

Though the problem is pretty trivial in terms of computer science, Im glad that the NYTimes made this demonstration. I imagine that the authors of this program were inspired to the success of Watson in playing Jeopardy. I think its a good thing that the Times is seeking to demonstrate how powerful even very simple computer algorithms can be. And it was certainly a fun exercise to try to beat the Times model. If I were making my own model, I would make a few changes (for example, I would consider simultaneously the result of different size string searches). But the point wasnt to make the best possible computer RPS player. Rather, it was to encourage people to think algorithmically and to elucidate how programmers approach computer challenges.