我的 tic tac toe negamax 算法输出错误

Question

我一直在学习电脑游戏，我在井字棋的极小极大算法上取得了成功。但 negamax 算法总是给出错误的举动。谁能告诉我我的代码有什么问题吗？

static negamax(board, alpha, beta, maxmizingPlayer) {
    const emptyCells = this.getEmptyCells(board);
    if (this.isGameOver(board) || emptyCells.length === 0) {
      const score = this.evaluate(board);
      return { score : maxmizingPlayer? score : -score };
    }
    let bestMove =  { score:  -Infinity };
    for (let i = 0; i < emptyCells.length; ++i) {
      const { x, y } = emptyCells[i];
      board[y][x] = maxmizingPlayer ? this.mySymbol : this.opSymbol;
      const move ={
        score: -this.negamax(board, -beta, -alpha, !maxmizingPlayer).score
      };
      board[y][x] = this.emptySymbol;
      move.x = x;
      move.y = y;
      if (move.score >= bestMove.score) {
        bestMove = move;
      }
      alpha = Math.max(alpha, bestMove.score);
      if (beta <= alpha) {
        break;
      }
    }
    return bestMove;
  }

static evaluate(board) {
    if (this.isWining(board, this.mySymbol)) {
      return Infinity;
    }
    if (this.isWining(board, this.opSymbol)) {
      return -Infinity;
    }
    return 0;
  }

Answer 1

我认为主要问题可能在于您否定基本情况下分数的方式。下面几点评论：

1. 在

   negamax

   中，您为基本情况返回

   { score: maxmizingPlayer ? score : -score }

   - 分数应始终被否定，并且不以

   maxmizingPlayer

   为条件。这样做的原因是因为 negamax 依赖于这样一个原则：对一个玩家有利的分数对另一个玩家同样不利。所以这可能应该是

   return { score: -score };

2. 不是一个交易破坏者，因为它是一致的，但你有一个错字

   maxmizingPlayer

   应该是

   maximizingPlayer

   （除非这是故意的。在这种情况下请忽略）：p

希望有帮助:)

更新（根据您下面的评论） （理论上）改变 for 循环不应该影响 negamax 算法的正确性。鉴于这确实可能意味着其他因素在起作用。

1. 首先要检查的是确保你的

   isWining

   函数正确识别所有获胜条件 - 你可能有，但总是可能存在一些隐藏的小错误（奖励：小打字错误，应该是

   isWinning

   ，如

   isWining

   暗示“正在喝酒”:p).

2. 第二件要检查的事情可能是评估订单移动。这不应该影响正确性，但如果更改评估移动的顺序会改变结果，则状态恢复或评估的方式可能会出现问题。

3. 当您恢复棋盘状态时，请确保恢复正确进行，并且在迭代之间不会意外保留任何状态信息

4. 最后一个建议可能是检查等效动作的随机性。如果有多个具有相同评估分数的动作，您的算法可能总是选择它遇到的第一个。这可能有助于解释为什么改变循环方向似乎可以提高性能。

我想这就是我现在所拥有的：S 如果这些都不起作用，那么请尝试仔细检查您的 alpha-beta 修剪逻辑，并确保最大化和最小化玩家的表现一致。如果这些似乎都没有帮助，我想您可能需要使用老式的方式来添加日志负载，以尝试了解它是如何评估和选择动作的。