```% 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;

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;
}
```