2. The game of Nim. Two players alternately take marbles from a pile. In each mo

Question

2. The game of Nim. 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 looses.

Write a program in which the computer plays against a human opponent. The computer can play in two modes: smart or stupid. In stupid mode, the computer simply takes a random legal value (between 1 and half of the marbles) 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, 63, etc.). That is always a legal move, except if the size of the pile is currently one less than a power of 2. In that case, the computer makes a random legal move. (Note that the computer cannot be beaten in smart mode when it has the first move unless the pile size happens to be a power of 2 minus 1. Of course, a human player who has the first turn and knows the winning strategy can win against the computer. )

Minimum requirements: ask the user to enter the initial size of the pile between 10 and 100, a number 0 or 1 to decide who has the first turn, and a number 0 or 1 to decide whether the computer plays in stupid or smart mode. Then play the game accordingly.

Explanation / Answer

#include <iostream>
#include <time.h>
using namespace std;

int main()
{
   //PROTOTYPES
   int compMove(int mode, int marbles);

   //LOCAL DECLARATIONS
   int marbles = 0;
   int turn = -1;
   int mode = -1;
   int takeOffQuan;

   //PROCEDURES
   srand((unsigned)time(NULL));

   while (marbles < 10 || marbles > 100)
   {
      cout << "Enter the number of marbles to play (10-100): ";
      cin >> marbles;
   }
   while (turn < 0 || turn > 1)
   {
      cout << "Decide who plays first (0-You 1-Comp): ";
      cin >> turn;
   }
   while (mode < 0 || mode > 1)
   {
      cout << "Decide computer mode (0-Stupid 1-Smart): ";
      cin >> mode;
   }

   cout << endl;

   while (marbles)
   {
      if (!turn)
      {
         cout << "The pile currently has " << marbles << " marbles. ";
         cout << "Enter the number of marbles you want to take off: ";
         cin >> takeOffQuan;
         if (marbles != 1)
         {
            while (takeOffQuan < 1 || takeOffQuan > marbles / 2)
            {
               cout << "Invalid number. "
                    << "The number of marbles must be between 1 and half of the pile's size. ";
               cout << "Re-enter the number of marbles: ";
               cin >> takeOffQuan;
            }
         }
         else
         {
            while (takeOffQuan != 1)
            {
               cout << "Invalid number. "
                    << "You must take off the last marble!!! ";
               cout << "Re-enter the number of marbles: ";
               cin >> takeOffQuan;
            }
         }
         cout << endl;
         marbles -= takeOffQuan;
         turn = 1;
      }
      if (marbles)
      {
         takeOffQuan = compMove(mode, marbles);
         cout << "Computer takes off " << takeOffQuan << " marbles from the pile. ";
         marbles -= takeOffQuan;
         turn = 0;
         cout << endl;
      }
   }

   cout << "You " << (turn ? "lose!" : "win!!!") << endl;

   cout << endl;
   cin.sync();
   cin.get();
   return 0;
}

//---------------------------------------------------------
// FUNCTION DEFINITIONS
//---------------------------------------------------------
int compMove(int mode, int marbles)
{
   if (!mode)
   {
      if (marbles == 1)
         return 1;
      return rand() % (marbles / 2) + 1;
   }
   else
   {
      if (marbles == 1)
         return 1;
      int targetMarbles = 63;
      while (marbles - targetMarbles <= 0)
      {
         targetMarbles /= 2;
      }
      if (marbles - targetMarbles > marbles / 2)
      {
         cout << "Ouch! ";
         return rand() % (marbles / 2) + 1;
      }
      return marbles - targetMarbles;
   }
}
//---------------------------------------------------------
//---------------------------------------------------------

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.