Playing Expert Rock, Paper, Scissors
As a final project for my Foundations of Machine Learning class with Rob Schapire, I created a Java applet that plays "Rock, Paper, Scissors" and consistently beats humans. In 2006, its final record was 114-47 (it has been reset since moving to this new website.)
Sorry! I'm moving to a new web server and my old record keeping code doesn't work anymore. You can still play, but it won't record your game history in the database. Click here to play.
This is currently disabled until I write more code on my new server.
How it works
The algorithm is based on online updates of weighted prunings of decision trees, a member of a family of algorithms based on the notion of "learning with expert advice".
In other words, the algorithm builds a probability distribution based on every possible combination of moves you previously have taken, starting with a blank slate at the beginning of the game. Any strategy that you employ will be exploited. And to make sure that you're kept on your toes, there's some randomness in the algorithm, too...
For more information about these algorithms, see Cesa-Bianchi et al. and Hembold and Schapire.