Minimax Algorithm with Alpha beta pruning takes over 2 minutes at depth 4

Question

I am trying to implement ChessAI engine using minimax alorigthm with alpha-beta pruning for my android app. The algorithm works fine uptil depth of 3 taking only 1-4 seconds, but as soon as I change the depth to 4, the best move calculation exceeds 2 minutes. Here are few things I tried but failed (chances are because of poor implementation).

1. Tried adding limited threading to improve performance but it worsened.
2. Instead of shuffling, tried sorting.

Please find the attached code for deeper analysis. Any help would be appreciated. Thanks

import java.util.ArrayList;
import java.util.Collections;
import java.util.Map.Entry;

public class ChessAI  {
    
    private Map map;
    private int recursions = 0;
    private boolean isThisPlayerTurn = false;
    private int depth = 3;
    
    public ChessAI(Map _map, int _depth)
    {
        map = _map;
        depth = _depth;
    }

    public Map getChessboardMap() {
        return map;
    }

    public Move getMove()
    {
        recursions = 0;
        long startTime = System.nanoTime();
        isThisPlayerTurn = map.isWhiteTurn();
        Move bestMove = minimaxRoot(depth, false);
        long totalTime = System.nanoTime() - startTime;
        double timeInSec = totalTime / 1e9;
        return bestMove;
    }
    
    public ArrayList<Move> getAllMoves()
    {
        ArrayList<Move> moves = new ArrayList<Move>();
        for(Entry<Pos, ArrayList<Pos>> entry : map.getAllReachableAllyPos().entrySet())
        {
            Pos from = entry.getKey();
            for(Pos to : entry.getValue())
            {
                moves.add(new Move(from, to));
            }
        }
        Collections.shuffle(moves);
        return moves;
    }
    
    private Move minimaxRoot(int depth, boolean isMaximising)
    {
        double bestValue = -10001;
        Move bestMove = null;
        for(Move move : getAllMoves())
        {
            map.movePiece(move.from.x,move.from.y, move.to.x,move.to.y, true, true);
            double value = minimax(depth - 1, -10000, 10000, isMaximising);
            map.undo(true);
            if(value > bestValue)
            {
                bestValue = value;
                bestMove = move;
            }
        }
        return bestMove;
    }
    static boolean[] depths = new boolean[5];
    private double minimax(int depth, double alpha, double beta, boolean isMaximising)
    {
        if(!depths[depth])
        {
            depths[depth] = true;
            System.out.println(depth + " " + isMaximising);
        }
        ++recursions;
        if(depth == 0)
            return isThisPlayerTurn ? map.evaluate() : -map.evaluate();
        
        if(isMaximising)
        {
            double bestValue = -10000;
            for(Move move : getAllMoves())
            {
                map.movePiece(move.from.x,move.from.y, move.to.x,move.to.y, true, depth != 1);
                bestValue = Math.max(bestValue, minimax(depth - 1, alpha, beta, !isMaximising));
                map.undo(true);
                alpha = Math.max(alpha, bestValue);
                if(beta <= alpha)
                    return bestValue;
            }
            return bestValue;
        }
        else
        {
            double bestValue = 10000;
            for(Move move : getAllMoves())
            {
                map.movePiece(move.from.x,move.from.y, move.to.x,move.to.y, true, depth != 1);
                bestValue = Math.min(bestValue, minimax(depth - 1, alpha, beta, !isMaximising));
                map.undo(true);
                beta = Math.min(beta, bestValue);
                if(beta <= alpha)
                    return bestValue;
            }
            return bestValue;
        }
    }

}

Answer 1

There are several things you can do.

Firstly, speed up move generation. The faster you can generate moves and make them, the more positions you will be able to look through. Look at your move generation and makemove function. Unless your board representation is very small, I would recommend "make" and "unmake" functions, rather than copying into a new board every time you want to make a move, if you aren't doing that already. In addition, check if you are doing any unnecessary looping. For example, looping through all your moves twice - first to separate legal from illegal moves, then to search them, is inefficient.

In addition, make sure you're not creating too many new objects. For example, consider representing moves as integers, and using bitwise operations such as shifts and "&" to represent move-from, move-to and move-type. Creating objects in Java is relatively inefficient - Objects are stored on the heap and have to be managed by the garbage collector, as opposed to ints which are stored on the stack and don't need garbage collector. You can read more about stack and heap allocation and the garbage collector here.

You may want to revamp your board representation. Most top chess engines, such as stockfish, komodo, etc. use bitboards. Essentially, it represents a chessboard as a 64 bit integer. This is very fast, as it takes advantage of bitwise operations to quickly generate, attack-maps, etc. The chess-programming wiki has some nice information about it, which you can read about here. They're very complicated, though, so many people use a 1-d or 2-d array of chars, ints or enums.

In addition, alpha-beta works better with good move ordering. There are a lot of heuristics that influence move ordering, but you should try evaluating captures first, using "MVV-LVA," which evaluates the material values of the attacker ("Least Valuable Attacker") versus the value of the victim ("Most Valuable Victim"). For example, PxQ is almost always going to be a good trade, but QxP may be a little more dubious.

I would reccommend using iterative deepening in combination with a transposition table. These are a little too complicated for right now, so I'll leave you a few links about hashing a board. Iterative deepening in conjunction with a transposition table can really boost speed quite a bit.

Iterative Deepening

Zobrist Hashing

Transposition Tables

Answer 2

This seems normal since the number of possible chess positions increases exponentially with depth.

A Chess AI usually have 2 bottlenecks: Finding all possible moves and evaluating the position. You need to figure out where your bottle neck is and try and optimize from there.

You can also read a lot about different optimization techniques and other general chess programming information at https://www.chessprogramming.org/Main_Page.

A few easy things to implement that would speed up your code significantly:

• Have a good board representation. Best is Bitboard, second best 1D array, and slowest a 2D array representation.
• Optimize your move generation functions given the board representation you are using.
• Use iterative deepening which enables better sorting
• After you have found all possible moves, sort them (https://www.chessprogramming.org/Move_Ordering)
• Start by only evaluating the static position. This can be done incrementally in the Make and Unmake move functions, then you won't have to loop over the board each time.

There are plenty of more techniques, some more advanced than others. To implement these, and the techniques above, it will be much easier for you if you use the Negamax algorithm instead. It is the same as Minimax, it removes all duplicate code which makes it easier to debug.