Why minimax is fundamentally flawed

[hgm]

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

You mean at 25 ply? I suppose that this is because 25 < 27, and that to guarantee seeing a mate-in-14 needs 27 ply.

[hgm]

I guess Fairy-Max would really need 28 ply to see mate in 14, because it detects checks only at d >= 1, and just stands pat if it finds itself mated at d=0. Here it finds the mate in 14 at d=27, because the PV contains a check:

Code: Select all

dep	score	nodes	time	(not shown:  tbhits	knps	seldep)
 28	+79.86 	162.9M	2:14.46	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c4 e2e3 c4c3 e3e2 d4d3 e2e1 d3d2 e1f1 c3d3 f1g1 d3e3 g1f1 d2a2 f1g1 e3f3 g1h1 f3g3
 27	+79.86 	97.0M  	1:19.84	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c4 e2e3 c4c3 e3e2 d4d3 e2e1 d3d2
 26	+79.85 	64.1M  	0:53.00	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 d4a4 e3e2 a4a3 e2e1 c2d3 e1f2 d3d2 f2g1 d2e1 g1g2 e1e2
 25	+79.84 	38.7M  	0:32.12	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 d4c4
 24	+79.84 	26.4M  	0:22.06	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 c2c3
 23	+79.82 	19.3M  	0:16.20	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e3 b3c3 e3e2 d4d3 e2f2 c3d2 f2g2 d2e2 g2g1 d3d1 g1g2 d1d7
 22	+79.78 	11.4M  	0:09.57	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e3 b3c3 e3e2 c3c2
 21	+79.74 	9.07M  	0:07.64	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b4d4 d2e2 b3c2 e2e3 d4c4
 20	+5.38 	7.03M  	0:05.93	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3c4 d2e2 b4b3 e2d2 c4d4 d2e2 d4c3
 19	+5.34 	6.60M  	0:05.56	b2b5 e4d4 c2b3 d4e4 b3c3
 19	+5.19 	5.20M  	0:04.32	c2c3 e4e5 b2b5 e5f6 c3c4 f6g6 c4d4 g6f6 d4e4 f6g6 e4e5 g6g5 b5b8 g5g6
 18	+5.12 	3.26M  	0:02.57	c2c3 e4e5 b2h2 e5e4 h2h5
 18	+5.10 	1.76M  	0:01.37	b2b5 e4d4 c2b3 d4e3 b5b4 e3d3 b3b2 d3e2
 17	+5.08 	1.24M  	0:00.95	b2b5 e4d4 c2b3 d4e3 b3c4 e3e4 c4c3 e4f3 c3d4 f3f4 d4d3
 16	+5.00 	939799	0:00.71	b2b5 e4d4 c2b3 d4e3 b3c4 e3e4 c4c3 e4f3 c3d4 f3f4 d4d3
 15	+4.96 	714278	0:00.54	b2b5 e4d4 c2b3 d4e3 b5b4 e3d3 b4h4 d3e3 b3c3 e3f3 h4b4
 14	+4.85 	467778	0:00.35	b2b5 e4d4 c2b3 d4e3 b3c4 e3e4 c4c3
 13	+4.82 	337576	0:00.25	b2b5 e4d4 c2b3 d4e4 b3c3 e4f3 c3d3 f3f4 b5a5
 12	+4.80 	258464	0:00.18	b2b5 e4d4 c2b3 d4e4 b3c3 e4f3 c3d4 f3f4 d4d3
 11	+4.71 	190676	0:00.14	b2b5 e4d4 c2b3 d4e4 b3c3 e4f3 c3d3 f3f4 d3d2
 10	+4.73 	145848	0:00.09	b2b5 e4d4 c2b3 d4d3 b5b4 d3d2 b3b2 d2d3
 10	+4.70 	118170	0:00.07	b2b1 e4f4 c2d3 f4f5 b1b5 f5f6 d3e4 f6e6 e4d3 e6f6
  9	+4.73 	58381  	0:00.03	b2b1 e4f4 c2d3 f4f5 b1b5 f5f6 d3e4 f6e6 b5c5
  8	+4.70 	31156  	0:00.01	b2b1 e4d5 c2d3 d5e5 b1f1 e5d6 d3e4 d6e6
  7	+4.70 	12092  	0:00.00	b2b1 e4d5 c2d3 d5e5 d3e3 e5f5 e3d4
  6	+4.69 	9504    	0:00.00	b2b1 e4d5 c2d3 d5e5 d3e3 e5f5
  5	+4.61 	4299    	0:00.00	b2b1 e4d5 c2d3 d5e5
  5	+4.38 	3288    	0:00.00	b2b8 e4d5 c2d3 d5e5
  4	+4.61 	936      	0:00.00	b2b8 e4d4 b8e8 d4d5
  3	+4.64 	265      	0:00.00	b2b8 e4e5 c2d3
  3	+4.53 	153      	0:00.00	b2b4 e4e5 c2d3
  2	+4.59 	84        	0:00.00	b2b4 e4e5
  2	+4.55 	28        	0:00.00	c2d2 e4e5
  2	+4.36 	21        	0:00.00	c2c3 e4e5
  1	+4.60 	13        	0:00.00	c2c3

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.

