Search code examples
algorithmminimax

How can I make Minimax/Alpha-Beta pruning prioritize shorter paths?

I am having problems regarding my implementation of the minimax algorithm in a chess engine. How can I make the algorithm favor the shortest paths to the win?

Take this configuration of the board as an example:

enter image description here .

The best move here would be to move the queen on the last line, but if the algorithm has a higher depth of search it doesn't matter if the checkmate occurs "faster".

Solution

  • A few fairly straightforward changes:

    • Change the return type of the search function, so that instead of returning a pair like (move, q) where q is a measure of how good the move is, it returns a triple like (move, q, m) where m is the length of the sequence following that move.
    • Change the return statements to include the correct sequence length; either 0 for an immediate game end, or (m + 1) where m is the length of the followup sequence found by a recursive call.
    • Use the sequence length as a tie-breaker to compare moves with equal q; lower m is preferred.
    • If you are short-circuiting by returning a winning move as soon as one is found, change the condition for this so that only an immediately-winning move short-circuits.

    Note that this will generally make the algorithm less efficient, since you have to explore more branches after finding a winning move in case there is a quicker winning move in the unexplored branches.