variable reductions

[bob]

You were not talking about the same thing. He was talking about using a 1 ply(or at least extremely shallow) full width search at the beginning to get an initial order for all of the root moves. Then using a normal search after that. Frankly, that was pretty obvious from what he wrote. I think an extra second or two spent reading would have saved you a minute on writing.

Better look again, because that is exactly what _I_ do to order the root moves.. He was not talking about just a 1 ply search, and in his first post it was not clear that he turned it off. I was simply interested in seeing where the discussion led, since his explanation was not clear to me (at least in the first post).

If N == 1 costs me only 20 * 1 milliseconds search time and I use these values to improve the move ordering at higher levels (slightly) in the root node then there is still a (small) gain.

First move is not always the best move. A research at move I is better than a research at move I + K unless the new value of the best move is almost equal to the previous best move or am I wrong.

I am not sure we are talking the same thing, so for clarity:

In a normal search where you do not change your mind at the root, the first move takes M units of time, each remaining move takes N. where N is much less than M. Here's real output from a 1 min/move game Crafty played in testing last night:

Code: Select all

         26->  21.65/50.26    0.62   21. Rd1 Re8 22. Nf3 Bc5 23. Bxf6 gxf6 24.
                                     Bf1 h6 25. Rd2 Bb6 26. Re2 Rxe2 27. Bxe2
                                     d4 28. Nh4 Bc8 29. Kg2 Kb7 30. Kf3 c5 31.
                                     Kf4 Ba5 32. Bd3 Bd2+ 33. Ke4 Bd7 34. Ng6
         27    39.31/50.26    0.62   21. Rd1 Re8 22. Nf3 Bc5 23. Re1 Bb4 24.
                                     Rd1 Bc5 25. Bxf6 gxf6 26. Bf1 h6 27. Rd2
                                     Bb6 28. Re2 Rxe2 29. Bxe2 d4 30. Nh4 Bc8
                                     31. Kg2 Kb7 32. Kf3 c5 33. Kf4 Ba5 34.
                                     Bd3 Bd2+ 35. Ke4 Bd7 36. Ng6
         27->  41.81/50.26    0.62   21. Rd1 Re8 22. Nf3 Bc5 23. Re1 Bb4 24.
                                     Rd1 Bc5 25. Bxf6 gxf6 26. Bf1 h6 27. Rd2
                                     Bb6 28. Re2 Rxe2 29. Bxe2 d4 30. Nh4 Bc8
                                     31. Kg2 Kb7 32. Kf3 c5 33. Kf4 Ba5 34.
                                     Bd3 Bd2+ 35. Ke4 Bd7 36. Ng6

It finished depth=26 after 21.65 seconds. It finished the first move at depth=27 after 39.31 seconds. And it searched the remainder of the root moves and completed them all at 41.81 seconds.

first move took 17.66 seconds, rest of the moves in total took 2.5 seconds. If I had searched each root move with a full window, that is 30 moves at around 17 seconds EACH. That search would have taken 31 * 17 = 500 seconds, not 20 seconds. That's a killer. Here is my ply one move ordering, which if you recall is just a simple call to q-search after making each root move:

Code: Select all

31 moves at root
        move   score
         Rd1      85
        Bxf6      73
         Bf4      62
         Nf3      55
         Nb1      19
        cxd5    -129
         Ne4    -230
        Bxd5    -260
         Re1    -287
         Be4    -308
          f4    -309
         Bf3    -318
         Rc1    -320
          h4    -323
          a4    -323
         Rb1    -325
         Kh1    -325
          h3    -325
          a3    -325
         Bd4    -328
         Ra1    -328
         Bh3    -331
          f3    -332
         Bb2    -340
         Ba1    -340
          g4    -342
         Bh1    -347
       Bxc7+    -350
          c5    -364
         Bc3    -415
         Bd6    -447

In this case, ordering was correct from the get-go, but in general it is pretty good overall even when it does change its mind due to seeing some deeper tactic that the simple q-search did not see. Now here's the question: what is the potential gain for improving move ordering?

Suppose the first move is not best, currently. Crafty will spend 17 seconds on the first, 17 seconds on the one that is better, and 2 seconds on the rest. By spending over 500 seconds, you have better ordering but since you search root moves with a full window, ordering doesn't get you a thing, and it has a HUGE cost.

If you stop doing the full-window searches after some specific depth limit (such as iteration #12 for example) you still incurred that big cost early on for very little benefit. I don't see how it can pay off.

[Eelco de Groot]

I guess it depends a lot on how stable your search is. That taking away the reduction will cause the score to change is normal, but that opening the window will turn the fail high into a fail low can be pretty unlikely if your search is quite stable.

The problem is, opening the window CHANGES the reduction value in that search, because we are now back to this move producing a PV node below it, as opposed to the previous search where it produced a normal null-window (non-PV node) below it. If you reduce PV nodes less, then on this last re-search, you now reduce less, you see more, and those fail high / worse score searches happen a bit more frequently...

I believe that in the past you said, on the Open Chess forum I think, that Crafty accepts a Fail High as best move even if you don't have an exact score yet (when you don't have the result of the last PV search with full open window). If that is true, then more reductions can/will mean more False Fail Highs or FFHs, even if you have the fail safes of re-searches in several steps. That seems completely normal?

Just for comparison, in Stockfish search, 'official' Stockfish at least, 'still' does not do this (I don't know exactly about the Open Chess version that was discussed then in its early stages); in the Rootnode there has to be a full open window search result better than alpha to accept a new move as best, even if the null window search of the new move was better than beta. At all other PV nodes, a null window search better than beta (i.e. not just better than alpha) is accepted immediately without a PV search (because it will refute a move below it and the opponent can likely still pick another move in the parent node).

Code: Select all

// For PV nodes only, do a full PV search on the first move or after a fail
// high &#40;in the latter case search only if value < beta&#41;, otherwise let the
// parent node fail low with value <= alpha and to try another move.
if &#40;PvNode && &#40;pvMove || &#40;value > alpha && &#40;RootNode || value < beta&#41;)))
    value = newDepth < ONE_PLY ?
                    givesCheck ? -qsearch<PV,  true>&#40;pos, ss+1, -beta, -alpha, DEPTH_ZERO&#41;
                               &#58; -qsearch<PV, false>&#40;pos, ss+1, -beta, -alpha, DEPTH_ZERO&#41;
                               &#58; - search<PV, false>&#40;pos, ss+1, -beta, -alpha, newDepth, false&#41;;

From what you said in the past, I think Crafty does not do this, but with heavier reductions, would it not be a reasonable try to test this?

Eelco