I can see no reason why you would suspect that. Plain minimax evaluates each position by the ultimate gain that can be forcibly achieved from it, irrespective of how long it takes to reach this gain. The delayed-loss method evaluates each position as the ultimate gain minus the length of the shortest path that can be forced to reach it. So it expresses progress in the score the search assigns to each position. This is known to work very well in case the ultimate gain is a checkmate.

I also dont understand why you would think the table gets less efficient, ratherthan the search. The table just retrieves what the previous search came up with, and what it should come up with again if you would redo it. This should work equally well no matter what scores you assign to the various positions.

[mvk]

I also dont understand why you would think the table gets less efficient, ratherthan the search. The table just retrieves what the previous search came up with, and what it should come up with again if you would redo it. This should work equally well no matter what scores you assign to the various positions.

My thinking is that alpha and beta now depend on the level in the tree. The deeper into the tree, the further they move away from zero. With that, what is a cut from the table at one level is not a cut at a deeper level any longer. The extreme case (in the other corner of the spectrum) is where you keep the evaluation constant, like I did above. So I was wondering if you observe such an effect with the delayed-loss technique or not.

(BTW, my constant eval should be considered a stub towards adding DTZ support. Because while all this might help at the simple endgames, it is generally not good anymore at 5 pieces or more. Even KQKR is hard with this. And once I use DTZ, there is no need for an evaluation at all, so that code is redundant).

[hgm]

My thinking is that alpha and beta now depend on the level in the tree. The deeper into the tree, the further they move away from zero. With that, what is a cut from the table at one level is not a cut at a deeper level any longer.

Well, that is the desired effect. Mate in 5 is no longer a cut-move on a level where mate in 3 has already been found in a parallel branch, while it would be a cut move on a level where you found only mates in 7 against good defense. For 'mate' you could substitute 'promotion' or 'gaining a piece' or whatever.

In Fairy-Max this actually causes mate-distance pruning: at some point the pre-adjustment of beta pushes it below -INF (the King-captured score), and this causes a stand-pat cutoff due to the initialization of bestScore to -INF (a cutoff which normally would occur only at d=0, when bestScore is initialized to Eval(), and the latter is >= beta). This happens when you would have to be mated in a negative number of moves from the current position to end worse than what the opponent already could force with other moves.

The extreme case (in the other corner of the spectrum) is where you keep the evaluation constant, like I did above. So I was wondering if you observe such an effect with the delayed-loss technique or not.

It is true that you ask the search to do more: without delayed loss you were happy with any path to the ultimate gain, now you ask it to find the shortest path. That will be more work. But you also get more. This is always the curse of a better, more detailed evaluation. Evaluate all positions as 0 and you suddenly reach incredible depths.

[mvk]

