algorithm - 如何从最小最大算法中获得实际移动而不是移动值

Question

我目前正在为国际象棋编写带有 alpha beta 剪枝的 minimax 算法。

从我见过的所有示例中，minimax 算法将返回一个 int 值，该值表示最佳分数或最佳棋盘状态。

我的问题是我们如何才能返回与分数返回值关联的最佳着法？

例如，我在伪下面的 alphabeta() ...

public int alphabeta(int depth, Board b, int alpha, int beta, boolean maxPlayer) {
    if(depth == 0)
        return evaluateBoard(b);
    if(maxPlayer) {
        for(each of max player's moves) {
            // make move on a tempBoard
            int eval = alphabeta(depth - 1, tempBoard, alpha, beta, false);
            alpha = Math.max(alpha, eval);
            if(beta <= alpha) 
                break;
        }
        return alpha;
    }
    else {
        for(each of min's moves) {
            // make move on a tempBoard
            int eval = alphabeta(depth - 1, tempBoard, alpha, beta, true);
            beta = Math.min(beta, eval);
            if(beta <= alpha)
                break; 
        }
        return beta;
    }
}

在我的 minimax/alphabeta 实现中，我有一个 Board 对象代表棋盘，棋子可以在其上移动以代表不同的棋盘纹理/游戏状态。

我的函数 evaluateBoard(Board b) 接收一个 Board 并计算参数 Board 的状态值。

本质上，evaluateBoard() 为我提供了 alphabeta() 的最终 int 结果值，作为最佳着法的值。但是，我没有看到 evaluateBoard() 返回导致最终得分的移动的方法。即使我要返回一些包含分数值和棋子信息的对象，我也不确定我如何才能在树的顶部获得给我最终最好分数的棋子的信息。

有谁知道我如何访问/返回给出最佳分值的最佳着法的信息？ 我是否缺少 mini max 算法中的关键元素和/或我是否必须以不同方式实现 alphabeta()？

编辑:

例如，假设 minimax 从以下移动中返回最佳分数: e4、e5、nf3、nc6。我所拥有的将返回董事会情况的数值。我怎样才能返回“e4”？ E4 是导致最高值的移动。

谢谢。

Answer 1

minimax 算法通过探索可能移动的树来工作，即使您没有明确使用树也是如此。因此，您的函数只需要返回其值(value)之外的最佳着法即可。

你可以这样做:

ScoredMove alphabeta(Board board, String player, Move move) {
  board.applyMove(move);
  if (board.gameOver())
  {
    score = board.scoreForPlayer(player);
    return ScoredMove(score, move);
  }

  if (player == "player1") {
    next_player = "player2";
  } else {
    next_player = "player1";
  }

  ScoredMove best_move = null;
  for (next_move in board.movesForPlayer(next_player)) {
    ScoredMove scored = alphabeta(board, next_player, next_move)
    if (best_move == null || best_move.score < scored.score) {
      best_move = scored;
    }
  }
  board.removeMove(move);
  return best_move;
}