如何从mini-max算法中获取实际移动而不是移动值

提问者：小点点

如何从mini-max算法中获取实际移动而不是移动值

我目前正在为国际象棋编写一个带有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实现中，我有一个棋盘对象，它代表国际象棋棋盘，棋子可以在上面移动以表示不同的棋盘纹理/游戏状态。

我的函数评估板（板b）接受一个板，并计算参数板的板状态的值。

本质上评估板（）给我的alphabeta（）的最终int结果值的最佳移动的价值。然而，我没有看到一个方法，为评估板（）返回移动，导致最终得分。即使我返回一些包含分数值和信息的对象，我也不确定如何在树的顶部获得给我最后最好分数的信息。

有人知道我如何访问/返回给出最佳得分值的最佳移动信息吗？我是否错过了迷你最大算法中的一个关键元素和/或我必须以不同的方式实现alphabeta（）？

编辑：

例如，假设minimax从以下移动返回最佳分数：e4、e5、nf3、nc6。我所拥有的将返回电路板状态的数值。如何退回“e4”？E4是导致最大值的移动。

谢谢

共1个答案

匿名用户

极小值算法通过探索可能移动的树来工作，即使你没有显式地使用树。因此，所需要的就是函数除了返回值之外，还返回最佳移动。

您可以这样做：

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;
}