Why doesn't my transposition table improve my move calculation time?

Question

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.

And here is my game with the transposition table hashing:

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?

Answer 1

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?