My thinking is that alpha and beta now depend on the level in the tree. The deeper into the tree, the further they move away from zero. With that, what is a cut from the table at one level is not a cut at a deeper level any longer.

Well, that is the desired effect. Mate in 5 is no longer a cut-move on a level where mate in 3 has already been found in a parallel branch, while it would be a cut move on a level where you found only mates in 7 against good defense. For 'mate' you could substitute 'promotion' or 'gaining a piece' or whatever.
...
It is true that you ask the search to do more: without delayed loss you were happy with any path to the ultimate gain, now you ask it to find the shortest path. That will be more work. But you also get more.

Yes, in mate that is the desired effect and you get more (and it is quite elegant there). But I mean in the cases where no mate is found yet: the heuristic part of the search. That is where games are won or lost. Efficient mate finding only comes after that. So my worry is that the delayed-loss technique helps where there is no real need, but costs, in the form of larger trees, where the game is still uncertain.

Anyway, to come back to the original premise of this thread: minimax was not the problem in this game. Bad evaluation functions are bad, I agree with that. But in this game, it was not the evaluator that caused the draw, but a transposition table bug (fixed by change nr 3), as Ronald suggested. Change nr 1 and 2 are just things I did at the same time.

I would love to see the delayed-loss technique, as a solution to the alleged minimax problem, proven to be valuable in, say, Stockfish, or any other program with modern evaluation. As said, I have used something very similar to it before, but I don't consider it worthwhile now in regular chess. Not without quantitative evidence, or some really cool examples at least

[hgm]

Yes, in mate that is the desired effect. But I mean in the cases where no mate is found yet: the heuristic part of the search. That is where games are won or lost. Efficient mate finding only comes after. So my worry is that the delayed-loss technique helps where there is no real need, but costs, in the form of larger trees, where the game is still uncertain.

It would only lead to larger trees in positions where the engine doesn't have anything useful to do anymore. If after a gain (say a promotion) it continues to improve its position, it would go for the shortest path to the gain anyway, because any longer path would leave fewer moves after the gain to improve the position.

The mechansim would only start to affect the search in positions where there is a dip in the score after a gain. Which is actually quite typical, as almost no gain in Chess can be completely effectuated without repercussions. In such cases extra depth is not really helpful: it just stimulates the engine to close its eyes for the repercussions, and it will try to fool around and delay the gain to occur at the horizon, the repercussions safely pushed just behind it.

Fact is that a gain occurring very close to the horizon is less verified by the search beyond it than a similar gain close to the root, and likely overestimated, as while you were busy securing the gain the opponent was already preparing his counter attack. To do justice to this effect the delaydloss bonus would probably have to be much larger than the score quantum of 1cP that Fairy-Max uses, though. But I would certainly expect an engine that uses such a large bonus to bungle fewer won games by indecision.

Anyway, to come back to the original premise of this thread: minimax was not the problem in this game. Bad evaluations are bad, I agree with that. But in this game, it was not the evaluation that caused the draw, but a transposition table bug (change nr 3), as Ronald suggested. Change nr 1 and 2 are just things I did at the same time.

Well, this is a thing that could only be established by an elaborate post-mortem investigation. At the time the trasposition-table bug was unknown, and I recall we agreed on the explanation of the local optimum. And it remains a fact that minimax fails to do the job on an evaluation with such local maxima, while a delayed-loss bonus would cure that.

I would love to see the delayed-loss technique, as a solution to the alleged minimax problem, proven to be valuable in, say, Stockfish, or any other engine with modern evaluation. As said, I have used something very similar to it before, but I don't consider it worthwhile now in regular chess. Not without quantitative evidence, or some really cool examples at least

Evidence is always nice. But as the logical expectation is that this will add Elo, empirical evidence would have to show that it is detrimental in order for me to abandon it. Or, more likely, tune it better.

[Ozymandias]

