Alpha-Beta Pruning returns mate in two instead of obvious mate in one

Question

I have an alpha-beta pruning chess AI that I have implemented using chessjs and chessboardjs. A friend of mine was playtesting it and came across the following position:

7r/ppp1k1rp/8/8/7K/4qb2/8/8 b - - 0 1

1... Qh6#
(1... Rhg8 2. Kh3 Qh6# (2... Rh8 Qh6))

In the position, black has a clear mate in 1 with Qh6. However, my alpha-beta algorithm, which is set to depth 4, first evaluates Rg8 (as it is the first move in the game.ugly_moves() array from chessjs). With Rg8, black still has mate in two, with white playing Kh3 and black playing Qh6. Thus, alpha and beta will both equal the "checkmate score", beta<=alpha satisfies, and the program returns, pruning the mate in one solution. Also, after playing Rg8, Kh3, black evaluates the board again, looking at Rh8 first, and yet again sees mate in two! (Either Kh2 or Kh4, then Qh6) and then the cycle continues (i.e. the AI plays Rg8, Rh8 until threefold repetition). Basically, in this position, I am always getting a draw instead of an obvious win.

Below is my alpha-beta implementation of this algorithm, in Javascript:

var minAI = function(depth, alpha, beta) {
  var options = game.ugly_moves();
  if (depth <= 0 || options.length === 0)
    return boardScore('b', game);

  var bestMin = 99999;
  for (var i = 0; i < options.length; i ++)
  {
    game.ugly_move(options[i]);
    if (game.in_threefold_repetition())
    {
      game.undo();
      continue;
    }
    bestMin = Math.min(bestMin, maxAI(depth - 1, alpha, beta));
    beta = Math.min(beta, bestMin);
    game.undo();
    if (beta <= alpha)
      break;
  }
  return bestMin;
}

var maxAI = function(depth, alpha, beta) {
  var options = game.ugly_moves();
  console.log("in maxAI");
  if (depth <= 0 || options.length === 0)
    return boardScore('b', game);
  var bestMax = -99999;
  for (var i = 0; i < options.length; i ++)
  {
    game.ugly_move(options[i]);
    if (game.in_threefold_repetition())
    {
      game.undo();
      continue;
    }
    bestMax = Math.max(bestMax, minAI(depth - 1, alpha, beta));
    alpha = Math.max(alpha, bestMax);
    game.undo();
    if (beta <= alpha)
      break;
  }
  return bestMax;
}

var bestAI = function() {
  var options = game.ugly_moves();
  if (!options.length) return;
  var bestScore = -99999;
  var moveIndex = -1;
  var alpha = -99999;
  var beta = 99999;
  for (i = 0; i < options.length; i++)
  {
    game.ugly_move(options[i]);
    var moveScore = minAI(maxDepth - 1, alpha, beta);
    if (moveScore > bestScore)
    {
      moveIndex = i;
      bestScore = moveScore;
      alpha = Math.max(alpha, bestScore);
    };
    game.undo();
    if (beta <= alpha)
    {
      console.log("we've been beta blocked");
      console.log(alpha);
      console.log(beta);
      break;
    }
  }
  game.ugly_move(options[moveIndex]);
  board.position(game.fen()); 
  if (game.in_checkmate())
    window.setTimeout(alert("checkmate!"), 250);
}

And here is how I give the board a score for a player (either 'w' for white, or 'b' for black):

var value = function(piece, player, i, j)
{
  if (piece === 'r') return (500 + 
    (player === 'w' ? rookGridWhite[i][j] : rookGridBlack[i][j]));
  else if (piece === 'n') return (320 + 
    (player === 'w' ? knightGridWhite[i][j] : knightGridBlack[i][j]));
  else if (piece === 'b') return (330 + 
    (player === 'w' ? bishopGridWhite[i][j] : bishopGridBlack[i][j]));
  else if (piece === 'k') return (0 + 
    (player === 'w' ? kingGridWhiteStart[i][j] : kingGridBlackStart[i][j]));
  else if (piece === 'q') return (900 + 
    (player === 'w' ? queenGridWhite[i][j] : queenGridBlack[i][j]));
  else if (piece === 'p') return (100 + 
    (player === 'w' ? pawnGridWhite[i][j] : pawnGridBlack[i][j]));
}

var boardScore = function(player, game) {
  if (scoreDict[game.fen() + ' [' + player + ']'])
    return scoreDict(game.fen() + ' [' + player + ']');
  if (game.turn() === player && game.in_checkmate())
    return -99999;
  else if (game.turn() !== player && game.in_checkmate())
    return 99999;
  var scoreWhite = 0;
  var scoreBlack = 0;
  for (var i = 0; i < 8; i ++)
  {
    for (var j = 0; j < 8; j ++)
    {
      var square = game.board()[i][j]
      if (square && square["color"] === 'w')
        scoreWhite += value(square["type"], player, i, j);
      else if (square && square["color"] !== 'w')
        scoreBlack += value(square["type"], player, i, j);
      if (scoreWhite <= 1100 || scoreBlack <= 1100)
      {
        kingGridWhiteStart = kingGridWhiteEnd;
        kingGridBlackStart = kingGridBlackEnd;
      }
    }
  }
  var posScoreWhite = scoreWhite - scoreBlack;
  scoreDict.push({
      key:   game.fen() + ' [w]',
      value: posScoreWhite
  });
  var posScoreBlack = scoreBlack - scoreWhite;
  scoreDict.push({
      key:   game.fen() + ' [b]',
      value: posScoreBlack
  });
  return (player === 'w' ? posScoreWhite : posScoreBlack);
} 

The "grids" referred to above are 2D position-value tables as given in the link below: https://chessprogramming.wikispaces.com/Simplified+evaluation+function

I reversed the arrays given in that link for black's evaluations, and used the kingGridStart arrays until an endgame condition is reached, in which case I use the kingGridEnd arrays.

I am not sure how to go about fixing this. Did I understand why my alpha beta program is failing, or is there another reason I am not aware of?

Answer 1

Add the depth information to the 99999. Let's look at Stockfish:

https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp

This block returns mate if mated_in is true.

if (!moveCount)
        bestValue = excludedMove ? alpha
                   :     inCheck ? mated_in(ss->ply) : DrawValue[pos.side_to_move()];

Let's check the mated_in function:

https://github.com/official-stockfish/Stockfish/blob/master/src/types.h

Please note Stockfish returns checkmate plus depth. That'd solve your problem.

inline Value mated_in(int ply) {
  return -VALUE_MATE + ply;
}

Answer 2

Well, there are two problems with your algorithm:

1. You don't treat draw (by whatever rule) in any way, meaning your AI will stubbornly run against a wall trying to keep the best possible position even if sacrificing a bit is likely to lead to a better outcome than draw.

2. You treat all moves leading to mate as equal. But as you found out, they aren't, which should be reflected in your code. So the evaluation should be a discriminated union:

   • Number of Moves to mate, OR
   • heuristic evaluation of relative strength of players positions

You might be able to map it to a single value, with abs(value) < MATE for the first, and BIG_VALUE - abs(value) for the number of moves to mate otherwise.