# The Game of Nim

Nim is a well-known game with a number of variants. The following variant has an interesting winning strategy. Two players alternately take marbles from a pile. In each move, a player chooses how many marbles to take. The player must take at least one, but at most half of the marbles. Then the other player takes a turn. The player who takes the last marble loses. Write a JAVA program in which the computer plays against a human opponent. Generate a random integer between 10 and 100 and use this as the initial size of the pile. Randomly determine whether the human or the computer moves first. The computer can play in two modes: smart or stupid (chosen randomly at start of game). In stupid mode the computer simply takes a random legal value (between 1 and n/2) from the pile whenever it has a turn. In smart mode, the computer takes off enough marbles to make the size of the pile a power of 2 minus one (3, 7, 15, 31, or 63). If the current size of the pile is one less than the power of two, the computer will then make a random legal move. Be sure to make your output for this program as descriptive as possible. For example, at the beginning of each game, display the size of the pile, whether the computer is playing in smart or stupid mode, and who moves first. As moves are made, show each move and the new pile size. If a move is illegal, note that and re-prompt. When someone loses, display appropriate information including who actually lost. *********************************************************************************************************** OUTPUT OF THE PROGRAM. There are 68 sticks in the pile. You go first. Take at least 1, but no more than 34 sticks 34 You take 34 There are 34 sticks in the pile The computer must take at least 1, but no more than 17 sticks Computer takes 7 There are 27 sticks in the pile Take at least 1, but no more than 13 sticks 13 You take 13 There are 14 sticks in the pile The computer must take at least 1, but no more than 7 sticks Computer takes 4 There are 10 sticks in the pile Take at least 1, but no more than 5 sticks 3 You take 3 There are 7 sticks in the pile The computer must take at least 1, but no more than 3 sticks Computer takes 3 There are 4 sticks in the pile Take at least 1, but no more than 2 sticks 1 You take 1 There are 3 sticks in the pile The computer must take at least 1, but no more than 1 sticks Computer takes 1 There are 2 sticks in the pile Take at least 1, but no more than 1 sticks 1 You take 1 There are 1 sticks in the pile The computer must take at least 1, but no more than 1 sticks The computer had to take the last one -- YOU WIN!