Chess AI MiniMax algorithm not working

Question

I have implemented the minimax algorithm here in my chess AI and I know it is not working properly because it just moves 1 piece back and forth over and over again.

getPieces(true) returns all white pieces in the current board state

getPieces(false) returns all black pieces in the current board state

ChessPiece.getAllPotentialMoves() pretty self explanatory, gets all possible moves for a particular piece

PieceMovements.move() moves a piece(p) to position(m -> represents a move)

PieceMovements.undo() undoes the previous movement

searchDepth is a variable that is first passed as the depth value when miniMax is first called, in other words, it is how far you want to search down. The reason for...

if(depth == searchDepth) {
    piece = p;
    move = m;
}

... is to record the piece and move to be made. I record this value at the top level of the search tree. piece and move represent the actual piece and move the algorithm thinks is the most efficient.

when miniMax is called, it looks like this: miniMax(searchDepth, false). False because the AI, black, is the minimiser.

Here is my method

public int miniMax(int depth, boolean maxi) {

    if(maxi) {
        if(depth == 0) return evaluateBoard();
        int max = -9999; //negative infinity
        for(ChessPiece p : getPieces(maxi)) for(Vector2 m : p.getAllPotentialMoves()) {
                PieceMovements.move(board, p, (int)m.x, (int)m.y);
                max = Math.max(max, miniMax(depth-1, !maxi));
                PieceMovements.undo();
                if(depth == searchDepth) {
                    piece = p;
                    move = m;
                }
            }
        return max;
    } else {
        if(depth == 0) return -evaluateBoard();
        int min = 9999; //positive infinity
        for(ChessPiece p : getPieces(maxi)) for(Vector2 m : p.getAllPotentialMoves()) {
                PieceMovements.move(board, p, (int)m.x, (int)m.y);
                min = Math.min(min, miniMax(depth-1, !maxi));
                PieceMovements.undo();
                if(depth == searchDepth) {
                    piece = p;
                    move = m;
                }
            }
        return min;
    }
}

and my evaluation function, which at the moment just takes the relative piece values of each piece and adds them up:

public int evaluateBoard() {
    int total = 0;
    for(ChessPiece[] row : board)
        for(ChessPiece piece : row)
            if(piece != null)
                switch(piece.getPiece()) {
                    case WPAWN:
                    case BPAWN:
                        total += RelativePieceValues.PAWN;
                        //a pawn about to be promoted takes on more value
                        if(piece.getPosition().y == 1 || piece.getPosition().y == 6)
                            total += 50; //50 + 10 = 60
                        break;
                    case WKNIGHT:
                    case BKNIGHT:
                        total += RelativePieceValues.KNIGHT;
                        break;
                    case WBISHOP:
                    case BBISHOP:
                        total += RelativePieceValues.BISHOP;
                        break;
                    case WROOK:
                    case BROOK:
                        total += RelativePieceValues.ROOK;
                        break;
                    case WQUEEN:
                    case BQUEEN:
                        total += RelativePieceValues.QUEEN;
                        break;
                    case WKING:
                    case BKING:
                        total += RelativePieceValues.KING;
                        break;
                }

    return total;
}

and the RelativePieceValues class:

public class RelativePieceValues{

//piece value constants
public static final int PAWN = 10;
public static final int KNIGHT = 30;
public static final int BISHOP = 30;
public static final int ROOK = 50;
public static final int QUEEN = 90;
public static final int KING = 900;
}

If you have any questions, please ask. Thankyou to any responses, I have been stuck on this for a while. I was wondering if there is actually something wrong with my mini max algorithm or my evaluation function or is there probably something else going wrong in my program that you cant see. Thanks.

At no point are you using the result of your minimax to decide which move to make. You seem to just be assigning every possible move you look at at the top of the recursion stack to an instance variable, meaning that the move you go with is always the last one considered. — mypetlion
– mypetlion, Commented Mar 14, 2018 at 23:03
Where in the algorithm then would I decide which the best move is? — Nalyd
– Nalyd, Commented Mar 15, 2018 at 8:10
The board evaluation is also kind of simple. If the search cannot find a piece to capture, how does it decide if one position is better than another? Moving back and forth can be a result of being satisfied with the current position (and know nothing about the stalemate rules). — Bo Persson
– Bo Persson, Commented Mar 15, 2018 at 13:06
How would I improve the evaluation function then? Anything you would recommend? — Nalyd
– Nalyd, Commented Mar 15, 2018 at 13:36
I also know there is negamax. The evaluation function, if using negamax takes into account only the pieces of one side(white or black). When using an evaluation function with the minimax algorithm, do i have to calculate a board value using ALL pieces on the board, both white and black? — Nalyd
– Nalyd, Commented Mar 15, 2018 at 18:24

eligolf · Accepted Answer · 2020-01-08 12:59:44Z

As pointed out in the answers, you are not using the results from your minimax function. Below is a working version that I developed in Python, hopefully you can translate it to java :)

This one is using alpha-beta pruning to increase performance.

Initial call with minimax function:

best_move, evaluation = minimax(board, 5, -math.inf, math.inf, True)

Minimax function itself. board.is_human_turn is used in the board class to determine who the player is. Then we get all possible moves for that player (children of the position).

Then it checks if we reached maximum depth or if it is game over in the position (draw or check mate).

For each player (maximizing and minimizing respectively), it goes through all children. It makes a board copy (to not alter with original board) and makes a move (one of the children) on the board. It then calculates evaluations in all nodes and returns the best move along with the evaluation.

def minimax(board, depth, alpha, beta, maximizing_player):

    board.is_human_turn = not maximizing_player
    children = board.get_all_possible_moves()

    if depth == 0 or board.is_draw or board.is_check_mate:
        return None, evaluate(board)

    best_move = random.choice(children)

    if maximizing_player:
        max_eval = -math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child)
            current_eval = minimax(board_copy, depth - 1, alpha, beta, False)[1]
            if current_eval > max_eval:
                max_eval = current_eval
                best_move = child
            alpha = max(alpha, current_eval)
            if beta <= alpha:
                break
        return best_move, max_eval

    else:
        min_eval = math.inf
        for child in children:
            board_copy = copy.deepcopy(board)
            board_copy.move(child)
            current_eval = minimax(board_copy, depth - 1, alpha, beta, True)[1]
            if current_eval < min_eval:
                min_eval = current_eval
                best_move = child
            beta = min(beta, current_eval)
            if beta <= alpha:
                break
        return best_move, min_eval

My evaluation function is currently very simple and only takes into account the piece values along with where they are on the board. For example, a knight is worth 320 originally, then you add or subtract depending on where it is positioned. See this link for more information: https://www.chessprogramming.org/Simplified_Evaluation_Function.

You can also implement an opening book so you get a good start in each game without having to spend time calculating positions.

Hope this helps!

Dear Eligolf, could you kindly have a look at this question: stackoverflow.com/questions/78404555/… ?

Collectives™ on Stack Overflow

Chess AI MiniMax algorithm not working

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related