1

I have an alpha-beta pruning chess AI that I have implemented using chessjs and chessboardjs. Below is my AI algorithm - it includes move ordering on the first two depths, using the boardScore value at that position as the heuristic, and a hash table of past minimizing and maximizing values for FEN strings at different depths, as a transposition table:

var minAI = function(depth, alpha, beta) {
  if (minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'])
    return minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'];
  var options = game.ugly_moves();
  if (depth <= 0 || options.length === 0)
    return boardScore('b', game, depth);
  if (maxDepth - 1 === depth) //only perform move ordering on "shallow" iteration
    orderMoves(options, depth, false);
  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;
  }
  minimaxDict[game.fen() + ' [ ' + depth + ' minimizing ]'] = bestMin;
  return bestMin;
}

var maxAI = function(depth, alpha, beta) {
  if (minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'])
    return minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'];
  var options = game.ugly_moves();
  if (depth <= 0 || options.length === 0)
    return boardScore('b', game, depth);
  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;
  }
  minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'] = bestMax;
  return bestMax;
}

var bestAI = function() {
  var options = game.ugly_moves();
  if (!options.length) return;
  orderMoves(options, maxDepth, true);
  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)
      break;
  }
  game.ugly_move(options[moveIndex]);
  board.position(game.fen()); 
  if (game.in_checkmate())
    window.setTimeout(alert("Checkmate!"), 250);
  else if (game.in_draw())
    window.setTimeout(alert("Draw!"), 250);
  else if (game.in_stalemate())
    window.setTimeout(alert("Stalemate!"), 250);
  else if (game.in_threefold_repetition())
    window.setTimeout(alert("Threefold repetition!"), 250);
  else if (game.insufficient_material())
    window.setTimeout(alert("Draw by insufficient material!"), 250);
}

Here is my game running on maxDepth = 5 after 5 moves, without the transposition table hash being used. At the bottom of the picture are the setTimeout violations, which (though they aren't supposed to be used as timers) show the time it took for each move to be made.

enter image description here And here is my game with the transposition table hashing: enter image description here

Comparing the two move calculation durations, it doesn't look like my transposition table is helping too much, and is sometimes slowing me down. Is my implementation of the transposition table incorrect? Is the move ordering algorithm hampering me in some way?

2

Let's give a try:

  • Are you sure your fen() is correct? Don't assume, check how many times your TB table is being used. If the fen() is bugged, your TB would never be used. A possibility is that you add halfmove clock and fullmove number into FEN (please check).
  • Please note the fen() function is very slow. Your line minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]'] is wrong, because you are asking the computer to compute the FEN position twice. It's important to note computing an FEN position can only be done by looping through the whole board (64 squares). Everytime when we read a square, we must append a character to the existing (possibly immutable) memory array. Appending a character to memory is a super slow operation, because the computer might need to allocate new memory. Please ask on Stackoverflow if you want clarification. This is a very serious issue. Your TB implementation is meaningless unless you're sure fen() is fast, and no reallocation complexity.
  • Please note a much better implementation is zobrist hashing. Why wouldn't you use it?
  • Please check, double-check and triple-check if your TB is being used. Are you sure if (minimaxDict[game.fen() + ' [ ' + depth + ' maximizing ]']) is true? Anything could happen in a program.
  • How many times your TB value was returned in the search? 1%? 2%? Do you have a number?
  • Your TB has the depth information and min/max. I've never done it myself like this. Are you sure it makes sense?
| improve this answer | |
  • To points 1 and 4 - I am sure the TB is being used as I have done some logging. To point 5 - I haven't checked it out yet, but will do so. For point 6, since I'm storing the return value from the alpha-beta tree, the depth is required, but you are correct that "min/max" are not required. For points 2, 3, and 5 - I will take a look at these ASAP. I'll also ask on Stackoverflow as you mentioned for clarification. Thanks for your help! – keyan.r Aug 27 '17 at 16:33
  • Edit: Actually, it looks like, though the .fen() values are being accessed, they do include additional information! Perhaps this is the point 1 you are mentioning above - I'll give it a quick look ~ – keyan.r Aug 27 '17 at 16:58
  • @keyan.r Good. Now we're getting somewhere. : -) – SmallChess Aug 28 '17 at 2:14

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.