The algorithm that beats this New york times' Rock/Paper/ Scissors AI

Question

The algorithm that beats* this New York Times' AI without brute forcing in Rock/Paper/ Scissors? (in Veteran Mode)

http://www.nytimes.com/interactive/science/rock-paper-scissors.html?_r=1& (flash must be enabled to play with the AI)(Website constantly gives info on how AI selects its next move after you played at least 5 times)

I am learning machine learning on my own and I'm pretty novice. (Just started yesterday).

My friend told me they were assigned to solve above problem without learning any ML techniques in their ML class. I also wanted to do it but I cannot think any other way except brute forcing.

For the training data set play with AI 100 or more time and collect those 100 or more data. Use this data to create an algorithm so that you win more games when using your program than without using your program. Being a super Novice, I can not think anything at all.

any hints? Thanks

Answer 1

Novice mode

So the nice thing of the site is, is that it shows the idea is behind every move. It tries to predict your action by looking at the history of your moves. So your move history could be the following: (rock =r, scissor =s and paper =p)

r p s p p s s r r p s

Now it looks through the history and tries to find a recurrence of r p s. It find this at beginning of the history r p s p p s s r r p s, and find that you played p after that. Thus the next move of the computer will be s.

If it cant find the recurrence of the string (r p s) it looks at smaller strings (p s) and so on. If it find mutiple recurrences, picks the one wich recurred the most (or for even just random picks one).

So you could write a program wich does exactly the same as the on the site. You try to predict your own move (like the program of the site does). So lets for example (r p s), the computer would predict a move of p, so with that knowledge you would pick s.

veteran mode

In veteran mode the AI uses the history of 200000 games to predict your next move. So to try to beat that you will use the history of 100 games in exactly the same way the AI does it.

You look at the history of your current try plus of your historie (100 games) and try to find recurrence of a certain type (example r s p r). And you look at what the computer respons was to that. Now you pick accordingly so that you beat the computer. Ofcourse this wont always wins, because the computer often uses a randomized respons between two picks (and a longer history so more samples to pick from). But this should increase the amount of wins you get.

I also do not have any experience with machine learning, but this would be my strategy in writing a program.

I hope this helps.

If you cannot beat them join them ;) Cheers