Negamax游戏的麻烦

Question

我正在学习我的第一个人工智能类，并尝试在c语言中实现NegaMax算法。我使用这个算法来玩Nim的简单游戏，在这个游戏中，每个玩家在他们的回合中删除1-3个匹配。电脑在这里自行其是。但是，我在实现方面遇到了困难。到目前为止，我似乎无法让状态对函数的每个递归调用进行更改。我得到一个无限循环，其中最佳值从-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;