New "smoothing" issue.

[bob]

I am looking at yet another issue with unit-step-function type arithmetic. Our good friend LMR.

Here's what I am seeing. I am going to use a simplified LMR matrix where it is of the form reduce[depth][moves_searched].

I am going to give a very simple matrix to explain the issue:

0 0 1 1 2 2 3
0 0 1 2 2 3 3
0 0 2 2 3 3 4
0 0 2 3 3 4 4

You get the idea. Each row corresponds to a specific remaining search depth, each column corresponds to the number of the move being searched.

Remember, this is a made-up example, not real numbers.

One thing I recently changed in Crafty is to make sure each move has the same "number" whether in a serial or parallel search, so that a move gets reduced by exactly the same amount no matter what order it is searched in.

Suppose at depth=N, at the root, you use that top row of numbers for the reduction due to that being the N'th row in this example. The first move is not reduced (the 0 column is unused in Crafty), where the second move is reduced by 1, the third by 1, the fourth by 2, the fifth by 2, etc.

Now on the next iteration, depth is N+1, and we introduce a bit of a quirk, because the second move is still reduced by 1, but now the 3rd and 4th are reduced by 2 and the 5th by 3. That causes some EXACT hash hits that are unexpected, solely because the reduction is causing many root moves to get a hash hit at ply=2. And this iteration flies. It all depends on which moves are important and which are not. When the ones that are important get reduced by an extra ply, the search speeds up since they won't fail high.

There's not a lot to do about it. I suppose one could resort to fractional plies, and fractional reductions that increase by a fraction of a ply rather than a whole ply. And the finer that resolution, the less this looks like a real coarse unit-step-function plot. But of course it is still done in discrete steps, just smaller steps.

The reason this caught my eye is output that looks like this:

Code: Select all

         22->   4:24         -2.15   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. Qa3+
                                     Kb1 5. Qd3+ Kxb2 6. Qe2+ Kb3 7. Qe3+ Kc4
                                     8. Qxe7 Qxd4+ 9. Kf1 a3 10. Qe6+ Qd5
                                     11. Qa6+ Kb3 12. Qb5+ Kc2 13. Qe2+ Kc3
                                     14. Qe1+ Qd2 15. Qe5+ Kb4 16. Qe4+ Kb3
                                     17. Qe6+ Kb2 18. Qe5+ Qc3 19. Qe2+ Kc1
                                     20. c6 Qxc6
         23     7:57         -2.73   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc1 9. Qa6 Qf4+ 10. Ke2 Qe5+
                                     11. Kf2 Qc5+ 12. Kf1 a3 13. h3 Kb2
                                     14. Qe2+ Qc2 15. Qe5+ Kb1 16. Qb8+ Ka1
                                     17. Qe5+ Qb2 18. Qd5
         23->   7:57         -2.73   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc1 9. Qa6 Qf4+ 10. Ke2 Qe5+
                                     11. Kf2 Qc5+ 12. Kf1 a3 13. h3 Kb2
                                     14. Qe2+ Qc2 15. Qe5+ Kb1 16. Qb8+ Ka1
                                     17. Qe5+ Qb2 18. Qd5
         24    19:20         -3.06   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc2 9. Qc7+ Kd2 10. Qa5+ Qc3
                                     11. Qg5+ Kc2 12. Qe7 a3 13. Qxa7 Qc4+
                                     14. Kf2 a2 15. Kg1 Kc3 16. Qa5+ Kb2
                                     17. Qe5+ Qc3 18. Qb8+ Ka1
         24->  19:22         -3.06   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc2 9. Qc7+ Kd2 10. Qa5+ Qc3
                                     11. Qg5+ Kc2 12. Qe7 a3 13. Qxa7 Qc4+
                                     14. Kf2 a2 15. Kg1 Kc3 16. Qa5+ Kb2
                                     17. Qe5+ Qc3 18. Qb8+ Ka1
         25    21:58         -3.06   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc2 9. Qc7+ Kd2 10. Qa5+ Qc3
                                     11. Qg5+ Kc2 12. Qe7 a3 13. Qxa7 Qc4+
                                     14. Kf2 a2 15. Kg1 Kc3 16. Qa3+ Qb3
                                     17. Qc5+ Kd3 18. Qf5+ Kd2 19. Qa5+ Ke3
                                     20. Qa7+ Kf4
         25->  22:01         -3.06   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc2 9. Qc7+ Kd2 10. Qa5+ Qc3
                                     11. Qg5+ Kc2 12. Qe7 a3 13. Qxa7 Qc4+
                                     14. Kf2 a2 15. Kg1 Kc3 16. Qa3+ Qb3
                                     17. Qc5+ Kd3 18. Qf5+ Kd2 19. Qa5+ Ke3
                                     20. Qa7+ Kf4
         26    26:14         -3.06   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc2 9. Qc7+ Kd2 10. Qa5+ Qc3
                                     11. Qg5+ Kc2 12. Qe7 a3 13. Qxa7 Qc4+
                                     14. Kf2 a2 15. Kg1 Kc3 16. Qa3+ Kd2
                                     17. Qa5+ Kd3 18. Qf5+ Qe4 19. Qb5+ Kc2
                                     20. Qc5+ Kb2 21. Qb6+ Ka1
         26->  26:23         -3.06   1. ... Qd5 2. Qd2+ Kb3 3. Qc3+ Ka2 4. c6
                                     Bd6 5. c7 Bxc7 6. Qxc7 Qxd4+ 7. Kf1 Kxb2
                                     8. Qb7+ Kc2 9. Qc7+ Kd2 10. Qa5+ Qc3
                                     11. Qg5+ Kc2 12. Qe7 a3 13. Qxa7 Qc4+
                                     14. Kf2 a2 15. Kg1 Kc3 16. Qa3+ Kd2
                                     17. Qa5+ Kd3 18. Qf5+ Qe4 19. Qb5+ Kc2
                                     20. Qc5+ Kb2 21. Qb6+ Ka1
