Беда с Negamax игрой Нима

Question

Я беру свой первый AI-класс и пытаюсь внедрить алгоритм NegaMax в мой код на c. Я использую этот алгоритм, чтобы играть в простую игру Nim, где каждый игрок удаляет 1-3 матча в свой ход. Компьютер играет против себя здесь. Однако у меня возникли проблемы с реализацией. Пока что я не могу заставить состояние меняться при каждом рекурсивном вызове функции. Я получаю бесконечный цикл, где наилучшее значение переходит от -INFINITY к INFINITY (где бесконечность равна 999999). Таким образом, программа никогда не завершается, потому что состояние никогда не достигает 1. У меня проблемы с рекурсией в общем, поэтому, если кто-то может дать мне несколько советов относительно того, куда я должен идти с моим кодом, это будет очень признательно.

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

Виновник в этом:

State *best;
best->eval = turn;

Вы вызываете неопределенное поведение здесь. Вы пытаетесь получить доступ eval в то время как best еще не было инициализировано (это только объявлено).

Вы должны подумать о том, чтобы сделать что-то вроде следующего:

State best;
best.eval = turn;