Question

The game of Nim. This 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 program in which the computer plays against a human opponent. Generate a random integer between 10 and 100 to denote the initial size of the pile. Generate a random integer between 0 and 1 to decide whether the computer or the human takes the first turn. Generate a random integer between 0 and 1 to decide whether the computer plays smart or stupid. 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 two minus 1 - that is, 3, 7, 15, 31, or 63. That is always a legal move, except when the size of the pile is currently one less than a power of two. In that case, the computer makes a random legal move.

You will note that the computer cannot be beaten in smart mode when it has the first move unless the pile size happens to be 15, 31, or 63. Of course, a human player who has the first turn and knows the winning strategy can win against the computer.

Make sure your program tells the user whether the computer played in smart or stupid mode.

Your program will need to use both decisions (if statements) and loops.

method returns a double value >= 0.0 and < 1.0. To get a random integer between two integer values (Min and Max) use:

Min + (int)(Math.random() * ((Max - Min) + 1))

Write pseudocode and/or a flow chart before you try to write this program. As you write your program, a good practice would be to write and test it in parts. For example, generate the initial size of the pile, which player goes first, and what mode the computer plays in and output without actually playing the game. Then play one round and end the game, etc.

Submit:
Pseudocode for your solution.
Your Java code as a .java file.

Answer 1

Pseudocode

1. n = a random integer between 10 and 100

2.. mode = a random integer between 0 and 1

3. Repeat While True:

4. Print: n + " marbles left"

5. IF n==0 Then

6 Print "You won!"

7. Else

8. Print : "How many marbles would you like to remove from pile?"

9. Read m

10. If m<=0 Or  m>n/2 Then

Goto Step 8.

11. n = n - m;

12. Print: n + " marbles left"

13. If n==0 Then

14. Print "Computer won!"

15. Else

16. If n==1  Then m=1
17. Else If mode==0 Then

18.  m = a random integer between 1 and n/2

19. Else If mode ==1 And n>=6 Then

20. m = a random integer between 2 and 5

21.  m = Power(m, 2) -1

22. If m<=0 Or m>n/2 Then

23. Goto 20

24. Else

25. m = a random integer between 1 and n/2

26. If m<=0 Or  m>n/2 Then

27, Goto 25

28. n = n - m

29. Print "The computer has taken " + m + " marbles from pile"

[End of loop]

30.End

Program

import java.util.Scanner;

//class Nim
class Nim
{
   //main method
   public static void main (String[] args)
   {
       //create instance of Scanner class and Random class
       Scanner sc = new Scanner(System.in);
      
       //Generate a random integer between 10 and 100 (initial size of the pile)
       int n = (int)(Math.random() * 91) + 10;
      
       //Generate a random integer between 0 and 1 (computer plays mode: smart or stupid)
       int mode = (int)(Math.random() * 2);
      
       if(mode==0)
           System.out.println ("Stupid mode");
       else
           System.out.println ("Smart mode");
          
       int m;
      
       //start play game
       while(true)
       {
           //display current state of the board
           System.out.println (n + " marbles left\n");
      
           //check for end of game
           if(n==0)
           {
               System.out.println ("You won!");
               break;
           }
          
           //prompt and read stone number from user
           do
           {
               System.out.print ("How many marbles would you like to remove from pile?");
               m = sc.nextInt();
           }while(m<=0 || m>n/2&&n!=1);
          
           //decrease number of stones
           n = n - m;
          
           //display current state of the board
           System.out.println (n + " marbles left\n");
          
           //check for end of game
           if(n==0)
           {
               System.out.println ("Computer won!");
               break;
           }
          
           //Computer's turn
      
           //select stone numbers randomly
          
           if(n==1) m=1;
          
           else if(mode==0)
           {
               do
               {
                   m = (int)(Math.random() * n/2) + 1;
               }while(m<=0|| m>n/2);
           }
           else
           {
           if(n>=6)
           {
               do
                   {
                       m = (int)(Math.random() * 5) + 2;
                       m = (int)Math.pow(m,2) - 1;
                   }while(m<=0 || m>n/2);
           }
           else
           {
               do
                   {
                       m = (int)(Math.random() * n/2) + 1;
                   }while(m<=0|| m>n/2);
           }
           }

           //decrease number of stones
           n = n - m;
          
           //display computer selections
           System.out.println ("The computer has taken " + m + " marbles from pile.\n");
       }
   }
}

Output:

Stupid mode
99 marbles left

How many marbles would you like to remove from pile?31
68 marbles left

The computer has taken 28 marbles from pile.

40 marbles left

How many marbles would you like to remove from pile?15
25 marbles left

The computer has taken 10 marbles from pile.

15 marbles left

How many marbles would you like to remove from pile?7
8 marbles left

The computer has taken 4 marbles from pile.

4 marbles left

How many marbles would you like to remove from pile?1
3 marbles left

The computer has taken 1 marbles from pile.

2 marbles left

How many marbles would you like to remove from pile?1
1 marbles left

The computer has taken 1 marbles from pile.

0 marbles left

You won!