Facing performance problems implementing minimax for a chess game

Question

I am trying to implement minimax algorithm for a little chess game. Maybe my premise is wrong and this is not something that should be attempted. Is it?

The program works but there is a big performance issue:

Depth = 0, 1 or 2 the result is immediate.
Depth = 3 the result takes 15 seconds.
Depth = 4 - haven't got a result yet.

Here is my implementation:

private Move findBestMove(Chessboard chessboard, int depth,
        boolean maximizingPlayer) {
    if (depth == 0) {
        return new Move(chessboard.calculateHeuristicValue());
    } else {
        Move bestMove;
        if (maximizingPlayer) {
            bestMove = new Move(Integer.MIN_VALUE);
            for (Move possibleMove : findAllPossibleMoves(chessboard,
                    !(maximizingPlayer ^ whiteTurn))) {
                Move move = findBestMove(
                        possibleMove.getResultChessboard(), depth - 1,
                        !maximizingPlayer);
                if (move.getValue() > bestMove.getValue()) {
                    possibleMove.setValue(move.getValue());
                    bestMove = possibleMove;
                }
            }
        } else {
            bestMove = new Move(Integer.MAX_VALUE);
            for (Move possibleMove : findAllPossibleMoves(chessboard,
                    !(maximizingPlayer ^ whiteTurn))) {
                Move move = findBestMove(
                        possibleMove.getResultChessboard(), depth - 1,
                        !maximizingPlayer);
                if (move.getValue() < bestMove.getValue()) {
                    possibleMove.setValue(move.getValue());
                    bestMove = possibleMove;
                }
            }
        }
        return bestMove;
    }
}

Maybe there is a fault in the implementation of the algorithm or in the design of the objects or in their use. I cannot put my finger on it. So, I want to be sure that there is no major problem I overlook before trying to optimize the code or to tweak memory configuration of the program.

Note: no experience with memory profiling.

minimax is exponential. to reduce the amount of branches explored, you can use alphabeta pruning — njzk2
– njzk2, Commented Jul 3, 2015 at 19:38

Adam Stelmaszczyk · Accepted Answer · 2015-07-04 10:12:24Z

In chess there are 20 possibilities to make the first move (16 by pawns and 4 by knights).

For the sake of simplicity, let's assume that this is also true for the next moves.

For depth 1, MinMax considers only that 20 moves.
For depth 2, MinMax considers 20 moves and 20 answers to that moves, 400 possible moves, no problem.
For depth 3, MinMax considers 20^3 = 8.000 possible moves. Already 15 seconds on your machine.
For depth 4, MinMax considers 20^4 = 160.000 possible moves. That will take around 20 times longer than the previous one...

Simply the search space becomes too big - it grows exponentially with the input (depth) size. Time complexity is O(20^depth).

But, we don't have to search through all the space to find really good moves.

Alpha-beta pruning is popular optimization for MinMax.

If that's not enough, I would consider switching to totally other algorithm - Monte Carlo Tree Search (with UCT) for example.

Moves databases could also help - instead of computing the first moves you can have already prepared (pre-computed) gambits.

Famous Deep Blue who beat Kasparov in 1997 used them, you can check what else it used here.

Collectives™ on Stack Overflow

Facing performance problems implementing minimax for a chess game

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related