CODEWITHSUNDEEP
algorithmminimax
BufferSpoofer
BufferSpoofer

Reputation: 108

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".

Upvotes: 0

Views: 377

Answers (1)

kaya3
kaya3

Reputation: 51063

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.

Upvotes: 1

Related Questions