Rock Paper Scissors Lizard Spock

I am quite the fan of rock paper scissors. Usually the attraction of playing rock paper scissors is that the outcome is viewed as random. Random is here taken to mean that all outcomes have equal probability. Because there is no obvious advantage to choosing say rock over scissors we assume that the choice between these elements is done at random in which case the game really does provide a random decision process. But suppose that the entities playing the game are not capable of truly random behavior (e.g. they are human) in which case there is now an incentive to try and predict what the action of your opponent is going to be. Especially if you are playing a game of RPS such that the victor is decided by the best two out of three or the best three out of five. Because then you have the data of what happened on the previous play which will give you an extra boost to decide what to do now. I once heard of a computer program that was written to analyze the probability distribution of the behavior of human opponents in a game of RPS and after a little while of observing the human player playing the computer opponent was able to beat the human player somewhere around 60-70% of the time.

I have been thinking rather a lot lately about different methods by which it might be profitable to do behavior prediction of agents playing games. The paper rock scissors type game seems to be a rather simple and interesting type of testing grounds on which i could try to test my methods of strategy analysis. Today I stumbled upon a game called Rock Paper Scissors Lizard Spock which is a simple generalization of the idea of a RPS type game

http://www.samkass.com/theories/RPSSL.html

In RPS we are using a directed version of the complete graph on 3 elements k3, which is just a triangle. The win loss relationships in RPSSL are more complicated because we are using k5 instead which is now more than just a loop. We can make a further generalization of this type of game by using the complete graph on n nodes kn and then randomly choosing a direction for each of the connections between the nodes denoting which node wins in a contest of the two. While admittedly this doesn't make for very interesting humanly playable games it does provide a convenient way to generate a large field for testing ideas for strategy prediction.

The method used in the aforementioned RPS playing computer program was Markov chaining. Which basically means the program would just look at the last couple of plays of the human player and take them to be the indicator of what they would do next. The program analyzes the probabilities of the human player and then just does what the probabilities suggests it should. For a human player playing RPS this works well. Part of the reason for this is that the state space for RPS is small. Meaning that the previous play combinations have only a relatively small total number of possibilities. There are 9 possibilities of play at each step in the game meaning that if we want to try and get decent probabilities based on a one step Markov chain we only need to observe behavior for perhaps a couple dozen turns. Of course a branching factor of 9 is still fairly large and no human player is going to play the computer long enough to make the 5 depth probabilities accurate with 9⁵ = 59049 But that is probably not likely I think the 1 depth probabilities would give decent performance and 2 depth probabilities better. Even 3 depth probabilities with 9³ = 729 are certainly within reach for long games. Since I am interested primarily in being able to beat other computers and not other humans though even depth 8 or 9 Markov chains are not out of reach computationally. I would be willing to hypothesize that computers playing against other computers with the same sort of Markov models would generally tend to end up tying each other. I think it would be an interesting exercise to code up such generalized RPS games and pit different prediction strategies against one another. I'll post if it ever gets done.