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

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())
else if (game.in_draw())
else if (game.in_stalemate())
else if (game.in_threefold_repetition())
else if (game.insufficient_material())
}
``````

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?

• 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 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.