0

我正在尝试实现 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(Board board) 将始终评估棋盘的最佳移动计算颜色。

另外，我试图让它通用，所以它对每场比赛（国际象棋，黑白棋，围棋）等都一样......（但这不是问题的一部分）

我还以维基百科的 negamax 伪代码为例。但是使用我>>认为<<我可以使用正确的启发式值很好地创建游戏树的代码。但我在getBestMove函数中有代码的原因是要弄清楚什么动作实际上是最好的。

但我不确定我是否能做到这一点。

4

1 回答 1

1

这看起来或多或少是对的。有一个打印错误（-sign而不是-colour），并且每次循环时都需要克隆板（或使用unmakeMove，但首先不需要克隆）。但除此之外，逻辑看起来是正确的。
在现实世界中，您可能希望在尝试之前以某种方式对这些动作进行排序。这可能会导致所有 beta 截止值的巨大加速。

于 2011-05-20T11:03:52.917 回答