How do I implement minimax with the chess.js node module

Question

I'm currently working on creating a chess engine using chess.js, chessboard.js, and the minimax algorithm. I eventually want to implement alpha-beta, but for right now, I just want to get minimax to work. It seems like the computer is thinking, but it usually just does Nc6. If I move the pawn to d4, it usually takes with the knight, but sometimes it just moves the rook back and forth in the spot that was opened up by the knight. If there is nothing for the knight to take, the computer moves the Rook or some other pointless move. My best guess is that all of the moves are returning the same valuation, and so it just makes the first move in the array of possible moves, hence the top left rook being a prime target. I should note that part of my confusion is around the way a recursive function works, and most of the stuff I've found online about recursive functions leaves me more confused than when I started.

I'm using Express.js with the chessboard.js config in public/javascripts as a boardInit.js that's included in the index.ejs folder, and when the user makes a move, a Post request is sent to /moveVsComp. It sends it to the server, where the app.post function for /moveVsComp tells chess.js to make the move that the player made.

After the player move is recorded, the computer calls the computerMoveBlack function.

Function call in the post request:

  let compMove = computerMoveBlack(3);
  game.load(currentFen)
  game.move(compMove)
  res.status(200).send({snapback: false, fen: game.fen()})

computerMoveBlack Function:

function computerMoveBlack(depth) {
  let bestMove = ['', 105];
  for (let move of game.moves()) {
    game.move(move)
    let value = minimax(move, depth-1, false)
    if (value < bestMove[1]) {
      bestMove = [move, value]
    }
    game.undo()
  }
  console.log(bestMove[0])
  return bestMove[0]
}

This function loops through all of the moves, and I was using this because it seemed like this was the best way to keep the best move instead of just returning a valuation of the current position.

Minimax Function:

function minimax(node, depth, maximizingPlayer) {
  let value = maximizingPlayer ? -105 : 105
  if (depth === 0 || game.game_over()) return getValuation()
  if (maximizingPlayer) {
    for (let move of game.moves()) {
      game.move(move)
      value = Math.max(value, minimax(move, depth-1, false))
      game.undo()
    }
    return value
  } else {
    for (let move of game.moves()) {
      game.move(move)
      value = Math.min(value, minimax(move, depth-1, true))
      game.undo()
    }
    return value
  }
}

getValuation Function:

function getValuation() {
  let evalString = game.fen().split(' ')[0];
  let score = 0;
  score += (evalString.split('r').length -1) * -5 || 0;
  score += (evalString.split('b').length -1) * -3 || 0;
  score += (evalString.split('n').length -1) * -3 || 0;
  score += (evalString.split('q').length -1) * -9 || 0;
  score += (evalString.split('p').length -1) * -1 || 0;
  score += (evalString.split('R').length -1) * 5 || 0;
  score += (evalString.split('N').length -1) * 3 || 0;
  score += (evalString.split('B').length -1) * 3 || 0;
  score += (evalString.split('Q').length -1) * 9 || 0;
  score += (evalString.split('P').length -1) || 0;
  return score;
}

I should note that I understand using a FEN in the valuation is very slow for this use case, but I'm not really sure what a better alternative would be.

Just as kind of a recap of the questions, I'm trying to figure out why it just makes the first move in the array every time, what is wrong with the format of my functions, and what a better way to get the valuation of a position is as opposed to string manipulation of the FEN.

Answer 1

I will point out a few suggestions below to help you on the way if you are just getting started. First I just want to say that you are probably right that all moves get the same score and therefore it picks the first possible move. Try to add some Piece Square Tables (PST) to your Evaluation function and see if it puts pieces on appropriate squares.

1. I would implement a Negamax function instead of Minimax. It is way easier to debug and you won't have to duplicate a lot of code when you later make more optimizations. Negamax is one of the standard chess algorithms.
2. It seems like you don't do the legal move generation yourself, do you know how the board is represented in the library that you use? Instead of using the FEN for evaluation you want to use the board (or bitboards) to be able to do more advanced evaluation (more on it further down).
3. The min/max value of -105/105 is not a good way to go. Use -inf and inf instead to not get into troubles later on.

Regarding the evaluation you normally use the board representation to figure out how pieces are placed and how they are working together. Chessprogramming.org is a great resource to read up on different evaluation concepts.

For your simple starting evaluation you could just start with counting up all the material score at the beginning of the game. Then you subtract corresponding piece value when a piece is captured since that is the only case where the score is changing. Now you are recalculating lots of things over and over which will be very slow.

If you want to add PST to the evaluation then you also want to add the piece value change for the moving piece depending on the old and new square. To try and sum up the evaluation:

1. Sum up all piece values at start-up of a game (with PST scores if you use them) and save it as e.g. whiteScore and blackScore
2. In your evaluation you subtract the piece value from the opponent if you capture a piece. Otherwise you keep score as is and return it as usual.
3. If using PST you change the own score based on the new location for the moved piece.

I hope it makes sense, let me know if you need any further help.