Rock Paper Scissors Programming Competition

All it did was keep around compressed concatenation of the opponents plays, and a compressed concatenation of opponent and my plays interleaved. When it was my turn to play, I would extend the strings with the three possible one turn plays, i.e. extend by 'r', 'p', 's' and re-compress, whichever gave the shortest compression was my guess of what the opponent would play next. Then I would play whatever defeated opponent's guessed play.

The whole thing was 15~20 lines but of course I was standing on shoulder of giants and the std library. The prediction part was entirely abstracted / co-opted out to the compressor. Better compressors would yield better results. Lempel-Ziv worked well enough as long as there were enough rounds.

The theory for this can run quite deep. There are algorithms that will do the best possible if the opponent is using a finite state m/c, which computers are anyway. The performance of these are determined by the state space of the FSM. If one wants to go deeper then one would land in the territory of Kolomogorov complexity.

I ended up going with a 'many demons' solution whereby I had many strategies voting on what the guess should be and I modulated the weight of their votes based on their success. I also used 'sicillian logic' to make meta-strategies that simply voted on a move that would win/lose to the guesses of my other strategies.

One thing I always wanted to try was to cheat. Flood the submissions with bots that would attempt a pseudo-random-looking handshake. If it failed the bots would act randomly. But if it succeeded they would perform a pre-determined pseudo-random pattern that my one true bot would exploit to boost its rating.

The comment in the program is, of course, a joke. What I actually did was download every other bot on the site, pick out all the ones that made no calls to `random` and let a brute force search for a good constant run for a few days.

The trick is that random play wins about 50% of the time, and this hack, despite being totally deterministic, has play that is indistinguishable from random within the constraints of the contest unless specifically accounted for. For each other program that also has deterministic play, about half of all possible constants will win. Try enough constants and eventually you'll find one that wins against a moderate majority of the other entries.

You can either play the "equilibrium" where your play is non-exploitable and yields neutral expectation (this is done by using a push-fold chart). Or you can play "exploitably" where your play tries to predict patterns in the opponent to gain a positive expectation.

The difference between this and rock-paper-scissors though is it involves more factors (3 choices vs 169 starting hands + push-or-fold), and a little bit of short-term chance. Though of course if you run bot vs bot 1,000,000 times, it'll be pretty clear which is superior.