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.