Mathwizurd.com is created by David Witten, a mathematics and computer science student at Vanderbilt University. For more information, see the "About" page.

## Jan 26 AI Rock Paper Scissors

Rock, Paper, Scissors- the classic game of chance. However, is it random?

When doing Rock, Paper, Scissors, one's moves are very pattern-based. For this reason, making an algorithm to defeat a human isn't that difficult.

So, I created an algorithm that saw the user's most popular chains of N moves (you can change N, depending on what length chain (called a Markov chain) you want to track. Generally, if you can make it simpler, without sacrificing results, you should.

So, it creates a dictionary of all of the possible N-length chains of moves, by assigning rock to 0, paper to 1, and scissors to 2 (e.g. {'012':0,'110':3}, meaning 3 occurrences). Whenever you do one of those chains of moves, it increases it by one.

When the computer decides which move to make, it looks to see which combinations are the most popular. If you had just gone rock, rock, and had previously gone (rock, rock, scissors) 72 times, more than any other combination, the algorithm says that it is most likely that you'd go rock, rock, scissors again, and it rolls rock.

When there's a tie, it randomly selects one of the two/three it think's you'd go, and does the one after it (e.g. it think's you will go scissors, so it goes rock).

There are other factors, such as if the user won or lost, but I would need a much larger data set in order for it to make a it effective.

Analysis:

Overall, it works very well. As expected, when I did 1000 random moves (random number generator from 0 to 2), it won a third of the time.

Here is the graph of the win percentages based on the Markov Chains used.

## Users's Winning Percentage vs. Computer based on Markov Chain

As I stated above, since a Markov Chain of 3 works better than any other from 2 through 10, it should be used, since it's simpler, so it's faster.

Here's the code. I wrote it as a class just because. The old version looked even worse.

This is my checking algorithm:

```def check(self):
start = {'0':'2','1':'0','2':'1'}
if self.userMove == self.compMove:
self.WLT['ties'] += 1
else:
if start[self.userMove] == self.compMove:
self.WLT['wins'] += 1
else:
self.WLT['losses'] += 1```

The dictionary "start" assigns a move to the one it beats. If the moves are equal, it's a tie, obviously, and if the result of the user's move is the opponent's room, it means the user wins.

This is how the AI algorithm is made, if there is one leading chain, it thinks the user will do that. If there are two tied for first, it thinks the user will do one of those, and if they're all equal, it picks them at random. At the end, it picks the next one in the order. If the computer thinks you will roll rock, it rolls paper.

```def AI(self):
possible = [i for i in self.combos.keys() if tuple(self.recent) == i[:-1]] #Possible next moves
new = {i:self.combos[i] for i in possible}
try:
finish = max(new,key=new.get)[-1] #(max element in the dictionary, by its value)
except ValueError:
if len(set(new.values())) == len(new.values()): #All equal chance
finish =  str(random.randrange(3))
else:
g = min(new,key= new.get)[-1] #Top two equal
finish = str(random.choice(list('012'.replace(g,''))))
return '012'['012'.index(finish)-2] #Winning move to the most popular one
```

An explanation: I put the parts to make it playable in triple quotes. If it doesn't work, I'll attach the other file below, and you can play with the computer.

David Witten