Untitled

// Step 1: Move generation and board visualization
// We’ll use the chess.js library for move generation, and chessboard.js for visualizing the board.
// The move generation library basically implements all the rules of chess.
// Based on this, we can calculate all legal moves for a given board state.
// A visualization of the move generation function. The starting position is used as input and the output is all the possible moves from that position.
// Using these libraries will help us focus only on the most interesting task: creating the algorithm that finds the best move.
// We’ll start by creating a function that just returns a random move from all of the possible moves:
function makeRandomMove() {
  var possibleMoves = game.moves();

  // game over
  if (possibleMoves.length === 0) return;

  var randomIndex = Math.floor(Math.random() * possibleMoves.length);
  game.move(possibleMoves[randomIndex]);
  board.position(game.fen());
}

// Step 2: Position evaluation
// Now let’s try to understand which side is stronger in a certain position.
// The simplest way to achieve this is to count the relative strength of the pieces on the board using the following table:
// With the evaluation function, we’re able to create an algorithm that chooses the move that gives the highest evaluation:
// The only tangible improvement is that our algorithm will now capture a piece if it can.
function evaluateBoard() {
  var totalEvaluation = 0;
  for (var i = 0; i < 8; i++) {
    for (var j = 0; j < 8; j++) {
      totalEvaluation = totalEvaluation + getPieceValue(board[i][j], i, j);
    }
  }
  return totalEvaluation;
}

// Step 3: Search tree using Minimax
// Next we’re going to create a search tree from which the algorithm can chose the best move.
// This is done by using the Minimax algorithm.
// In this algorithm, the recursive tree of all possible moves is explored to a given depth, and the position is evaluated at the ending “leaves” of the tree.
// After that, we return either the smallest or the largest value of the child to the parent node, depending on whether it’s a white or black to move. (That is, we try to either minimize or maximize the outcome at each level.)
function minimax(depth, game, isMaximisingPlayer) {
  if (depth === 0) {
    return -evaluateBoard(game.board());
  }

  var possibleMoves = game.moves();

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

// Step 4: Alpha-beta pruning
// Alpha-beta pruning is an optimization method to the minimax algorithm that allows us to disregard some branches in the search tree.
// This makes the algorithm faster and more efficient.
// Here’s the final version of our algorithm:
function calculateBestMove() {
  var possibleMoves = game.moves();
  var