Issues implementing the Minimax Algorithm

Question

I've been trying to implement a Minimax algorithm for a simple chess bot and I feel I understand the basics and general principles behind it, but my code isn't really working and I'm trying to figure out why.

This is my function for generating the boardScore.

const boardScore = (fen) => {
    // fen = rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1
    // caps are for white
    // white is maximizing player
    const pieceWorth = {
      p: -1,
      P: 1,
      k: -3,
      K: 3,
      b: -3,
      B: 3,
      r: -5,
      R: 5,
      q: -3,
      Q: 3,
      k: -99999,
      K: 99999,
    };
    const pieces = fen.split(" ")[0].split("");
    const score = 0;
    for (const piece in pieces) {
      score += pieceWorth[pieces[piece]] || 0;
    }

    if (game.turn() === "b" && game.in_checkmate()) score += 99999999;
    if (game.turn() === "w" && game.in_checkmate()) score -= 99999999;

    return score;
  };

This is my code for the root minimax function that's called. Currently I'm only trying to make it work for the black pieces (the AI's turn)

const minimaxRoot = (game, depth) => {
    // checking for black - minimizing player
    const minUtility = Infinity;
    let bestMove = null;

    const moves = game.moves();
    for (let i = 0; i < moves.length; i++) {
      game.move(moves[i]);
      let score = minimax(game, depth - 1);
      if (score < minUtility) {
        minUtility = score;
        bestMove = moves[i];
      }
      game.undo();
      console.log(minUtility);
      return bestMove;
    }
  };

And this is my minimax algorithm.

// white is maximizing player
  const minimax = (game, depth, white) => {
    console.count();
    if (depth === 0) {
      return boardScore(game.fen());
    }

    const moves = game.moves();

    if (white) {
      let bestScore = -Infinity;
      for (let i = 0; i < moves.length; i++) {
        game.move(moves[i]);
        let score = minimax(game, depth - 1, false);
        bestScore = Math.max(bestScore, score);
        game.undo();
      }
      return bestScore;
    } else {
      let bestScore = Infinity;
      for (let i = 0; i < moves.length; i++) {
        game.move(moves[i]);
        let score = minimax(game, depth - 1, true);
        bestScore = Math.min(bestScore, score);
        game.undo();
      }
      return bestScore;
    }
  };

This is how I'm calling the function, which happens when I make a move.

const blackMove = () => {
    game.move(minimaxRoot(game, 3));
    setPosition(game.fen());
  };

Any help would be appreciated. I've been banging my head working on this for the better part of 2 days and have made very little progress. Most of the examples I've seen include some form of alpha-beta pruning or transposed tables or move-ordering and it makes it more complicated which gives me trouble understanding.

Answer 1

First of all, do not use the minimax algorithm. It is inefficient compared to alpha-beta. You should use Alpha Beta in a NegaMax framework for more simplicity.

Note with NegaMax : the evaluation function should be relative to the side to move.

Then, your evaluation function is only based on material balance, it is not enough to have a decent playing style. Two good (and simple) pages about evaluation :
https://www.chessprogramming.org/Simplified_Evaluation_Function
https://www.chessprogramming.org/PeSTO%27s_Evaluation_Function

For more complex/advanced search implementations :

• the MiniMax and AlphaBeta algorithms are pretty well explained here

• transposition tables are well explained here and the Zobrist Hashing here. The (simplified) idea is to not (wast time to) search position previously searched, we prefer to store their score.

• Move Ordering is the simple fact that the performance of AlphaBeta is dependent of the order of moves : it will be quicker if it has the best moves to search first. So we approximate the move order to pass in alphaBeta (ex QxP is not good as PxQ => search good captures first).

• Also, to have a decent chess in a chess engine, it is essential to have a Quiescent Search, to avoid horizon effect.

I've implemented all this stuff in a (I think) pretty well commented chess engine in JavaScript here.

I think this should be a working code for you of the AlphaBeta algorithm in a NegaMax fashion :

const alphaBeta = (game, depth, white, alpha=-Infinity, beta=Infinity) => {
    console.count();
    if (depth === 0) {
        var view = white ? 1 : -1;
        return view * boardScore(game.fen());
    }

    const moves = game.moves();

    let bestScore = -Infinity;
        for (let i = 0; i < moves.length; i++) {
                game.move(moves[i]);
            let score = -alphaBeta(game, depth - 1, !white, -beta, -alpha);
            game.undo();
            if( score >= beta ) {
                return beta;   //  fail hard beta-cutoff
            }
            if( score > alpha ) {
                alpha = score; // alpha acts like max in MiniMax
            }
        }

    return alpha;
 
};

Answer 2

When it alternates between 2 moves it most often mean that it picks the first move in the list and doesn't fins a better move.

The problem here isvery common and it has to do with your evaluation function. You are always returning a negative value for black, even when it is blacks turn in the minimax loop (and opposite for white). You need to return -score if it is blacks turn to move, and score when it is whites turn. If there are no other issues in your minimax loop then this should solve your problem.

Another thing you will get an issue with later is that you are not checking for checkmate or draw in your minimax function. Where you check if depth == 0 you also need to check if game is over in any way, and then return, otherwise it will keep calculating even when game is over which will yield very strange results.