A known flaw of minimax is that it is in no hurry to achieve anything, with as a result that it might not achieve anything at all, but keeps postponing the gain it sees indefinitely. This is of course well known in the case of checkmates, and many people for this reason do not evaluate mate with the game-theoretical maximum score, but make the score depend on the distance from the root. By this kludge minimax will go for the fastest mate.

The problem is that most moves in a Chess game must be made without a forced mate being within the horizon, and the mate-score kludge does of course nothing for gains other than checkmates. So it can still happen that some necessary intermediate objective on the path to a win, such as a promotion, is postponed forever.

I have hardly ever seen a clearer example of this than in the following game from the CSVN tourney yesterday:

[pgn][Event "ICS Rated standard match"]
[Site "winboard.nl"]
[Date "2014.11.09"]
[Round "-"]
[White "Tornado"]
[Black "Rookie"]
[Result "1/2-1/2"]
[WhiteElo "1897"]
[BlackElo "1787"]

1. e4 e5 2. Nf3 Nc6 3. Bc4 Nf6 4. d3 Bc5 5. c3 a5 6. d4 exd4 7. cxd4 Bb4+
8. Kf1 d5 9. exd5 Nxd5 10. a3 Be7 11. Nc3 Be6 12. Bb3 Qd7 13. Kg1 O-O-O 14.
Ba4 Nb6 15. Bb5 Bg4 16. h3 Bxf3 17. Qxf3 Qe6 18. Bxc6 Qxc6 19. Qg4+ Kb8 20.
Be3 Nd5 21. Bd2 Rhe8 22. Rc1 Nxc3 23. Rxc3 Qb6 24. Bf4 Bd6 25. Bxd6 Qxd6
26. Re3 g6 27. Qe2 Rxe3 28. fxe3 c5 29. dxc5 Qxc5 30. Kh2 Qe5+ 31. g3 h5
32. Kg2 Qe4+ 33. Kh2 h4 34. gxh4 Rd3 35. Re1 Rb3 36. Qf2 Qe5+ 37. Kg2 Rxb2
38. Re2 Qe4+ 39. Kg3 Rb5 40. Kh2 Qd3 41. Qf4+ Ka7 42. Qd4+ Qxd4 43. exd4
Rb3 44. Re5 Rxa3 45. h5 gxh5 46. Rxh5 Ka6 47. Rh6+ b6 48. h4 Rd3 49. Rd6 a4
50. h5 a3 51. Rd8 Rd2+ 52. Kg3 a2 53. h6 Rd3+ 54. Kg2 Rxd4 55. Ra8+ Kb7 56.
Rxa2 Rh4 57. Rf2 Rxh6 58. Rxf7+ Ka6 59. Rf4 b5 60. Kf3 Re6 61. Rg4 Ka5 62.
Rg1 b4 63. Rb1 Ka4 64. Ra1+ Kb5 65. Rb1 Kc4 66. Rc1+ Kd3 67. Kg3 b3 68. Rc7
Rb6 69. Rd7+ Kc4 70. Rd1 b2 71. Rb1 Kb3 72. Kf4 Kc2 73. Rxb2+ Rxb2 74. Ke4
Rb4+ 75. Ke5 Kd2 76. Kd5 Kd3 77. Ke5 Rb5+ 78. Kf6 Kd4 79. Ke6 Kc4 80. Kd6
Rg5 81. Ke6 Kd3 82. Kf6 Rg8 83. Kf7 Rg5 84. Kf6 Rb5 85. Ke6 Kc3 86. Kd6 Rg5
87. Ke6 Rg7 88. Kf6 Ra7 89. Ke5 Rc7 90. Kd6 Rb7 91. Ke5 Rb5+ 92. Kd6 Rh5
93. Ke6 Kd2 94. Kd6 Rh7 95. Ke5 Rh2 96. Kd4 Rh4+ 97. Ke5 Rh6 98. Kd4 Rh7
99. Ke5 Rh6 100. Kd4 Rc6 101. Ke5 Ke3 102. Kd5 Rh6 103. Ke5 Rc6 104. Kd5
Rb6 105. Kc5 Rh6 106. Kd5 Rf6 107. Ke5 Rg6 108. Kd5 Ra6 109. Ke5 Kd2 110.
Ke4 Rg6 111. Kd4 Rh6 112. Ke4 Rh8 113. Kd4 Rh6 114. Ke4 Rg6 115. Kd4 Rg4+
116. Ke5 Rg8 117. Kd4 Rg7 118. Ke5 Ke3 119. Kf6 Rg4 120. Ke6 Ke4 121. Kd6
Rg6+ 122. Kc5 Rh6 123. Kc4 Rc6+
{Draw by the 50 move rule} 1/2-1/2
[/pgn]

