The Hanover Collaboration

Here’s an applet that lets you play rock/paper/scissors against the computer. Some of you might find the following two experiments interesting. You should do the experiments before reading how the algorithms work.

1. Play with the window scaled such that you can’t see the results. In other words, do your best to create a random sequence. Check in every 25 clicks or so.
2. Watch the computer and see how well you can “fake it out.”

In both cases I went to an early lead, but by 100 or so the computer had “gotten into my head.”

I’m pretty impressed, so much the more because the algorithm is deterministic¹ and shockingly simple. You could write it with a few lines of shell script. Basically, it records your move history as a string. Then to that string it tries appending ‘r’,‘p’ and ‘s’ and compresses it with the standard unix “compress.” It predicts that you will make the move with the best compression ratio and plays accordingly.

Next time you are facing an inference or prediction problem, before you dive into anything fancy (in this case, say, Q-learning) you should try running it through compress or gzip and see what happens.

¹ If it were allowed to randomize, you wouldn’t be able to net nearly so many points in the beginning.