# Chess AI Using Minimax and Alpha-Beta Pruning

I am working on a Chess AI using chess.js, and currently, it can run 3 layers in under 10 seconds, but 4 or more takes minutes. How can I optimize my current code to be able to run 4 or 5 layers, or do I have to implement a different algorithm.

Here is my code:

function startMinimax(depth, game, isMaximisingPlayer) {
var moves = game.moves({ verbose: true });
var bestEval = -9999;
var bestMove;
for (var i = 0; i < moves.length; i++) {
var move = moves[i];
game.move(move);
var value = minimax(depth - 1, game, -10000, 10000, !isMaximisingPlayer);
game.undo();
if (value >= bestEval) {
bestEval = value;
bestMove = move;
}
}
return bestMove;
}

function minimax(depth, game, alpha, beta, isMaximisingPlayer) {
if (depth === 0) {
return -evaluateBoard(game);
}
var moves = game.moves({ verbose: true });

if (isMaximisingPlayer) {
var bestEval = -9999;
for (var i = 0; i < moves.length; i++) {
game.move(moves[i]);
bestEval = Math.max(bestEval, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
game.undo();
alpha = Math.max(alpha, bestEval);
if (beta <= alpha) {
return bestEval;
}
}
return bestEval;
} else {
var bestEval = 9999;
for (var i = 0; i < moves.length; i++) {
game.move(moves[i]);
bestEval = Math.min(bestEval, minimax(depth - 1, game, alpha, beta, !isMaximisingPlayer));
game.undo();
beta = Math.min(beta, bestEval);
if (beta <= alpha) {
return bestEval;
}
}
return bestEval;
}
}

• You should at least weed off the transpositions. Too many move sequences lead to the same position, and you keep inspecting it over and over again. – vnp May 4 at 19:01
• I tried adding a transposition table, checking if the fen of any move was equal to one in the past, but it picked poor moves with it. – CannotCode May 4 at 19:04
• Then I am afraid something else was wrong. And BTW fen is not the best hash. – vnp May 4 at 19:06
• I'll try to implement it again. What would you recommend as a hash? Also, does anything else need to be stored beside the hash? – CannotCode May 4 at 19:31
• It is a huge topic. Start here – vnp May 4 at 19:33