20-CS-122-001 Computer Science II Spring 2012
Implement a Game

Virtual functions, classes, inheritance, lists, queues, stacks, applications

A game:
    Here is a game for two players. The game begins with a list of numbers from 1 to 9. Player one takes one of the numbers. Player two takes one of the remaining numbers. This continues until either some player has a subset of numbers that sums to 15 or all the numbers have been taken. A player with a subset summing to 15 wins. Otherwise the game is a draw.

Example:
    Move     Player     Chooses     From     Reason     Player 1 has     Player 2 has
    1     1     5     1,2,3,4,5,6,7,8,9     Seems like a good move     5    
    2     2     2     1,2,3,4,6,7,8,9     Tit for Tat     5     2
    3     1     8     1,3,4,6,7,8,9     Strategic move     5,8     2
    4     2     9     1,3,4,6,7,9     Setting up 2,4,9     5,8     2,9
    5     1     4     1,3,4,6,7     Block the 2,4,9     4,5,8     2,9
    6     2     3     1,3,6,7     Block the 3,4,8     4,5,8     2,3,9
    7     1     6     1,6,7     Grab the 4,5,6     4,5,6,8     2,3,9
Player 1 wins in 7 moves!

The problem:
    Write a program that plays according to the rules but never loses a game if it makes the first move.