开发者

Is this implementation of the negamax algorithm correct

I'm trying to implement the negamax algorithm, and this is how I thought it should be:

public Move getBestMove(Board board){
 List<Move> possibleMoves = board.getPossibleMoves();
 Move optimalMove;
 int maxScore;
 forea开发者_如何学运维ch(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;
  }
 }
}

And the corresponding negamax function

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

Yeah I know it's not compiling but I'm just trying to pseudocode it a bit.

Edit

The calculateBoardFunction(Board board) will ALWAYS evaluate the board for the color that the best move is calculated for.

Also, i've tried to make it generic, so it works the same for every game (chess, reversi, go) etc... (but that's not part of the question)

Also I used the wikipedia's negamax pseudocode as an example. But using that code I >>think<< I could create the game tree very well, with the correct heuristics values. but the reason I have the code in the getBestMove function, is to figure out what move is actually the best.

But im not sure if I can do that.


This looks more or less right. There is a misprint (-sign instead of -colour), and you need to clone the board every time through the loop (or use unmakeMove, but then you don't need a clone in the first place). But apart from this, the logic looks correct.
In the real world, you would want to sort the moves somehow before trying them out. This can result in a huge speed-up, from all the beta cutoffs.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