davidbau.com

RPS Battle of Wits

For a little programming fun, try playing the Online Rock-Paper-Scissors Battle of Wits.

Back in 1999 and 2000, Darse Billings introduced the world to computer-RPS in the First and Second International RoShamBo Programming Competition. You might imagine that rock-paper-scissors is too simple a game to be worth building computer players. But you would be wrong.

How to Win at Rock-Paper-Scissors

True, it is impossible to build an algorithm that dominates the simple random player, but it is also impossible for the random player to dominate any other algorithm. In any tournament that includes nonrandom players, you can win by detecting the nonrandom strategies and beating them.

For example, if your opponents are the random player and good ole' rock, you can win the tournament by just playing "always paper." When you go up against random, you will be evenly matched. But you will dominate rock - that is better than random can do, and so you win overall.

Of course "always paper" and "always rock" are defeated by my daughter Piper's favorite RPS strategy, which is to make the move that beats her opponent's previous throw. Here is her algorithm, written in python:

import rps, random
 
last = random.randrange(3)
for turn in xrange(rps.turns):
  last = rps.play(rps.beat(last))

In this code rock is 0, paper is 1, and scissors is 2; rps.beat(last) returns the move that beats "last"; and rps.play(n) plays our move and returns our opponent's.

Piper's "beat last" algorithm is ruthlessly aggressive. On the other hand, it is also very predictable, so it will lose to a player who knows how to provoke it....

Below is Daddy's counter to Piper's algorithm - I call it the "provoker." It actually knows how to recognize and dominate a whole class of basic algorithms including "echo" and "good ole' rock":

import rps
 
their_response, my_last_move = [0, 0, 0], 0
for turn in xrange(rps.turns):
  my_move = rps.beat(their_response[my_last_move]))
  their_response[my_last_move] = rps.play(my_move)
  my_last_move = my_move

As you can imagine, with enough deviousness you can do far better than this. And yet any program that tries to trip other algorithms will be predictable to some extent and therefore vulnerable to defeat itself!

Rock-paper-scissors is the purest game of the second-guess and bluff. To win, you must know your opponents better than they know you.

MMORPS: Massively Mutiplayer Online RPS?

The online Rock-Paper-Scissors arena is now open for RPS battles. You program your bot as a CGI script on your own web server, and then you pit your bot against the others by entering its URL in the arena. Or you can just visit to pit other programmers' bots against each other.

Can you devise a bot that beats the "provoker"? Can you beat the other bots in the arena?

A list of bots in the arena is here. I have written the example bots in python, but you can write yours in whatever language you like; the http-based protocol is simple. (If you do make a bot with PHP or perl or ruby, please do let me know, because I would love to post some example code.)

For keeping score, the arena keeps a record of outcomes and ranks players by their average point scores. I have used Ed Pegg's suggestion to score games in a non-zero-sum way - there is a penalty for ties so that purely random play is at a disadvantage.

Full instructions for building your own RPS bot are posted here. There is a small python rps module that you can use, and code for some example bots is here. Of course the fun is devising your own bot. Simple submissions are helpful and welcome; both super-genius bots and easy-to-defeat bots are interesting.

Winning at rock-paper-scissors is harder than it looks. You should know that very few algorithms are able to dominate Dan Egnor's Iocaine Powder. Do not be discouraged; beating iocaine is only for the very elite. Do not underestimate the challenge.

If you can beat quickstudy you are doing well.

Have fun storming the castle!

Posted by David at January 27, 2007 12:45 AM