Why minimax is fundamentally flawed

[hgm]

Well, this starts to be all semantics, but for me 'minimax' has a very specific definition, namely

value(position) = max_i(value(move_i))
value(move) = -value(MakeMove(position, move))

(in negamax formulation). As soon as you start to mess with that definition, like replacing max_i by sum_i or average_i, or (average_i(value(move_i)^N)^(1/N), it would no longer be minimax.

It is true that a delayed-loss bonus can be formulated as a modification of the score-propagation rule only, so that you still maximize something.

Note that minimax has other flaws as well (in combination with a heuristic eval), namely that it is very poor in risk management, and would not hesitate at all to go for the node with highest score if every deviation from the path to it can already be seen to end in total disaster. End then, of course, after it can see a bit deeper, the score of the node it was aiming for collapses as well... So it would actually be a good idea to not just take the maximum, but weight in the score of the second and third move as well, to determine the value of a position. Even if these would have only infinitesimal weight you would already achieve that of two paths leading to the same final position, it would prever the one that offers escapes in case the original plan collapses, and not the one that totally commits it. Rather than just picking them by pure chance. I definitely would not call that minimax.

[DustyMonkey]

Forgive me for butting in, but it seems to me that there is already well accepted attempts to deal with this second issue of "after it can see a bit deeper, the score of the node it was aiming for collapses as well..."

I am quite sure that minimax() in all of its varieties comes with the assumption that sudden eval swings from ply to ply greatly harms the utility of searches that dont go to terminal (end of game) nodes.

The fault here then sits at the feet of qsearch() and eval(), which in concert do not give an accurate evaluation that is so fundamental to minimax() being good for incomplete searches.

The top engines do a very good job here. When qsearch() fails to deliver, the evals() then mostly overcome that failure by applying a penalty to the evals of positions where danger might loom (mobility, activity, safety, ..) Only when these danger positions are well within the horizon will the top engine see unpenalized gains on the other side.

Sure, even the top engines arent perfect. Recently at TCEC Stockfish didnt recognize the danger of Gulls connected passed as being worth avoiding. The penalty for facing two connected passed pawns wasnt enough to overcome the other factors within its horizon. Maybe connected passed pawns should be evaluated higher, or maybe those other factors shouldnt be rated so high when there are two connected passed pawns

..its a complex thing to try to solve, but its not solved by giving up on minimax() .. its solved by feeding minimax() what it needs more often.

[hgm]

Well, like I said, if evaluation is perfect, search is pointless. What you are arging is basically that we should make the evaluation perfect, so that no job is left to do for the search, so that even a flawed search would not hurt. But that of course does not make it any less flawed.

[mvk]

Coincidentally, I had that in Rookie v2, 1997-1998 era. I don't have it in the v3 rewrite anymore because it costs several hard to predict branches per node (and it is difficult to understand).

Actually I don't think it costs any branches at all. The way Fairy-Max writes it is different from the code I gave above for educational purposes. What it really does is:

Code: Select all

alpha -= &#40;alpha < curEval&#41;;
beta -= &#40;beta <= curEval&#41;;
...
return bestScore + &#40;bestScore < curEval&#41;;

Your implementation is certainly more elegant than what I did in the day. I will reconsider it for the next version. (Not to fix KRK of course, it should be taken care by that time by other means...)

I do have one other concern which I didn't mention before, and that is that the window is now changing all the time. How does that play with transpositions and the usefulness of cuts from the transposition table? Do you have any data on that?

[Karlo Bala]

Note that minimax has other flaws as well (in combination with a heuristic eval), namely that it is very poor in risk management, and would not hesitate at all to go for the node with highest score if every deviation from the path to it can already be seen to end in total disaster. End then, of course, after it can see a bit deeper, the score of the node it was aiming for collapses as well... So it would actually be a good idea to not just take the maximum, but weight in the score of the second and third move as well, to determine the value of a position. Even if these would have only infinitesimal weight you would already achieve that of two paths leading to the same final position, it would prever the one that offers escapes in case the original plan collapses, and not the one that totally commits it. Rather than just picking them by pure chance. I definitely would not call that minimax.

If you add (somehow) score of the second move to the best score, evaluation before and after making the best move will differ significantly, which is not good at all. If you try to make the average value of the first two moves or something similar, then the singular moves will have an advantage. All in all, it is not an easy task. For example, the BPIP-DFISA algorithm has a similar defect.

[DustyMonkey]

Well, like I said, if evaluation is perfect, search is pointless. What you are arging is basically that we should make the evaluation perfect, so that no job is left to do for the search, so that even a flawed search would not hurt. But that of course does not make it any less flawed.

I dont see why this is debatable.

If we have 6 man TB's and its a 7 man position and every min and max branch of the tree leads to one of the 6 man positions, then we have a perfect eval() over the whole space, but still we had to search to get there.

Surely if we had a really terrible eval() that didnt model even a close approximation of game theoretical outcome we would not be blaming the search algorithm. Makes no sense to start blaming the search algorithm when the eval() is a lot better than that.

Yes, providing good data for the search algorithm is hard. That doesnt make the search algorithm flawed. Sometimes things really are hard, and even more so when all of this rests additionally on resource allocation tradeoffs between the various parts of the whole.

[hgm]

If we have 6 man TB's and its a 7 man position and every min and max branch of the tree leads to one of the 6 man positions, then we have a perfect eval() over the whole space, but still we had to search to get there.

That is because you don't have perfect evaluation for 7-men positions. This is not really different from chess without tablebases, saying that you have perfect evaluation in all positions that are checkmates. But you have to search to the checkmate. Well, usually you cannot, and checkmate will be very far beyond your horizon. Just like it can happen that forced conversion to 6 men is very far beyond the horizon of a 7-men position.

Surely if we had a really terrible eval() that didnt model even a close approximation of game theoretical outcome we would not be blaming the search algorithm. Makes no sense to start blaming the search algorithm when the eval() is a lot better than that.

I don't follow that lgic. If the eval sucks it is OK to blame the search algorithm, but if the eval is good, and things go wrong, it makes no sense to blame the search??? Then who is to blame in that case?

[mvk]

Of course Fairy-Max, having nothing but King centralization in its eval, (and delayed-loss bonus), has little difficulty finding the mate, form the position immediately after conversion to KRK:
[d]8/8/8/8/4k3/8/1RK5/8 w - - 0 1

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 25	+79.85 	53.2M  	0:42.37	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3f2 c3d3 f2f3 b4d4
 24	+79.85 	31.0M  	0:24.78	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 c2c3 e3e2
 23	+79.83 	24.8M  	0:19.81	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e1 b3c3 e1e2 c3c2
 22	+79.78 	13.1M  	0:10.36	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 d4b4 e3f3 c2d2 f3f2 b4f4 f2g2 d2d1
 21	+79.76 	9.31M  	0:07.36	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e3 b3c3 e3e2 c3c2
 20	+5.52 	6.15M  	0:04.82	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f2 d4d3 f2f3 b4e4

At 21 ply it already sees a mate in 24, which at 24 ply (24 sec on a single 2.4GHz i3 core) is improved to a mate in 15.

This of course is cause by grafting, as to see M15 would need 29 ply. (Checks just delay the mate in KRK, so you wont get free plies from the check extension.) So not doing hash cuts in PV moves, which destroys the ability to graft, probably plays a role here too.

I must admit that the search above was using Fairy-Max 4.8V's new feature for recognizing bare King in the root, and multiplying its centralization bonus by 5. (This was needed to reliably checkmate with many centralizing pieces, such as in KNFFK with the F both on the same color; when it would give centralization of the bare King equal weight to centralization of the 4 pieces of the winning side, the latter would think it more profitable to just centralize his own pieces, and leave the bare King alone to do what he wants!) When I let it search the same position using the normal centralization bonus for both Kings, it takes a bit longer:

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 24	+79.83 	48.3M  	0:40.03	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f3 d4d3 f3f2 b4f4 f2g2 d3d4
 23	+79.83 	41.3M  	0:34.31	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f3 d4d3
 22	+79.79 	35.5M  	0:29.48	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e3 c4c3 e3e2 c3d4 e2f2 d4d3 f2f3 b4b5
 21	+79.76 	32.9M  	0:27.36	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3b2 d2d3 b4a4 d3e3 b2c2 e3f3 c2c1
 21	+5.25 	31.5M  	0:26.12	b2b1 e4d4 b1e1 d4c4 e1d1 c4b4 c2d3 b4c5 d3c3
 20	+5.26 	27.9M  	0:23.15	b2b1 e4d4 b1e1 d4c5 e1d1 c5c4 c2b2 c4b5 b2c3 b5c5 c3b3
 20	+5.19 	22.9M  	0:19.18	b2b4 e4d5 c2d3 d5c5 b4b3 c5d5 b3c3 d5e5 c3c6 e5d5 c6c4

I recently reworked some of the transposition table and endgame code in Rookie:
1. Remove the mopup evalution. Just return +30000 in a won position.
2. Smarter use of mate values in transposition table (but still using only 1 bound)
3. Bug with draws in transposition table fixed. I used some old GHI idea inspired by a Campbell article, but it doesn't work out. This is what Ronald hinted at, and the main reason the program didn't always find mate.

The result in the position above is good enough for play: First mate is found at 4M nodes. Best mate is found at 13M nodes. Full PV is resolved at 22M nodes.

Code: Select all

8/8/8/8/4k3/8/1RK5/8 w - - 0 1
8  - - - - - - - -
7  - - - - - - - -
6  - - - - - - - -
5  - - - - - - - -
4  - - - - k - - -
3  - - - - - - - -
2  - R K - - - - -
1  - - - - - - - -  O
   a b c d e f g h

  time ply  score variation
   0.0   1 +30.000 1. Kd2
   0.0   2 +30.000 1. Kd2 Kf5
   0.0   3 +30.000 1. Kd2 Kf5 2. Ke3
   0.0   4 +30.000 1. Kd2 Kf5 2. Ke3 Kg6
   0.0   5 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4
   0.0   6 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7
   0.0   7 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7 4. Kg5
   0.0   8 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7 4. Kg5 Kh8
   0.0   9 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7 4. Kg5 Kh8 5. Kh6
   0.0  10 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7 4. Kg5 Kh8 5. Kh6 Kg8
   0.1  11 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7 4. Kg5 Kg8 5. Kh6 Kf8 6. Kh7
   0.1  12 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kh7 4. Kg5 Kg7 5. Kh5 Kh7 6. Kh4 Kh8
   0.2  13 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kg7 4. Kg5 Kf7 5. Kh6 Kf8 6. Kh7 Kf7 7. Kh8
   0.2  14 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kg7 4. Kg5 Kf7 5. Kh6 Kf8 6. Kh7 Kf7 7. Kh8 Kg6
   0.4  15 +30.000 1. Kd2 Kf5 2. Ke3 Kg6 3. Kf4 Kg7 4. Kg5 Kf7 5. Kh6 Kf8 6. Kh7 Kf7 7. Kh8 Kg6 8.
                   Kg8

   1.1  16 +31.955 1. Rb4+ Kf5 2. Kd3 Ke5 3. Rb5+ Kd6 4. Kd4 Kc6 5. Rh5 Kd7 6. Kd5 Ke7 7. Rh4 Kd7 8.
                   Rb4 Kc7 9. Rb5 Kd7 {M23}

   1.2  17 +31.959 1. Rb4+ Kf5 2. Kd3 Ke5 3. Re4+ Kd5 4. Rd4+ Kc5 5. Ke4 Kc6 6. Rc4+ Kd6 7. Rc1 Ke6
                   {M21}

   1.5  18 +31.967 1. Rb4+ Kf5 2. Kd3 Ke5 3. Rb5+ Kd6 4. Kd4 Kc6 5. Rc5+ Kd6 6. Rd5+ Ke6 7. Ke4 Kf6 8.
                   Re5 Kg6 9. Kf4 Kf6 10. Re4 Kg6 11. Re6+ Kf7 12. Kf5 {M17}

   1.6  19 +31.969 1. Rb4+ Kf5 2. Kd3 Ke5 3. Rc4 Kd5 4. Rd4+ Kc5 5. Rd8 Kb5 6. Rd5+ Kb6 7. Kd4 Kc6 8.
                   Kc4 Kb6 9. Rd6+ Kb7 10. Kd5 Kc7 11. Kc5 Kb7 12. Rd7+ Kc8 {M16}

   2.2  20 +31.971 1. Kc3 Ke5 2. Re2+ Kf4 3. Kd4 Kf5 4. Re5+ Kf4 5. Rc5 Kf3 6. Rf5+ Ke2 7. Ke4 Kd2 8.
                   Rc5 Ke2 9. Rc2+ Kd1 10. Kd3 Ke1 11. Ke3 Kf1 12. Ra2 Kg1 {M15}

   2.6  21 +31.971 1. Kc3 Ke5 2. Re2+ Kf4 3. Kd4 Kf5 4. Re5+ Kf4 5. Rc5 Kf3 6. Rf5+ Ke2 7. Ke4 Kd2 8.
                   Rc5 Ke2 9. Rc2+ Kd1 10. Kd3 Ke1 11. Ke3 Kf1 12. Ra2 Kg1 13. Kf3 {M15}

   2.9  22 +31.971 1. Kc3 Ke5 2. Re2+ Kf4 3. Kd4 Kf5 4. Re5+ Kf4 5. Rc5 Kf3 6. Rf5+ Ke2 7. Ke4 Kd2 8.
                   Rc5 Ke2 9. Rc2+ Kd1 10. Kd3 Ke1 11. Ke3 Kf1 12. Ra2 Kg1 13. Kf3 Kh1 {M15}

   3.3  23 +31.973 1. Kc3 Ke5 2. Rb5+ Kf6 3. Kd4 Ke6 4. Rd5 Kf6 5. Re5 Kf7 6. Kd5 Kf6 7. Kd6 Kf7 8.
                   Re6 Kf8 9. Re7 Kg8 10. Ke5 Kf8 11. Kf6 Kg8 12. Rd7 Kh8 {M14}

   5.3  26 +31.973 1. Kc3 Ke5 2. Rb5+ Kf6 3. Kd4 Ke6 4. Rd5 Kf6 5. Re5 Kf7 6. Kd5 Kf6 7. Kd6 Kf7 8.
                   Re6 Kf8 9. Re7 Kg8 10. Ke5 Kf8 11. Kf6 Kg8 12. Rd7 Kh8 13. Kg6 Kg8 14. Rd8# {M14}
{Depth limit reached}

Total nodes                        : 22217623
Endgame table hits                 : 2704665
Total time [s]                     : 5.279
Node frequency [Hz]                : 4.209e+06
Average depth [ply]                : 16.2
Maximum depth [ply]                : 28
CPU time [s]                       : 5.278
CPU load                           : 100.0%

The same method finds the mate in KBNK now from the worst positions if there are at least 2 minutes left on the clock for the remainder of the game. The first few moves it shuffles around, and then it sees the mate and zooms in on that. Well before 50 moves.

So all in all, I don't see that minimax is flawed. At least, this endgame is not an example of that.

[hgm]

So all in all, I don't see that minimax is flawed. At least, this endgame is not an example of that.

Indeed, you don't see it anymore. The way you now treat this end-game is not an example of it anymore.

But that does not prove that minimax is OK. The signalled problem was that it would not be able to find a win in the presence of an evaluation with local maxima, even when on any local maximum it would be possible to see the next better maximum. Just because it sees no incentive to go to the nearest visible maximum, and entropy will make it unlikely it will get there by accident.

You just cured that by making a totally flat evaluation, so that there are no local maxima in the first place, and fixed some defects in the minimax implementation so that you can now search deep enough to see the mate. (Flat evaluation of course helps speeding up the search too, as any move would be a beta cutoff, when all moves get the same score.)

The price is that when the search cannot get the mate within the horizon, the flat evaluation makes it totally clueless.

[mvk]

No. If I place back the evaluation, it still finds mate reliably and fast. Just a little bit later, because the tree gets wider. These endgames are small enough to solve by brute force. The fatal bug was in the GHI cleverness.

BTW: I'm still interested in my open question earlier in the tread regarding the interaction of changing alpha/beta values and cuts in the table. It seems to me that the table becomes less effective when using the delayed-loss method.

And oh: is there a reason that Fairymax doesn't find the mate in 14?