2

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"));
}
  • Would prolog be a better choice of language? – Ed Heal May 15 '16 at 12:10
  • 1
    @DelaneyWarren, are you sure that the `move` within `negaMax2()` is different than the one in the struct? – abhishek_naik May 15 '16 at 12:45
  • 1
    @CodingBatman yeah it's definitely different. Although thank you for pointing that out because it is a bit unclear. I've changed it now for readability. – Delaney Warren May 15 '16 at 12:51
  • 1
    And @EdHeal Because it's a class given in c, I unfortunately don't really have much choice on the language used. – Delaney Warren May 15 '16 at 12:53
  • 2
    for ease of readability and understanding by us humans: 1) separate code blocks (for, if, else, while, do...while, switch, case, default) via a blank line. 2) consistently indent the code: indent after every opening brace '{'. un-indent before every closing brace '}'. Suggest using 4 spaces for each indent level as that is wide enough to be visible even with a variable width font. – user3629249 May 15 '16 at 18:49
  • This is literally my homework right now, lol. Thanks – Andrew Lalis May 19 '17 at 07:48

1 Answers1

2

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;
abhishek_naik
  • 1,287
  • 2
  • 15
  • 27