Roshambo or
rock paper scissors is interesting from the point of
view of
AI. You can
download the
source code for the entries in
the first Roshambo programming contest from http://www.cs.ualberta.ca/~darse/rsbpc.html.
You might think that a random strategy would be optimal for this
game but because there are some opponents with a strategy
that sucks
int rockbot () /* Good Ole Rock */
{
/* "Good ole rock. Nuthin' beats rock." */
return(rock);
}
there are opportunities for
intelligent strategies to out-perform
Random. The winner in the first tournament was
Iocaine Powder
by Dan Egnor. There's a detailed explanation of how it works in the source code but I'll outline the general idea.
IP tries to predict what its opponent will do. It has several predictive
algorithms that it can use for this. These include Random Guess,
Frequency Analysis and History Matching. But it also uses a metastrategy so that each predictive algorithm P gets tranformed into six variants. I won't list them all but these include
-
Just Use P.
- Try to defeat second-guessing. Assume that your opponent guesses you are using P. Say P predicts their next move is paper. So according to P IP would play scissors. Since your opponent is on to you
they will play rock instead of P's prediction. So to defeat them,
this variant strategy will play paper.
As you can guess, defeating triple-guessing is next!
Finally, how does IP decide between each of (the six variants
of) its different predicitve algorithms? Simple. It assumes that it's opponent
will be using a consistent strategy and tests out how each of the variants
of each P would have done over the last few rounds. It then chooses
the variant that would have done best.