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.
Can the computer be beaten if it is playing in smart mode when it has the first move? If so, under what conditions would this happen?