Thread: Nim Trainer

  1. #1
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179

    Nim Trainer

    Seriously, I should never be up until 3:30am, but since my wife isn't around I have no self control. I'll turn in early tomorrow.

    Why am I up so late? Can't you guess. I pulled another all-nighter. Got it in my head to do this program and couldn't stop until it was done.

    Supposedly, making a computer program play Nim is an academic exercise. Don't you believe it. Especially if like me you insist on making Nim (multiple piles) and not pick up sticks (one pile) and insist on making the misere version (loser takes last) that everyone is SUPPOSED to be playing anyways, not the "normal" version (winner takes last) that mathematicians like to talk about because the math is easier. But add to that I set myself the sadistic goal of making a game that not only played a perfect game but would teach YOU, the human, to play a perfect game.

    See, if the computer's going to beat you every time you play, what's the fun in that? I'd rather the computer be used as a tool to help me beat my friends later. Maybe your highly honed skills could settle a tab with the bar tender. Maybe not. The point is being beat isn't fun. Learning to beat someone else can be.

    So now I present to you the fruits of my depravity. Why? Like I said, it's 3:30 am and it seems like a good idea.
    Code:
    /* Nim Trainer
     * by Joseph Larson. ver 2008-May-01
     */
    #include <stdio.h>
    #include <ctype.h>
    #include <stdlib.h>
    #include <time.h>
    
    #define MAXPILES 10
    #define MAX 20
    
    void intro () {
      puts("Nim Trainer\n----------\n"
      "Nim is a counting game where players take turns removing objects from\n"
      "piles of things. You can take as many as you want from whichever pile\n"
      "you want. The person who takes the last one loses.\n\n"
      "It is possible to play a perfect game if you:\n"
      " o Think of the number in each pile in binary.\n"
      " o Do an exclusive 'or' (xor) on the numbers.\n"
      "   or count up the number of 1s in the binary columns and if there are\n"
      "   an even number write a 1, if an odd number wirte a zero.\n"
      " o The number, in binary or integer, is called a 'nimber'.\n"
      " o If the nimber is zero, you can't win this round.\n"
      " o If the number is not zero find a piece you can take that will leave\n"
      "   your opponent with a zero nimber.\n"
      " o To win the game, when you get to the point where you'd normally leave\n"
      "   all piles of size 1, make sure there are an odd number of sized 1 piles\n"
      "   and you won't be taking the last one.\n\n"
      "This program is written so help you learn to win nim by showing you the\n"
      "piles in binary and doing the xor for you so you can seen how it works.\n");
    }
    
    void printbinary (int num) { /* Show a number in binary, 1s and 0s. */
      int c;
    
      for (c = 5; c >= 0; c--)
        if (num & (1 << c)) printf (" 1"); else printf (" 0");
    }
    
    void printpile (int num) { /* Show a pile, it's size, and it's binary */
      int c;
    
      for (c = 0; c < 20 - num; c++) putchar (' ');
      for (c = 0; c < num; c++) printf ("| ");
      for (c = 0; c < 20 - num; c++) putchar (' ');
      printf (": %d \t ", num);
      printbinary (num);
      putchar ('\n');
    }
    
    int printgame (int *p) {
      int nimber, c;
    
      nimber = 0;
      printf ("\n%s%40s%s\t  %s\n", "Pile", "", "Size", "Binary"); /* 2 spaces */
    
      for (c = 0; c < MAXPILES; c++) {
        if (!p[c]) continue;
        printf ("%4d", c + 1); printpile(p[c]);
        nimber ^= p[c];
      }
    
      printf ("\n%48s%d\t(","nimber = ",nimber); printbinary(nimber); printf (" )\n");
      return nimber;
    }
    
    int won (int *p) {
      int c;
    
      for (c = 0; c < MAXPILES; c++) if (p[c]) return 0;
      return 1;
    }
    
    int allones (int *p) {
      int c;
    
      for (c = 0; c < MAXPILES; c++) if (p[c] > 1) return 0;
      return 1;
    }
    
    int bestmove (int *bmoves, int *p, int nimber) {
      int c, d, nummoves, number;
    
      nummoves = 0;
    
      number = 0; /* Use number to count the number of >1 sized piles */
      for (c = 0; c < MAXPILES; c++) {
        bmoves[c] = 0; if (p[c] > 1) number++; /* clear best move array as well*/
      }
      if (number == 1) { /* We are in the end game. */
    
        printf ("\nThis is it, the end game. Make sure you leave an odd number of "
        "piles of size 1.\n");
    
        number = 0; nummoves = 1;
        for (c = 0; c < MAXPILES; c++)
          if (p[c] > 1) d = c; /* use d to store the 1 pile >1 */
          else if (p[c] == 1) number++;
    
        if (number % 2) bmoves[d] = p[d];
        else bmoves[d] = p[d] - 1; /* leave an odd number of 1 piles */
    
      } else if (allones(p)) {
        for (c = 0; c < MAXPILES; c++) if (p[c]) {
          bmoves[c] = p[c]; nummoves++;
        }
     
      } else if (!nimber) {
        printf ("\nThe nimber is 0, which means there is no best move right now.");
        for (c = 0; c < MAXPILES; c++) if (p[c]) { /* random moves */
          nummoves ++; bmoves[c] = p[c] - rand() % p[c];
        }
    
      } else { /* the nimber has a value, so we must have a move. Easy first */
        for (c = 0; c < MAXPILES; c++)
          if ((p[c] & nimber) == nimber) {
            nummoves ++;
            bmoves[c] = nimber;
          }
        if (nummoves)
          printf ("\nThere is/are %d relatively easy good moves.\n"
          "Hint: Look for the binary nimber within a pile, and take the nimber's "
          "number\nof pieces away from that pile.\n", nummoves);
    
        else {
          printf ("\nGood moves are hard to find here. Look at the row(s):\n");
          for (c = 0; c < MAXPILES; c++) for (d = 0; d < p[c]; d++)
          if (!(nimber ^ p[c] ^ d)) {
            nummoves++;
            bmoves[c] = p[c] - d; printf ("Row %d, ", c + 1);
          }
          printf ("\nRemember, to leave your opponent with a nimber of zero\n"
           "Good luck.\n");
        }
    
      }
    
      return nummoves;
    }
    
    void compymove (int *p, int nimber) {
      int num, c, bests[MAXPILES];
    
      num = bestmove (bests, p, nimber);
      num -= rand () % num; /* randomly select a move */
      for (c = 0; c < MAXPILES && num; c++)
        if (bests[c]) num--;
      c--;
      printf ("\nComputer takes %d from pile %d leaving...\n", bests[c], c + 1);
      p[c] -= bests[c];
    }
    
    void humanmove (int *p, int nimber) {
      int c, nummoves, pile, number;
      int bests[10];
    
      nummoves = bestmove (bests, p, nimber);
      do {
        printf ("\nTake from which pile? ");
        scanf ("%d", &pile);
        if (!p[--pile]) printf ("\nThere is nothing to take from that pile.");
      } while (!p[pile]);
      do {
        printf ("\nHow many? ");
        scanf ("%d", &number);
        if (!number || number > p[pile])
          printf ("Choose a number between 1 and %d.", p[pile]);
      } while (!number || number > p[pile]);
      p[pile] -= number; /* do the move */
      if (nimber) {
        nimber = 0; /* Calculate the new nimber */
        for (c = 0; c < MAXPILES; c++) nimber ^= p[c];
        if ((nimber) && (!allones(p))) {
          printf ("\nThat wasn't the best move. Move(s) that would have left a "
          "nimber of zero would\nhave been:\n");
          for (c = 0; c < MAXPILES; c++) if (bests[c])
            printf ("%d from pile %d\n", bests[c], c + 1);
          printf ("\nPress ENTER...\n"); getchar (); getchar ();
        }
      }
      printf ("\nYou take %d from pile %d leaving...\n", number, pile + 1);
    }
    
    void play () {
      int piles[MAXPILES];
      int c, nimber;
      char ch;
    
      do {
        puts ("\nDo you want a (S)tandard or (R)andom setup? (S/R) ");
        while (!isalnum(ch = getchar ()));
      } while ((tolower(ch) != 'r') && (tolower(ch) != 's'));
      if (tolower(ch) == 'r')
        for (c = 0; c < MAXPILES; c++) piles[c] = rand () % MAX;
      else
        for (c = 0; c < MAXPILES; c++) piles[c] = (c < 3) ? 3 + c : 0; /* "Standard" setup */
    
      nimber = printgame (piles);
    
      while (!won (piles)) {
    
        if ((!nimber) && (!allones (piles))) {
          printf ("\nComputer is going to win. Do you want to continue? (Y/N) ");
          while (!isalnum(ch = getchar ()));
          if ((tolower(ch) == 'n') || (tolower(ch) == 'q')) return;
        }
    
        humanmove (piles, nimber);
        nimber = printgame (piles);
        if (won (piles))
          printf ("\nComputer won that round. Try harder next time.");
        else {
    
          compymove (piles, nimber);
          nimber = printgame (piles);
          if (won (piles)) printf ("\nYou won! You're getting pretty good.");
    
        }
    
      }
    }
    
    int playmore (void) {
      char yesno;
    
      printf ("\nWould you like to play again? ");
      while (!isalpha (yesno = getchar ()));
      if (tolower(yesno) != 'n') return 1;
      return 0;
    }
    
    int main () {
    
      intro ();
      srand (time (NULL));
      do play (); while (playmore ());
    }
    Standard C. No funny business. I'm trying to comment better, and I tried spacing it out a bit more than I usually do. It was like pulling teeth, I tell ya.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

  2. #2
    l'Anziano DavidP's Avatar
    Join Date
    Aug 2001
    Location
    Plano, Texas, United States
    Posts
    2,743
    since my wife isn't around I have no self control.
    I was too lazy to read your code, but I read that one line, and it kind of scared me.
    My Website

    "Circular logic is good because it is."

  3. #3
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,195
    Mathemeticians talk about the winner take last because loser takes last is a solved problem. Whoever goes first loses if the other player knows the solution.

  4. #4
    Registered User guesst's Avatar
    Join Date
    Feb 2008
    Location
    Lehi, UT
    Posts
    179
    Quote Originally Posted by DavidP View Post
    I was too lazy to read your code, but I read that one line, and it kind of scared me.
    I just mean that without my wife I'll stay up all night instead of going to bed at a reasonable time.

    Quote Originally Posted by abachler View Post
    Mathemeticians talk about the winner take last because loser takes last is a solved problem. Whoever goes first loses if the other player knows the solution.
    No, they talk about winner take last because it's easier and technically misere is just and extension of it. Compare here's what the best move function would look like playing the "normal" version:
    Code:
    int bestmove (int *bmoves, int *p, int nimber) {
      int c, d, nummoves, number;
    
      nummoves = 0;
    
      if (!nimber) {
        printf ("\nThe nimber is 0, which means there is no best move right now.");
        for (c = 0; c < MAXPILES; c++) if (p[c]) { /* random moves */
          nummoves ++; bmoves[c] = p[c] - rand() &#37; p[c];
        }
    
      } else { /* the nimber has a value, so we must have a move. Easy first */
        for (c = 0; c < MAXPILES; c++)
          if ((p[c] & nimber) == nimber) {
            nummoves ++;
            bmoves[c] = nimber;
          }
        if (nummoves)
          printf ("\nThere is/are %d relatively easy good moves.\n"
          "Hint: Look for the binary nimber within a pile, and take the nimber's "
          "number\nof pieces away from that pile.\n", nummoves);
    
        else {
          printf ("\nGood moves are hard to find here. Look at the row(s):\n");
          for (c = 0; c < MAXPILES; c++) for (d = 0; d < p[c]; d++)
          if (!(nimber ^ p[c] ^ d)) {
            nummoves++;
            bmoves[c] = p[c] - d; printf ("Row %d, ", c + 1);
          }
          printf ("\nRemember, to leave your opponent with a nimber of zero\n"
           "Good luck.\n");
        }
    
      }
    
      return nummoves;
    }
    The difference? I removed 17 lines of code and now it plays to take that last piece. The strategy is exactly the same, up until the end game. Playing misere means the strategy has to change right at the end, but the method of keeping control is exactly the same up to that point.

    Mathematicians are lazy, man. Thorough, but lazy. We'll sum up 20 pages of proof with "from here the solution is academic," which really means, "bugger all, it's going to take us 20 more pages to finish this right. You do it."

    What drives me crazy is that lazyness affected the vocabulary. I was under the impression that the misere version of nim was the way to play it, the way everyone played it. Then I run into the mathematical analysis of the game and suddenly the normal way of playing it (misere) is not what they called the normal play. So the variant gets to be called normal because it's solution is shorter.

    Sorry, going off on my own kind here.
    Last edited by guesst; 05-04-2008 at 04:18 PM.
    Type-ins are back! Visit Cymon's Games at http://www.cymonsgames.com for a new game every week!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. NIM in C++
    By mmiskand in forum C++ Programming
    Replies: 1
    Last Post: 11-14-2008, 11:14 AM
  2. nim game
    By mixalissen in forum C++ Programming
    Replies: 4
    Last Post: 04-30-2008, 04:32 PM
  3. C++ NIM with functions
    By Middlechild47 in forum C++ Programming
    Replies: 9
    Last Post: 11-20-2006, 01:22 AM
  4. does anyone have the game nim programed?
    By Unregistered in forum C++ Programming
    Replies: 0
    Last Post: 11-27-2001, 08:37 AM