Why does Min-Max algorithm delays a good move indefinitely?

Question

Consider a simple chess example:

Q is white Queen.

K, R is black King and black Rook respectively.

  A B
1 . Q
2 . .
3 K .
4 . .
5 . .
6 R .
7 . .
8 . R

1,2...8 is the rank and A and B are the files of the chessboard.

Assume the king can only move horizontally for this example.

Here, if we search to depth 0, the best move should be Qxb8 (queen takes rook on B8)

But if we search for depth 2, then one line goes:

1. Qa1+ Kb3 2. Qxa6 (evaluation of the position +100 as rook is taken)

Second line:

1. Qxb8 Ra4 2. Qb1 (evaluation of the position +100 as rook is taken)

And since both have the same evaluation we select the first variation and play Qa1+ and let's say opposing player plays Kb3.

And now, if we again search to depth 2, same situation arise:

One line:

1. Qb1+ Ka3 2. Qxb8 (evaluation of the position +100 as rook is taken)

Second line:

1. Qxa6 Rb4 2. Qa1 (evaluation of the position +100 as rook is taken)

And again since both lines have the same evaluation we select the first variation and play Qb1+ and let's say opposing player plays Ka3.

And this will keep repeating and the queen will never capture the rook and just keep checking the king in the hope of capturing the rook in the next move but again repeats the same idea.

I hope this example makes it much clear what I am trying to say.

Answer 1

This is because you are not using a discount factor in your search.

A discount factor $\gamma$ is a number between 0 and 1. The discount factor describes the preference of an agent for current rewards over future rewards. When $\gamma$ is close to 0, rewards in the distant future are viewed as insignificant. When $\gamma$ is 1, discounted rewards are exactly equivalent to additive rewards, so additive rewards are a special case of discounted rewards.

The basic problem is that you are valuing taking the rook in the next move the same as if you took the rook in this move. This is not always correct, and can get you stuck like you've seen. You need to set a discount factor of the value of the next move to something like $\gamma =$ 0.9, this way your queen will value taking the rook sooner more highly. This gets multiplied by the expected reward of the next move. See Russel & Norvig's "Artificial Intelligence: A Modern Approach" Section 17.1 for more on discounted rewards.

There is another common case you'll come across if you work through Berkley's AI labs. Where pac man will never eat the last dot because it thinks it can always eat it in the next move so the game never ends.

Answer 2

In a game-theoretical sense, both of the moves you describe are equally good in the scenarios you describe, so the algorithm is "correct" in that it doesn't matter which move it picks -- you do not explicitly encode a preference for faster wins (or faster gains of $+100$) over slower scores.

Introducing a discount factor to explicitly encode such a preference, as described in ryan's answer, can be a solution... but it's not very common in game AI / minimax / alphabeta search literature, and it can also be detrimental in slightly different scenarios. For example, if we can get a score of $+100$ in one ply, or a score of $+101$ in the second ply, we would generally prefer the path leading to that delayed $+101$... but a common choice of a discount factor $\gamma = 0.9$ would lead us to prefer the suboptimal path. Note that this does not just hold for the example of $\gamma = 0.9$; we can come up with such a counterexample for any value $0 \leq \gamma < 1$ that will cause the solution with discount factor to break down and lead to suboptimal behaviour.

A more robust solution is a combination of iterative deepening with move ordering. In practice, we rarely use a plain minimax search with a predetermined depth limit. In practice, we usually do something like:

• Start out with a $1$-ply search
• Proceed to run a $2$-ply search afterwards if we still have time
• Proceed to run a $3$-ply search if we still have time
• etc.

This is referred to as iterative deepening. Now, when we start a new search (with an increased depth limit), a common trick is to first re-order the moves at the root node based on the scores found in the previous search (with the lower depth limit).

Now, imagine that we apply this process to the scenario described in your question. The Qxb8 line of play will first be discovered to give a $+100$ score in one of the first iterations (shallow searches). Based on this, we will sort that Qxb8 line to be searched before the Qa1+ line when moving on to the next iteration with a deeper search. Both lines will then be discovered to have the same $+100$ score, but now, due to clever move ordering (not specific to this case, but clever move ordering in general thanks to iterative deepening!), the shorter line will have been searched first and be the preferred line of play.

---

Note that the "trick" with iterative deepening + move ordering is not just useful to solve the issue highlighted in this question, but in general can also significantly increase the number of prunings that can be achieved when we extend the basic minimax algorithms with techniques like alpha-beta pruning.

Answer 3

In the rules of chess, one player can demand a draw when the same position is entered three times. If your opponent can demand a draw, the value of the position is 0 in the best case. So if you look forward far enough, you see that a move leading to repetition may not be that good.

(In this case, you would choose the second best move if it has a value > 0, or you would remain in the move repetition loop if the second best move has a value < 0. A real player in that situation would think about how confident they are to still win when breaking the loop and entering a negative value position).

You might carefully consider if you give positions with a single repetition a value of 0. There may be a good way to break the loop at some point at the start. If you realise the repetition too late, you might not get back to the start of the loop and be able to break from it but the opponent demands a draw first.