Как получить фактическое перемещение, а не значение перемещения из алгоритма мини-макс.

В настоящее время я пишу минимаксный алгоритм с альфа-бета-обрезкой для шахмат.

Из всех примеров, которые я видел, минимаксный алгоритм вернет значение int, которое представляет лучший результат или состояние доски, полученное в результате наилучшего хода.

Мой вопрос: как мы можем вернуть лучший ход, связанный с возвращаемым значением счета?

Например, моя alpha() в псевдониме ниже...

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

В моей реализации минимакса/алфавита у меня есть объект Board, который представляет шахматную доску, и фигуры могут перемещаться по ней, чтобы представлять различные текстуры доски/состояния игры.

Моя функция evaluateBoard(Board b) принимает плату и вычисляет значение параметра Board для состояния платы.

По сути, оценкаBoard() дает мне окончательное значение int-результата alpha() для значения лучшего хода. Однако я не вижу способа для оценкиBoard() вернуть ход, который привел к окончательному счету. Даже если бы я вернул некоторый объект, содержащий значение очков и информацию о фигурах, я не знаю, как я мог бы получить информацию о фигуре на вершине дерева, которая дала мне окончательный лучший результат.

Кто-нибудь знает, как я могу получить доступ/вернуть информацию о лучшем ходе, который дает наилучшее значение очков? Мне не хватает ключевого элемента в алгоритме мини-макс и/или мне нужно реализовать alpha() по-другому?

ИЗМЕНИТЬ:

Например, предположим, что минимакс возвращает лучший результат для следующих ходов: e4, e5, nf3, nc6. То, что у меня есть, вернет числовое значение ситуации на доске. Как я могу вернуть "e4"? E4 — это ход, который приводит к наибольшему значению.

Спасибо.


algorithm chess minimax alpha-beta-pruning
person Rohan    schedule 19.07.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Минимаксный алгоритм работает, исследуя дерево возможных ходов, даже если вы явно не используете дерево. Итак, все, что нужно, — это чтобы ваша функция возвращала лучший ход в дополнение к его значению.

Вы можете сделать что-то вроде этого:

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;
}
person azani    schedule 19.07.2014
comment
Моя реализация технически не использует дерево. Например, если я установил глубину 2: я просматриваю каждый ход max, играю этот ход на временной доске и передаю эту доску следующему вызову alpha. Следующий вызов alphabeta будет рассматривать каждый ход min на основе хода max на доске, которая была пройдена. По сути, для каждого вызова alphabeta я играю ход на доске и перемещаю его вперед. Я не уверен в том, что вы пытаетесь передать с помощью ScoredMove(evaluateBoard(board), last_move). Скажем, наилучшее значение, возникающее из минимакса, это: e4, e5, nf3, nc6. Как вернуть е4? - person Rohan; 19.07.2014
comment
Дерево - это разные пути, по которым может пойти игра. Допустим, вы пасуете на доске и есть 2 хода: е3, е4. Таким образом, вы применяете ход e3 к своей доске и коллируете на ней alpha. Alphabeta возвращает объект, который содержит счет и некоторый последующий ход. Итак, вы следите за е3 и счетом и пробуете с е4. Вы видите, что e4 лучше. Таким образом, вы отбрасываете e3 и счет и возвращаете e4 и его счет, поскольку e4 — лучший ход. Имеет ли это смысл? - person azani; 19.07.2014