Является ли эта реализация алгоритма Negamax правильной

Question

Я пытаюсь реализовать алгоритм negamax, и я так и думал:

public Move getBestMove(Board board){
 List<Move> possibleMoves = board.getPossibleMoves();
 Move optimalMove;
 int maxScore;
 foreach(Move move in possibleMoves){
  Board newBoard = board.clone();
  newBoard.makeMove(move);
  int score = negamax(newBoard, DEPTH, Integer.MAX, Integer.MIN, 1);
  if (score > maxScore){
    optimalMove = move;
    maxScore = score;
  }
 }
}

и соответствующая функция negamax

public int negamax(Board board, int depth, int alpha, int beta, int sign){
 if(depth == null || board.getPossibleMovesNumber(colour) == 0){
  return calculateBoardFunction(board);
 }
 else{
  List<Move> possibleMoves = board.getPossibleMoves();
  foreach(Move move in possibleMoves){
   Board newBoard = board.clone();
   newBoard.makeMove(move);
   alpha = Math.max(alpha, -negamax(newBoard, depth-1, -beta, -alpha, -sign);
   if(alpha >= beta){
     break;
   }
  }
 return alpha;
}

Да, я знаю, что он не компилируется, но я просто пытаюсь немного псевдокодировать его.

Редактировать

CalculateBoardFunction (доска) ВСЕГДА оценивает доску по цвету, для которого рассчитан лучший ход.

Кроме того, я попытался сделать его универсальным, чтобы он работал одинаково для каждой игры (шахматы, реверси, го) и т. Д. (Но это не является частью вопроса)

Также в качестве примера я использовал псевдокод negamax из Википедии. Но используя этот код, я думаю, что << я мог бы очень хорошо создать дерево игры с правильными значениями эвристики. но причина, по которой у меня есть код в функции <code>getBestMove, состоит в том, чтобы выяснить, какой шаг на самом деле лучший.

Но я не уверен, смогу ли я это сделать.

Answer 1

Это выглядит более или менее правильно. Есть опечатка (-sign вместо -colour), и вам нужно каждый раз клонировать доску через цикл (или использовать unmakeMove, но тогда вам не нужен клон в первую очередь). Но кроме этого логика выглядит правильно.
В реальном мире вы бы хотели как-то отсортировать ходы, прежде чем испытывать их. Это может привести к огромному ускорению от всех бета-отсечек.