I’m a new programmer currently coding a javascript alpha-beta pruning minimax algorithm for my chess engine. I’ve implemented a basic algorithm with move ordering, and instead of evaluating each leaf node I’m “tracking” each move made along the way as to speed up the board evaluation. Currently, it’s evaluating around 14000 nodes for 8 seconds, which is way too slow. Is there something wrong with my algorithm or are there optimizations that I can implement? I was also thinking about making each branch search asynchronously, i.e. each of the x possible moves will run at the same time and compare the results when all branches have finished evaluating. Thank you.
function minimax(game, depth, distanceFromRoot, alpha, beta, gameEval) {//returns gameEval
if (depth === 0) {
nodeNum++;
if(game.turn() === 'b'){
return (-gameEval / 8);
}else{
return (gameEval / 8);
}
}
// run eval
var prevEval = gameEval;
var moves = game.moves();
moveOrdering(moves);
var bestMove = null;
var bestEval = null;
for (let i = 0; i < moves.length; i++) {
var gameCopy = new Chess()//dummy board to pass down
gameCopy.load(game.fen())
const moveInfo = gameCopy.move(moves[i])
var curGameCopy = new Chess()//static board to eval, before the move so we know which piece was taken if a capture occurs
curGameCopy.load(game.fen())
var curEval = trackingEval(curGameCopy, prevEval, moveInfo, moves[i]); //returns the OBJECTIVE eval for the current move for current move sequence
var evaluated = -minimax(gameCopy, depth - 1, distanceFromRoot + 1, -beta, -alpha, curEval);//pass down the current eval for that move
if (evaluated >= beta) {
return beta;
}
if (evaluated > alpha){
alpha = evaluated
bestMove = moves[i]
bestEval = evaluated;
if (distanceFromRoot === 0) {
bestEval = evaluated;
}
}
}
if(distanceFromRoot === 0){
setEval(-bestEval)
return bestMove;
}
return alpha;
}