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

^{5}= 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

^{3}= 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.

## No comments:

Post a Comment