A while ago there was a competition for Rock-Paper-Scissors game: http://webdocs.cs.ualberta.ca/~darse/rsbpc.html
At first I thought that the best strategy should be just random. However, when there are deterministic bots with a definite patterns (eg., always play a winning strategy to the opponent's last move) then a clever bot should do better. So the task boils down to learning/predicting your opponent's strategy. There has been some serious research done in this area and so the problem is quite interesting and non-trivial. Also I like that the game is very easy to understand, easy to code and testing should be very fast (I am thinking in the order of 100 moves per second).
We could repeat this challenge with a small modification. One idea I had was to extend the game to multiple players. This can be done by doing score=(number of people you beat) - (number of people you lost to). The aim is to maximize the score. Here are some examples for 3 players:
* A chooses rock, B chooses paper and C chooses paper. scoreA=-2, scoreB=1, scoreC=1
* A chooses rock, B chooses rock and C chooses paper. scoreA=-1, scoreB=-1, scoreC=2
* A chooses rock, B chooses paper and C chooses scissors. scoreA=0, scoreB=0, scoreC=0
* A chooses rock, B chooses rock and C chooses rock. scoreA=0, scoreB=0, scoreC=0
This extra complexity should make the challenge sufficiently difficult and different from the previous one.