I'm a new programmer currently coding a javascript alpha-beta pruning minimax algorithm for my chess engine, using Chess.js and Chessboard.js. I've implemented a basic algorithm with move ordering. 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 haven't implemented? My algorithm can't process anything deeper than depth 4 within reasonable time constraints. Thank you. P.S. the "tracking Eval" function just evaluates each specific move as a way to avoid doing a full evaluation of boards at leaf nodes, this optimization sped up my program by around 50%, but it's still slow right now.
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;
}
It's hard to say what optimizations you have made and what is reasonable since we only see a small part of your code. Your evaluation can be slow, your move ordering can be slow/incorrect, and to copy the board is also slower than to make and then unmake the move.
You can find lots of advice on how to speed up your algorithm here: https://www.chessprogramming.org/Search. Chessprogramming.org is a very good resource for developing your engine in general too.
I see two quick optimizations, before going further into other classical optimization.
Do not compute the evaluation of the board except when depth = 0. I assume that you compute the whole evaluation at every step, it's very time consuming and totally unnecessary.
Do not copy the board each time. It's also time consuming. Work with one board for the whole search, in which you make and unmake moves when you are doing the search. The pseudo-code for this is:
for move in moves:
board.do(move) #the original (not a copy) board has made the move
#Alpha-beta stuff like you did
board.undo(move) #restore the board