At low search depth Rookie has no problem checkmating in KRK at all. But at this long TC, it cannot find the win, and falls victim to the 50-move rule! As Marcel explained afterwards: Rookie was thinking ~20 ply here, which is not enough to see a forced mate. So its search just goes for the position with the best heuristic evaluation. Which will be something with the strong King in the center, and the bare King pressed against the edge. But such a position can be forced with far fewer moves than the available 20 ply. So there are lots of branches that start by wasting 6 or 8 ply, and then decisively force the 'optimal' position in the remaining moves. And minimax cannot see any difference between the lines that immediately 'talk shop' and those that initially merely waste time. And as the latter are of course much more abundant, the chances that it picks a move that makes progress are very slim indeed. Of course when it would have accidentally reached the 'optimal' position, it would have seen that it was not really optimal at all, but a better position would come in the horizon, (namely the checkmate).

Now there are of course many ways in use to patch this problem. E.g.

* One could use 3-men tablebases. But this masks the problem, rather than solving it. It would work in this specific KRK case, but the same problem can occur in much more complex end-games, for which tablebases are not feasible.

* One can attempt to abuse the 50-move rule to blackmail a program into making progress where it would just fool around on its own, thinking it could always make the progress later. In KRK this will of course not help, because there is no other way to reset the move counter than a forced Rook sac, which makes it draw anyway.

* One could prevent local maxima in the heuristic eval, and require the eval increases monotonically towards the mate position. Then there is an incentive to progress as much as possible, which excludes pointless fooling around. The snag is of course that this basically requires the evaluation to be perfect, and with perfect evaluation search would be pointless to begin with. You would just make the move with the highest evaluation gain, and this would always bring you to the mate, as there would always be a move that increases the evaluation. Search is only needed to bridge dips in the evaluation, to be able to reach a better local optimum from the current one.

So there still is need for something similar to the mate-score kludge for other gains than checkmates. Note that this cannot be the same trick of applying a discount to the heuristic eval based on the distance to the root, in the same way as you discount mate scores based on that distance. Because in a fixed-depth search, for instance, all evaluations would have the same distance to the root, so this would still not distinguish one branch from another. You really want to select the branch where the gain that can be foreseen is reached as early as possible. So you want to discount it with the depth at which the gain actually materialized. For checkmates this is of course the end of the branch, as one never searches beyond checkmate.

So if at the end of the branch there is a certain eval score higher than the eval in the root (meaning that some way to make progress can be seen within the horizon), you would have to discount the score of that branch by the distance (mesasured from the root) of the point where the evaluation reached the value it has in the leaves. Beyond that point it has apparently just been wasting time, not upping the evaluation any further. This is exactly what a 'delayed-loss bonus' does: it adds one eval point to the score propagated towards the root when this score is below the current eval. Thus it counts the number of full-moves between the root and the point where the evaluation reaches (or exceeds) the value it has in the leave. In absence of anything better to do (as visible within the horizon), the program would then take the move that brings it to that eval in the quickest way. Meaning that it will quickly reach it, rather than fooling around thinking it can always go there later. And once it is there, it can see further, and hopefully does see an even more profitable goal, which it otherwise would never get to see. (Like the KRK mate in the example.)

