Paper Scissors Stone
Paper Scissors Stone is more complicated than I thought (via BoingBoing). This article from 1999 describes the second international RoShamBo programming contest, in which entrants had to provide a program that could play other programs at the classic childhood game:
A good predictive algorithm will be able to play RoShamBo very well, without being explicitly programmed to solve that task. A few applications of such algorithms are data compression, grammatical inference, speech recognition, data mining, natural language understanding, syntactic pattern recognition, speech segmentation, machine translation, text generation, spelling correction, author identification, email classification, image recognition, stock market analysis, finding structure in data, analysis of DNA sequences, analysis of music, input methods for disabled users, and playing RoShamBo!
The winning program Iocaine Powder is described by the author here.