% Listing 1: ngame.c

/* ngame.c */
/* Andrew Davison, June 1996 (ad@cs.mu.oz.au) */

/* Usage:
     ngame

   Nim consists of piles of sticks (or stones, etc) in rows. The
   user removes some sticks from a given row, then the computer
   does the same from a row it chooses, and so on.
   The winner is the player who removes the last stick.

   The computer employs a clever strategy based on summing the
   binary values of the stick numbers in each pile. However, it
   may lose if the player is equally clever.

   My source for this strategy was:
 "The Art of Prolog", by Sterling & Shapiro, 
 The MIT Press, 2nd ed., 1994, section 21.2.
*/

#include <stdio.h>
#include <string.h>

#define ROWS 5          /* number of rows */
#define ROW_STRT 1      /* number of sticks in first row */
#define ROW_CHG 2       /* number of extra sticks per new row */
#define COLS 4          /* max sticks in a row must be <= (2^COLS)-1 */
#define MAXLEN 120      /* max length of a string */

struct movement {
  int row;
  int remove_num;
};
typedef struct movement Move;

enum player_type {USER, COMPUTER};
typedef enum player_type Player;


void init_game(int sticks[], char *nm);
void display_game(int sticks[]);
void make_move(Player p, char *nm, Move m, int sticks[]);
void swap_player(Player *p);
int game_over(int sticks[]);
void give_result(Player p, char *nm);
void choose_move(int sticks[], Player p, Move *m);
void user_move(int sticks[], Move *m);
int legal_move(int sticks[], Move mv);

/* The computer's move */
void comp_move(int sticks[], Move *m);
void init_bsticks(int sticks[], int b_sticks[][COLS]);
void binary_val(int no, int b_sticks[]);
int safe(int b_sticks[][COLS]);
void any_move(int sticks[], Move *m);
void init_pbrow(int pbrow[], int sno);
int safe_now(int b_sticks[][COLS], int pbrow[], int rmove);


int main()
{
  int sticks[ROWS];    /* game data structure */
  Move mv;
  Player p = USER;
  char user_name[MAXLEN];

  init_game(sticks, user_name);
  printf("\nHello %s\n", user_name);
  display_game(sticks);
  do {
    choose_move(sticks, p,  &mv);
    make_move(p, user_name, mv, sticks);
    display_game(sticks);
    swap_player(&p);
  } while (!game_over(sticks));

  give_result(p, user_name);

  return 0;
}


void init_game(int sticks[], char *nm)
/* There are ROW_STRT sticks in the first row, with ROW_CHG
   extra sticks in each subsequent row */
{
  int r;
  int num = ROW_STRT;

  printf("Please enter your name: ");
  gets(nm);

  for (r = 0; r < ROWS; r++) {
    sticks[r] = num;
    num = num + ROW_CHG;
  }
}


void display_game(int sticks[])
{
  int r;
  
  printf("\nThe stick configuration is now:\n");
  for (r = 0; r < ROWS; r++)
    printf("Row %d: %d sticks\n", r, sticks[r]);
  putchar('\n');
}


void make_move(Player p, char *nm, Move m, int sticks[])
/* Remove sticks from the specified row */
{
  if (p == USER)
    printf("%s ", nm);
  else
    printf("The COMPUTER ");
  printf("removes %d stick(s) from row %d\n", m.remove_num, m.row);
  sticks[m.row] = sticks[m.row] - m.remove_num;
}


void swap_player(Player *p)
{
  if (*p == USER)
    *p = COMPUTER;
  else
    *p = USER;
}


int game_over(int sticks[])
/* A game is over when there are no sticks left */
{
  int r;

  for (r = 0; r < ROWS; r++)
    if (sticks[r] != 0)
      return 0;
  return 1;
}


void give_result(Player p, char *nm)
/* p has lost; the other player has won */
{
  if (p == USER)
    printf("I win -- bad luck %s.\n", nm);
  else
    printf("%s, you win -- I'm not feeling well.\n", nm);
}



void choose_move(int sticks[], Player p, Move *m)
{
  if (p == USER)
    user_move(sticks, m);
  else
    comp_move(sticks, m);
}


