Search code examples
javascriptnode.jsartificial-intelligencechessminimax

Minimax algorithm doesnt go for mate in chess


My goal is to code a somewhat OK chess engine, in the following position it's a mate in 2 which the engine should easily find with its depth of 4-5.

Chess board with FEN: rr2k3/8/8/8/8/8/8/4K3 (black to play)

The first move the AI makes is Ra2 to trap the white king, the white king goes to f1 and instead of mating the AI moves the Rook to c2.

  var initial_depth = depth;
  var bestMove = null;
  var nodes = 0;
  var ret = await minimax(position, depth, alpha, beta, maximizingPlayer);
  console.log("nodes visited: " + nodes);
  return ret;
 
  async function minimax(position, depth, alpha, beta, maximizingPlayer) {
    nodes++;
    if (maximizingPlayer) {
      var validMoves = await getValidMoves(position, ArrtoFEN(position) + " w");
    } else {
      var validMoves = await getValidMoves(position, ArrtoFEN(position) + " b");
    }
    if (validMoves.length < 1 || depth == 0) {
      var eval = await getEval(position);
      return [eval, null];
    }
 
    if (maximizingPlayer) {
      var maxEval = Number.NEGATIVE_INFINITY;
      for (var i = 0; i < validMoves.length; i++) {
        var move = validMoves[i];
        
        var testbrd = makeMove(move, position)  //not the actual code. shortend for Readability
 
        
        var eval = await minimax(testbrd, depth - 1, alpha, beta, false);
        if (eval[0] > maxEval) {
          maxEval = eval[0];
          if (initial_depth == depth) {
            bestMove = move;
            console.log("current bestmove: " + bestMove);
          }
        }
        alpha = Math.max(alpha, eval[0]);
        if (beta <= alpha) {
          break;
        }
      }
      return [maxEval, bestMove];
    } else {
      var minEval = Number.POSITIVE_INFINITY;
 
      for (var i = 0; i < validMoves.length; i++) {
        var move = validMoves[i]; 
          
        var testbrd = makeMove(move, position)//not the actual code. shortend for Readability
 
        var eval = await minimax(testbrd, depth - 1, alpha, beta, true);
        if (eval[0] < minEval) {
          minEval = eval[0];
          if (initial_depth == depth) {
            bestMove = move;
            console.log("current bestmove: " + bestMove);
          }
        }
        beta = Math.min(beta, eval[0]);
        if (beta <= alpha) {
          break;
        }
      }
 
      return [minEval, bestMove];
    }
  }
}

Solution

  • This is because it sees that any move will win, and you don't have a condition that tells the engine that it is better to do mate in 1 move than in 5 moves. If at the end of a search find that you have 0 legal moves and you are in check, then you are checkmated. In this case you want to send back a checkmate score (large negative value) and add the ply from this. This way you will make it better to mate in fewer moves than in a larger amount of moves.

    I suggest you go for Negamax alogirthm in stead of minimax. It will mean much less code and much easier to debug.