Trouble with Negamax game of Nim

Question

I'm taking my first AI class and attempting to implement the NegaMax algorithm into my code in c. I am using this algorithm to play the simple game of Nim, where each player removes 1-3 matches on their turn. The computer plays against itself here. However, I'm having trouble with the implementation. So far, I cannot seem to get the state to change for each recursive call of the function. I get an infinite loop where the best value goes from -INFINITY to INFINITY (where infinity is 999999). So the program never terminates because the state never gets to 1. I have trouble with recursion in general so if anyone can give me some hints as to where I should go with my code it would be greatly appreciated.

typedef struct State{
   int m;
   int eval;
}State;


State negaMax2(int state, int turn, State *best){
int move;
/*terminal state?*/
if(state == 1){
    printf("Terminal state\n");
    best->eval = turn;
    return *best;
}
best->m = -INFINITY;
for(move = 1; move <= 3; move++) {
    if (state - move > 0) { /* legal move */
     int value = -1 * (negaMax2(state-move, turn, best)).m;
     if (value > best->move){
         best->eval = turn;
         best->m = value;
     }
    }
  }
return *best;
}


void playNim(int state) {
int turn = 0;
State *best;
best->eval = turn;
while (state != 1) {
  int action = (negaMax2(state, turn, best)).m;
  printf("%d: %s takes %d\n", state, 
       (turn==MAX ? "Max" : "Min"), action);
  state = state - action;
  turn = 1 - turn;
  }
 printf("1: %s looses\n", (turn==MAX ? "Max" : "Min"));
}

Answer 1

The culprit is this:

State *best;
best->eval = turn;

You are invoking undefined behavior here. You are trying to access eval while best has not yet been initialised (it is just declared).

You should consider doing something along the following lines:

State best;
best.eval = turn;