Infinite recursion - Javascript minimax

Question

I am trying to create a chess AI using the chess.js library. I am using the minimax solution with Alpha-Beta pruning, but for some reason, when the program runs it continues even after the depth reaches 0. Can anyone tell me why?

var Buddha = function() {

  this.movehistory = 0;
  this.color = "b";
  this.opp = "w";


  this.minimax = function(board, depth, alpha, beta) {
    console.log(depth);
    if(depth === 0 || board.game_over() === true) {
      console.log("Depth == 0");
      return [this.eval_board(board), null]
    } else {
      if(board.turn() === this.color) {
        var bestmove = null

        var possible_moves = board.moves()
        for (index = 0; index < possible_moves.length; ++index) {
          var new_board = new Chess(board.fen());
          new_board.move(possible_moves[index])

          var mini = this.minimax(new_board, --depth, alpha, beta)
          var score = mini[0];
          var move = mini[1];

          if(score > alpha) {
            alpha = score;
            bestmove = possible_moves[index];
            if(alpha >= beta) {
              break;
            }
          }
        }
        return [alpha, bestmove]
      } else if(board.turn() === this.opp) {
        var bestmove = null

        var possible_moves = board.moves()
        for (index = 0; index < possible_moves.length; ++index) {
          var new_board = new Chess(board.fen());
          new_board.move(possible_moves[index])

          var mini = this.minimax(new_board, --depth, alpha, beta)
          var score = mini[0];
          var move = mini[1];

          if(score < beta) {
            beta = score;
            bestmove = possible_moves[index];
            if(alpha >= beta) {
              break;
            }
          }
        }
        return [beta, bestmove]
      }
    }
  }

  this.eval_board = function(board) {
    if(board.in_check()) {
      if(board.turn() == this.opp) {
        return Number.POSITIVE_INFINITY;
      } else {
        return Number.NEGATIVE_INFINITY;
      }
    } else if(board.in_checkmate()) {
      if(board.turn() == this.opp) {
        return Number.POSITIVE_INFINITY;
      } else {
        return Number.NEGATIVE_INFINITY;
      }
    } else if(board.in_stalemate()) {
      if(board.turn() == this.opp) {
        return Number.POSITIVE_INFINITY;
      } else {
        return Number.NEGATIVE_INFINITY;
      }
    }
  }

  this.move = function(board) {
    var bestmove = this.minimax(board, 1, Number.NEGATIVE_INFINITY, Number.POSITIVE_INFINITY)
  }

}

score 2 · Accepted Answer · answered Mar 07 '14 at 04:02

2

function minimax(board, depth, alpha, beta) {
  if(depth === 0 …) { …
    return …
  } else {
    …
    for (index = 0; index < possible_moves.length; ++index) {
      … minimax(new_board, --depth, alpha, beta)
//                         ^^
    …
    }
  }
}

Here you're decrementing the depth in a loop. Use depth <= 0 for the base case, and/or pass depth - 1 as an argument or put the decrement statement before the loop.

answered Mar 07 '14 at 04:02

Bergi

630,263
148
957
1,375

Why does the --depth and depth - 1 make a difference? Aren't they creating the same thing? – TimCPogue Mar 07 '14 at 04:04
No. `--depth` is a [prefix decrement operator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Arithmetic_Operators#--_.28Decrement.29) - the same as `depth -= 1` or `depth = depth - 1`. Don't use it if you don't know what it does :-) – Bergi Mar 07 '14 at 04:06
I'm sorry, I'm not very good at Javascript. I'm more of a python guy. I assumed that they both did the same thing. Thank you! – TimCPogue Mar 07 '14 at 04:07
Ah, I see, [python doesn't even have these](http://stackoverflow.com/questions/3654830/why-are-there-no-and-operators-in-python). – Bergi Mar 07 '14 at 04:09

Infinite recursion - Javascript minimax

1 Answers1