CODEWITHSUNDEEP
javaperformancerecursionartificial-intelligenceminimax
Limbo Exile
Limbo Exile

Reputation: 1351

Facing performance problems implementing minimax for a chess game

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:

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.

Upvotes: 1

Views: 979

Answers (1)

Adam Stelmaszczyk
Adam Stelmaszczyk

Reputation: 19837

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.

Upvotes: 4

Related Questions