void user_move(int sticks[], Move *m)
{
  Move nmv;

  printf("Enter a row (0 to %d), and sticks to remove: ", ROWS-1);
  scanf("%d %d", &nmv.row, &nmv.remove_num);
  while (!legal_move(sticks, nmv)) {
    printf("Enter a row (0 to %d), and sticks to remove: ", ROWS-1);
    scanf("%d %d", &nmv.row, &nmv.remove_num);
  }
  (*m) = nmv;
}


int legal_move(int sticks[], Move mv)
{
  if (mv.row < 0) {
    printf("Error: row must be >= 0\n");
    return 0;
  }
  if (mv.row > (ROWS-1)) {
    printf("Error: row must be < %d\n", ROWS);
    return 0;
  }
  if (sticks[mv.row] < mv.remove_num) {
    printf("Error: row %d only contains %d sticks\n",
                              mv.row, sticks[mv.row]);
    return 0;
  }
  return 1;
}



/* The following code is for the computer's move. */


void comp_move(int sticks[], Move *m)
/* The safety of sticks[] is determined first by using b_sticks[].
   If it is safe then the computer selects any move. If sticks[] is
   unsafe then a search is made for a row r, number of sticks to
   remove remv, which makes it safe.

   The search is done by 'brute force'. Each row is examined. In
   a given row, an increasing number of sticks are considered for
   removal. If this makes the resulting sticks[] array safe then
   the search can finish. Otherwise the next row is tried.

   The algorithm is guaranteed to find a move to safety from an
   unsafe sticks arrangement.
*/
{
  int b_sticks[ROWS][COLS];
  int poss_brow[COLS];
  int r, remv;

  init_bsticks(sticks, b_sticks);
  if (safe(b_sticks))
    any_move(sticks, m);
  else {    /* unsafe position */
    for (r = 0; r < ROWS; r++)
      if (sticks[r] > 0)
        for (remv = 1; remv <= sticks[r]; remv++) {
          init_pbrow(poss_brow, sticks[r] - remv);
          if (safe_now(b_sticks, poss_brow, r)) {
            (*m).row = r;
            (*m).remove_num = remv;
            return;
          }
        }
    printf("Error: cannot find a safe move\n");   /* should not happen */
  }
}


void init_bsticks(int sticks[], int b_sticks[][COLS])
/* Initialise each b_sticks[] row with the binary value of the
   corresponding sticks[] row. 
*/
{
  int r;
  for (r = 0; r < ROWS; r++)
    binary_val(sticks[r], b_sticks[r]);
}


void binary_val(int no, int b_sticks[])
/* Binary number stored with increasing radix to the right.
   Fill the rest of the row with 0's */
{
  int c = 0;
 
  while (no != 0) {
    b_sticks[c] = no % 2;    /* remainder */
    no = no / 2;             /* integer division */
    c++;
  }
  for( ; c < COLS; c++)
    b_sticks[c] = 0;
}


int safe(int b_sticks[][COLS])
/* sticks[] is safe if the sum of the binary digits in b_sticks[]
   down every column is 0 (modulo 2)
*/
{
  int r, c, tot;

  for (c = 0; c < COLS; c++) {
    tot = 0;
    for (r = 0; r < ROWS; r++)
      tot = tot + b_sticks[r][c];
    if ((tot % 2) != 0)
      return 0; 
  }
  return 1;
}



void any_move(int sticks[], Move *m)
/* A reasonable 'any' move is to choose the first stick found */
{
  int r;
  for (r = 0; r < ROWS; r++)
    if (sticks[r] > 0) {
      (*m).row = r;
      (*m).remove_num = 1;
      return;
    }
}


void init_pbrow(int pbrow[], int sno)
/* Initialise pbrow[] with the binary value for sno */
{
  binary_val(sno, pbrow);
}


int safe_now(int b_sticks[][COLS], int pbrow[], int rpos)
/* The safety calculation is the same as in safe(), except
   that the binary value in pbrow[] is used in row rpos
   rather than the bsticks[] row.
*/
{
  int r, c, tot;

  for (c = 0; c < COLS; c++) {
    tot = 0;
    for (r = 0; r < rpos; r++)
       tot = tot + b_sticks[r][c];
    tot = tot + pbrow[c];
    for (r = (rpos+1); r < ROWS; r++)
       tot = tot + b_sticks[r][c];
    if ((tot % 2) != 0)
      return 0;
  }
  return 1;
}