From what I understand, you're saying: "minimax is fundamentally flawed [when applied to a chess engine's search]". Even in that case, minimax isn't fundamentally flawed, as the thread's title states, because there're other scenarios for it to be used in, successfully. I'm thinking of opening theory, where the refutation to an entire line, remains hidden, as long as the occurrence doesn't reach a point, where it affects the previous moves' statistics. I seem to remember you advocating about some sort of minimax for this very purpose, so I guess the title was just trimmed for space reasons.

[mvk]

The mechansim would only start to affect the search in positions where there is a dip in the score after a gain. Which is actually quite typical, as almost no gain in Chess can be completely effectuated without repercussions. In such cases extra depth is not really helpful: it just stimulates the engine to close its eyes for the repercussions, and it will try to fool around and delay the gain to occur at the horizon, the repercussions safely pushed just behind it.

The challenge is: is this really a problem in the strong programs?

Anyway, to come back to the original premise of this thread: minimax was not the problem in this game. Bad evaluations are bad, I agree with that. But in this game, it was not the evaluation that caused the draw, but a transposition table bug (change nr 3), as Ronald suggested. Change nr 1 and 2 are just things I did at the same time.

Well, this is a thing that could only be established by an elaborate post-mortem investigation. At the time the trasposition-table bug was unknown, and I recall we agreed on the explanation of the local optimum. And it remains a fact that minimax fails to do the job on an evaluation with such local maxima, while a delayed-loss bonus would cure that.

My old evaluation reached a plateau, not a local optimum. I believed it could not search out of the plateau, and I mentioned I didn't do mate grafting right everywhere. Extra plies should take care of that, and proper evaluations don't have this problem with promotions and such. I believed the plateau stretched too far. But I recall I also mentioned that it was suspect that the PV was changing, and with that the first move, which didn't match with that theory.

Evidence is always nice. But as the logical expectation is that this will add Elo, empirical evidence would have to show that it is detrimental in order for me to abandon it. Or, more likely, tune it better.

Or have better evaluation. These delaying moves, are they present in the strong programs? Those seem to cope pretty well with this. So the question is if that problem is real when the evaluation is properly tuned.

I have been bitten too many times by things that appear to be logical, but still don't work out (such as the GHI "fix", which seemed perfectly valid). I had another such logical flaw when improving the mate usage from the table, related to accepting a lower bound as an exact value when the required depth is lower than the stored depth, in combination with ignoring depth on certain mate bounds. Both ideas sound logical, but the combination doesn't always work well. Because when you back up such a score, the "fake" exact value gets stored higher in the tree, and from that moment onwards, later transpositions fail to search beyond it. This eventually prevented the program from finding the best mate, regardless of the depth. (/rant)

[hgm]

The challenge is: is this really a problem in the strong programs?

I wouldn't know. I cannot judge the play of strong programs.

I have been bitten too many times by things that appear to be logical, but still don't work out (such as the GHI "fix", which seemed perfectly valid). I had another such logical flaw when improving the mate usage from the table, related to accepting a lower bound as an exact value when the required depth is lower than the stored depth, in combination with ignoring depth on certain mate bounds. Both ideas sound logical, but the combination doesn't always work well. Because when you back up such a score, the "fake" exact value gets stored higher in the tree, and from that moment onwards, later transpositions fail to search beyond it. This eventually prevented the program from finding the best mate, regardless of the depth. (/rant)

I must admit I do not understand how this could happen. When you use the bound of a deeper hit as an exact score, you are faking too low a score (i.e. too large a DTM) because of grafting. But that is pretty normal for any form of grafting, also when grafting exact scores. Usually you do not get the quickest mate that way, often rediculously long mates, like mate in 57, when in reality it is a mate in 11. So if this really is a problem, it should be a problem with any grafting. Counting a mate-in-6 score obtained in a 13-ply search as valid for any higher depth should also be pretty safe.

[Aleks Peshkov]

Stupid question, how delayed-lose bonus compares to a known technique of interpolation of evaluaiton score and draw score near fifty-moves-rule horizont. Can both of those generalized into one?