## CS23005 Design and analysis of algorithms | ## Autumn 2004--2005 |

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.