Chess AI Using Minimax and Alpha-Beta Pruning

Question

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

• vnp: 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.
• CannotCode: 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.
• vnp: Then I am afraid something else was wrong. And BTW fen is not the best hash.
• CannotCode: 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?
• vnp: It is a huge topic. Start here

Answer 1

1. Not handling draw cases

Draw cases isn't implemented, but checkmate is implemented.

2. Missing transposition table and some optimizations

Best hash algorithm: Zobrist hash, it exists in many chess libraries, or you can implement them yourself. Optimizations:

• Transposition Table
• Null Move Pruning
• Late Move Reductions
• Move Ordering
• Quiescence Search
• Alpha-Beta with all the basic cutoffs
• Selectivity