2

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?

  • You might want to look at this. – boboquack Aug 26 '17 at 22:42
  • To the people voting to close: The community has decided that questions about chess programming are on-topic. This is also stated in the help center: Chess-specific questions about programming a chess engine or other chess software are welcome. – Herb Wolfe Sep 1 '17 at 14:58
2

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

  • Thanks! I wanted to also comment and note that move ordering is another implementation that I learned about and which works here. In that case, we order the moves on a more shallow depth, and search the branches of the move tree with the highest score first. In this case, this means that we search the checkmate position in one move before the one in two moves, and the alpha-beta pruning stops the searching from there. – keyan.r Aug 26 '17 at 16:32
  • This answer is incorrect, nonsense and just wrong. Evaluation function doesn't know "number of moves to mate" because it's just mate or not mate. You should add the information to the search as in Stockfish, please study my answer. – SmallChess Aug 27 '17 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.