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.

Can you explain the main issue in more detail? Is the algorithm not returning the correct scores for the moves? You should try building a custom scenario where the number of moves is limited, and console log the score before bestScore gets edited. — Brother58697
– Brother58697, Commented Aug 2, 2022 at 6:43
It just returns really shitty moves. I'm not sure which part is the issue, but this is an example pgn: 1. e4 Nc6 2. d3 Rb8 3. Nc3 Ra8 4. Nf3 Rb8 5. d4 Ra8 6. d5 Rb8 7. dxc6 Ra8 8. cxb7 Rb8 9. bxc8=Q as you can see, it just starts alternating between Rb8 and Ra8 — Stryke
– Stryke, Commented Aug 2, 2022 at 7:18
How about this. Set the board state to only 2 kings and 2 pawns and have them so that the next good move is obvious (pawn takes other pawn). Test at a depth of 2. Log each score inside the the actual minmax's loops. Make your logs clear, by also logging the depth and the color. — Brother58697
– Brother58697, Commented Aug 2, 2022 at 8:24
The idea is to make sure that it's actually minmaxing. I was making a tic tac toe minmax a couple of months ago and my issues were mostly simple typos and not overall algortihm understanding. — Brother58697
– Brother58697, Commented Aug 2, 2022 at 8:25

LittleCoder · Accepted Answer · 2022-08-19 11:10:34Z

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;
 
};

eligolf · Accepted Answer · 2022-08-03 04:48:28Z

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.

Collectives™ on Stack Overflow

Issues implementing the Minimax Algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related