4
\$\begingroup\$

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;
  }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ 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. \$\endgroup\$ – vnp May 4 at 19:01
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – CannotCode May 4 at 19:04
  • \$\begingroup\$ Then I am afraid something else was wrong. And BTW fen is not the best hash. \$\endgroup\$ – vnp May 4 at 19:06
  • \$\begingroup\$ 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? \$\endgroup\$ – CannotCode May 4 at 19:31
  • \$\begingroup\$ It is a huge topic. Start here \$\endgroup\$ – vnp May 4 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.