The rules for playing the game Nehmen are as follows. Nehmen is played between two players, I (the computer) and U (you). To start with there is a bag containing N items, say sticks. One of the player starts the game, and after that moves alternate between the players. At each move a player has to take out some number between 1 and M of sticks from the bag with the only restriction that one is not allowed to take out the same number of sticks as his/her opponent took out in the immediately preceding move. No player is allowed to pass a move. The player who fails to take out stick(s) from the bag loses.

Here is an example of Nehmen. Initially, there are N=20 sticks and player I makes the first move. Take M=5.

Sticks left : 20.  Player I takes 5 sticks.
Sticks left : 15.  Player U takes 4 sticks.
Sticks left : 11.  Player I takes 5 sticks.
Sticks left :  6.  Player U takes 3 sticks.
Sticks left :  3.  Player I takes 2 sticks.
Sticks left :  1.  Player U takes 1 stick.
Sticks left :  0.  Player I is unable to move and loses.

Here is another game starting from the same initial settings.

Sticks left : 20.  Player I takes 3 sticks.
Sticks left : 17.  Player U takes 5 sticks.
Sticks left : 12.  Player I takes 1 stick.
Sticks left : 11.  Player U takes 4 sticks.
Sticks left :  7.  Player I takes 5 sticks.
Sticks left :  2.  Player U takes 1 stick.
Sticks left :  1.  Player I is unable to move and loses.

In order to make this game interesting for you, we provide you our implementation of the game. However, in order that you cannot simply mimic our strategy, you are given only the binary executables. These are expected to work in Pentium machines running some version of Linux.

Your objective for this assignment is to find a winning sequence of moves for each of the following games. You are advised to write a program to help you locate your winning strategy. Dynamic Programming should help you greatly.

Submit your program and your winning sessions for the following five cases. Save the linked files in your machine, give execute permission and run.

chmod 755 nehmen1
chmod 755 nehmen2
chmod 755 nehmen3
chmod 755 nehmen4
chmod 755 nehmen5

Download	N	M	Who starts	Difficulty level
Game 1	100	10	I	U r a kid!
Game 2	100	15	U	U r grown-up!
Game 3	100	20	U	U r a dynamic programmer!
Game 4	100	25	I	U r Dynamic Programmer the Great!
Game 5	100	30	I	U r the Superhuman Incarnate!

Well, if these examples make you feel that the winning strategy for this game is too trivial and does not require dynamic programming, we suggest you to find out the winning strategy for other small variants of this game, for example, when a player is not allowed to repeat the last two moves, or the last two moves of the opponent, etc. Write a dynamic program to tackle one such variant which does not seem obvious to you.

Home