Which one do you start with – rock? Paper perhaps? Or scissors? This great LEGO® MINDSTORMS® robot (found via instructables.com) can not only play the traditional rock-paper-scissors game but it also learns how to play the game and beat the person it is playing against!
It does require more input than two humans playing against each other (the article says that the user has to input moves and to say who had won) but this is a great example of how LEGO MINDSTORMS can be used to push what can be created using standard kit.
Full details of the model can be found here – what other games could LEGO MINDSTORMS be used to re-create?