[code]

Notice that iteration 23 to 24 took almost 12 minutes, where iteration 24 to 25 took less than 3 minutes.  25 to 26 took just over 4 minutes.  Also note this is NOT a parallel search, it is a pure one thread serial search.

When I display the tree, I see some pretty funny stuff when tracing only to depth=2.  At the long iteration, every ply-1 move reached a ply-2 position where moves were searched.  At the short one, the ply=1 move was searched and an exact hit at ply=2 occurred.  This is a bit odd for a branching factor to grow and shrink iteration by iteration.

Anybody else seen this peculiar effect of LMR?

[mar]

Anybody else seen this peculiar effect of LMR?

I observe a similar effect, but I haven't investigated yet.
I should be able to use fractional plies easily so if it's a LMR problem in my case and not some kind of bug elsewhere, I will certainly try to experiment a bit to see if it helps.
Since I always truncate the fractional depth down, I'm not sure it would help with TT hits (but it will certainly accumulate as I go deeper), but this behavior can be changed easily.

[jdart]

I have used fractional plies (resolution = 1/4 ply) for a long time, so this effect probably exists, but at lower frequency than what you see.

Btw. also: I don't bother to present the same move indexing to SMP and non-SMP searches. My theory is there are actually very few splits during a search relative to the size of the overall tree. So if the ordering is "off" for those it may not matter so much. But I could be wrong.

--Jon

[bob]

I have used fractional plies (resolution = 1/4 ply) for a long time, so this effect probably exists, but at lower frequency than what you see.

Btw. also: I don't bother to present the same move indexing to SMP and non-SMP searches. My theory is there are actually very few splits during a search relative to the size of the overall tree. So if the ordering is "off" for those it may not matter so much. But I could be wrong.

--Jon

Hint: it is of major significance if you LMR at the root, which I do. It was causing some interesting search inconsistencies. But when I fixed it, I decided to fix it everywhere, perfectly, just for sanity. And the search got less unstable (fewer fail highs/fail lows/etc...)