CODEWITHSUNDEEP
algorithmartificial-intelligenceminimax
ipsec
ipsec

Reputation: 680

Minimax: what to do with equal scores in endgame?

As far as I understood, the Minimax algorithm in its simplest form works the following way: traverse the game tree bottom-up and if it's the player's turn, assign the maximum score of all child nodes to the current node, else the minimum score. Leaves are scored according to the game output, let's say +1 for win, 0 for draw, -1 for loss. Finally choose the move which leads to the node with the highest score.

Of course it is impractical to traverse the whole game tree, so a heuristic is used. But assume we are near the end of the game. Then I have found some problems with this simple approach.

For example, we are playing chess and the player (playing white) has reached this position: Chess position, mate in one

It is the players turn. So there is a mate in one with Qg7, the node for Qg7 thus gets a score of 1. But for instance, Ke1 is also a legal move. The only reply is c5, then Qg7# is still available. And because Qg7 gets a score of 1, so does c5, so does Ke1.

So we have at least two moves with a score of 1 (Ke1 and Qg7). Let's say the algorithm considers king moves first and chooses the first move with the highest score. That would mean, that in this position, the player would not checkmate the opponent, but would do random King moves until the opponent could actually prevent the checkmate (with queening the pawn).

The fundamental problem is, that a checkmate in one (Qg7) has the same score as a checkmate in two (Ke1), so there is no reason for the player, to actually go for the checkmate in one.

This can be prevented with a simple modification to the Minimax algorithm: in case of equal score, choose the shorter path to the position with this score. So a checkmate in one would be prefered.

My question is: I have not found any mention of this in any Minimax-related source, so is there some misunderstanding of Minimax on my part? If not, is this the usual way to solve this or are there superior ways?

Upvotes: 2

Views: 1097

Answers (1)

Bernhard Barker
Bernhard Barker

Reputation: 55589

I'm pretty sure you understand minimax correctly.

The thing I would probably do is to simply pass down the current distance in the minimax function, and weight the wins / losses according to that. A faster win (to reduce the possibility of unseen situations) and a slower loss (to allow for mistakes by the opponent) should generally be preferred. Whether the win is 1, or any positive value, it doesn't matter too much - it will still get picked as better than 0 or -1.

If you have a win be the largest possible value in your heuristic - you can still do something similar - just weight it by increasing or decreasing it a little, but still have it be larger than all other non-win values.

For your example, it probably doesn't really matter, as, when the pawn gets close to promoting, you'd detect that a draw is coming and then you'd make the winning move. But it can certainly be a problem if:

  • There's a sequence of inevitable moves beyond the search depth that results in a worst outcome for you (which is a pretty common problem with minimax, but if it's likely avoidable, it's obviously better to do so)
  • There's a time constraint on your side
  • You don't cater for all draw conditions (e.g. 3 repeated positions)

Upvotes: 1

Related Questions