c - Nim 的 Negamax 游戏出现问题

Question

我正在上我的第一个 AI 类(class)，并尝试在我的 c 代码中实现 NegaMax 算法。我正在使用这个算法来玩简单的 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;

您正在调用 undefined behavior这里。您正在尝试访问 eval 而 best 尚未初始化(它刚刚被声明)。

您应该考虑按照以下几行做一些事情:

State best;
best.eval = turn;