Geoffrey Mott-Smith Thirty-One Game: This a an example taken from the Ferguson book on Game Theory.
In this game the 2 players alternate moves and in each turn they have to take a card from the ones available and add it to a pile, the first one to make it sum more than 31 loses.
This is what it’s called a Combinatorial Game since the player have sets of moves and there are is no chance involved (and also finishes in a finite number of step and there is always a winner and a loser). In particular, this type of games are called Substraction Games. The problem here is that we have a limited use for each number, if that weren’t the case, the implementation would be trivial.
So for solving this problem we will classify the positions of the game in Winner or Looser positions, from the end to the firsts possible moves, using dynamic programming.
There is a great tutorial on how to implement these kind of games in topcoder at http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames