singular moves

[Daniel Shawul]

Duplicate

[Daniel Shawul]

Quote from you

I don't see they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

You said the difference between the two programs is one ply which is completely wrong. We (I count three) tried to point out to you the difference in nominal depth is more than that.You completely forgot the recursive part there. I think this issue is done and dusted, unless you still insist on that the difference in nominal
depth between program A and B is still 1.


Moving on, right from the beginning when I asked the question ,I was talking about the case where we have a singular move, and whether to decide to extend the singular move Or reduce the non-singular moves.If there is no singular move at a node , no reductions or extensions are done. It doesn't make sense to reduce the non-relevant part of the tree. So lets discuss this case in particular.

[Daniel Shawul]

What about tree explosion that Uri gave example for ? If you do only reductions , you never have tree explosions. So with this trivial fact one can easily refute your "identical tree" claim.

[Gerd Isenberg]

Quote from you

I don't see they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

You said the difference between the two programs is one ply which is completely wrong. We (I count three) tried to point out to you the difference in nominal depth is more than that.You completely forgot the recursive part there. I think this issue is done and dusted, unless you still insist on that the difference in nominal
depth between program A and B is still 1.


Moving on, right from the beginning when I asked the question ,I was talking about the case where we have a singular move, and whether to decide to extend the singular move Or reduce the non-singular moves.If there is no singular move at a node , no reductions or extensions are done. It doesn't make sense to reduce the non-relevant part of the tree. So lets discuss this case in particular.

This tree might be a result of a depth = 1 (only extensions, up to two), depth = 2 (extensions and reductions, one each) or depth = 3 (only reductions, up to two here) search.

Code: Select all

                (P)
               / | \
             /   |   \
           /     |     \
         /       |       \
       /         |         \
     [P]        [C]        [C]
    / | \        |          
   /  |  \       |          
 (P) (C) (C)    (A)       
 /|\  |   
[PCC][A]
  
  3   3   2      2           1                                   

So it seems a matter to tune the extension and reduction conditions accordantly, which might be hard to archive in practice without fractions at least. Too much reductions still has qsearch, too much extentions might deal with pathological tree explosions. Therefor the reduction approach seems safer with that respect, e.g. multi-cut with C == 2 versus SE.

[bob]

Quote from you

I don't see they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

You said the difference between the two programs is one ply which is completely wrong. We (I count three) tried to point out to you the difference in nominal depth is more than that.You completely forgot the recursive part there. I think this issue is done and dusted, unless you still insist on that the difference in nominal
depth between program A and B is still 1.


Moving on, right from the beginning when I asked the question ,I was talking about the case where we have a singular move, and whether to decide to extend the singular move Or reduce the non-singular moves.If there is no singular move at a node , no reductions or extensions are done. It doesn't make sense to reduce the non-relevant part of the tree. So lets discuss this case in particular.

Please re-read. I did not say "one ply always". For the example I gave, where we were just searching one ply, the difference would be one ply. But I clearly said, several times, that the depths will be different, not different by just 1 ply, but the trees will be identical, given identical amounts of search time.

Then you are talking about 3 classes of moves, as I originaly mentioned. Some you reduce, some you extend, and some you do nothing about. As an equivalent alternative, you could reduce some by 2 plies, some by 1 plies, and some not at all, and achieve the _same_ result. That's been my point. Extensions and reductions are opposites that achieve the same results if applied in the opposite way.

For SE, you could extend singular moves, or reduce everything else. If you are already reducing many moves, reduce the ones you normally reduce by 2 plies, reduce all that is left (except a singular move) by 1 ply, and don't reduce the singular move at all. Same result in the same amount of time.

[bob]

What about tree explosion that Uri gave example for ? If you do only reductions , you never have tree explosions. So with this trivial fact one can easily refute your "identical tree" claim.

Again, the two cases are _identical_. I can't imagine anyone extending checks by 3 plies. For realistic values such as the usual -1, 0 and +1 (reductions, normal moves and checks) the results will end up being the same given equal time. If I extend checks by 3 plies, I will have a problem. If I reduce everything but checks by 3 plies I will _still_ have a problem in that I will have great difficulties reaching reasonable depth along the checking path, for the same reason.

[bob]

That was the point of my comments. You can extend, or reduce, or do nothing, which is exactly the same as extending 2, extending 1 or doing nothing. The depths will differ, but in the same time, they will all coverge to exactly the same score and PV (hash issues notwithstanding, of course).

Are you sure they will converge to the same score and PV? For example, Program B would have a lower branching factor, wouldn't it? So with increasing time, wouldn't Program B get an advantage slowly?

How? You have 2 sets of moves. A and B. How is extending A and leaving B alone any different than leaving A alone and reducing B? All B moves are searched one ply deeper than the A moves. yes, you will report different search depths. But the final result will be _exactly_ the same.

I don't see how they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply (the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

This is simply not true. From the point of view of one node, what you say is right, but doing this recursively makes it wrong. Take your example of extending normal moves by 1, good moves by 2, and doing nothing with bad moves. Suddenly a 1-ply search becomes infinite, going through all the lines with just normal moves. OTOH in the same 1-ply search, a bad move at the root only gets searched 0 ply (qsearch). So the two searches cannot be equivalent.

EDIT: And now that I think about it, it's not always equivalent in the case of one node. Reductions are completely meaningless in a 1-ply search (all moves drop straight into qsearch), and generally reductions of >=N ply are all the same in an N ply search. So the easy case of {-1, 0, 1} (as a set of depths to add to bad, normal, and good moves) is not equivalent to { 0, 1, 2 } in a 1-ply search but rather { 1, 1, 2}.

If you _ignore_ the depth, this is not an issue. So long as I search all checking moves one ply deeper than non-checking moves, I _must_ search the same tree at some point, even though the number of iterations might well be different. Who cares? Time will be the same.

No, it is still an issue. I gave two very specific examples where you are wrong, and the two extension schemes cannot be equivalent. They both rely on the boundary case of reducing when the depth is already zero. If you say I'm wrong, then you're going to have to refute the examples somehow.

Think about it this way: your two schemes have the equivalent of adding a depth to every move. At the root, this is fine, you can subtract the depth from the nominal depth, and then those iterations will be equivalent, as long as you only extend/reduce at the root node, and you don't run into boundary conditions where you reduce more than the depth to search. But think about doing this recursively: for each node you extend/reduce in, you are adding a constant into the nominal depth. The problem is that you are reducing and extending moves differently. In some lines, you add the constant more times than others.

And all of this is completely ignoring the effects of nullmove, iterative deepening, hashing, etc. If you don't believe me, turn off every search trick in Crafty, just pure A/B. Do a 10-ply search (no iterative deepening) with the set of extensions { -1, 0, 1}--the "normal" way--and then try to find any depth you can pass in that will give you the exact same tree when adding a depth of one to every move, the extension set { 0, 1, 2 }. It's not going to happen.

Back up the trolley a minute. _nobody_ extends by 2 plies. And I never gave that as an example. I spoke _only_ in terms of reductions. If you normally reduce some, extend some, and leave the rest alone, then you can get an equivalent result by reducing the old 1-ply-reduction moves by 2, the old 1-ply extensions by zero, and the old no-reduction-extension moves by 1. That will _never_ explode. One _can_ do the 0,+1,+2 extension idea but one has to treat the term "ply" differently to avoid an infinite tree.

So let's take the usual -1, 0 and +1 and compare it to -2, -1 and 0, only, and forget about 0, +1 and +2 which is absolutely meaningless. Even +1 is dangerous as it can lead to a nearly-infinite tree bounded only by the 50-move rule and/or repetitions.

In a current search, every move at every ply is already reduced by 1 move to make the search terminate. So in this scheme, using anything over +1 is fatal, unless it is limited somehow. The first simple equivalence would be to not reduce the remaining depth as we step deeper into the tree, then even the depths would be reported as the same.

[Gerd Isenberg]

Quote from you

I don't see they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

You said the difference between the two programs is one ply which is completely wrong. We (I count three) tried to point out to you the difference in nominal depth is more than that.You completely forgot the recursive part there. I think this issue is done and dusted, unless you still insist on that the difference in nominal
depth between program A and B is still 1.


Moving on, right from the beginning when I asked the question ,I was talking about the case where we have a singular move, and whether to decide to extend the singular move Or reduce the non-singular moves.If there is no singular move at a node , no reductions or extensions are done. It doesn't make sense to reduce the non-relevant part of the tree. So lets discuss this case in particular.

Please re-read. I did not say "one ply always". For the example I gave, where we were just searching one ply, the difference would be one ply. But I clearly said, several times, that the depths will be different, not different by just 1 ply, but the trees will be identical, given identical amounts of search time.

Then you are talking about 3 classes of moves, as I originaly mentioned. Some you reduce, some you extend, and some you do nothing about. As an equivalent alternative, you could reduce some by 2 plies, some by 1 plies, and some not at all, and achieve the _same_ result. That's been my point. Extensions and reductions are opposites that achieve the same results if applied in the opposite way.

For SE, you could extend singular moves, or reduce everything else. If you are already reducing many moves, reduce the ones you normally reduce by 2 plies, reduce all that is left (except a singular move) by 1 ply, and don't reduce the singular move at all. Same result in the same amount of time.

Ahh, I got it. On extension of singular move versus reductions of all its sibling moves, while keeping nodes without singular moves uneffected, Daniel is of course right with different trees. Sample with one singular move s:
depth 2, x - extension of singular moves (r some LMR)

Code: Select all

                (P)
               / | \
             /   |   \
           /     |     r
         /       |       \
       /         |         \
     [P]        [C]        [C]
    s | \        |         
   x  |  \       |         
 (P) (C) (C)    (A)
 /|\  
[PCC]

to get the same tree with depth 3, requires not only reducing the siblings of a singular moves bit also all other moves.

Code: Select all

                (P)
               / | \
             /   |   \
           /     r     r
         /       |       r
       /         |         \
     [P]        [C]        [C]
    s | \        |         
   /  r  r       |         
 (P) (C) (C)    (A)
 /|\  
[PCC]

Daniel's question was about this different tree, also depth 3, but only reduction of siblings of singular moves

Code: Select all

                (P)
               / | \
             /   |   \
           /     |     r
         /       |       \
       /         |         \
     [P]        [C]        [C]
    s | \        |          | 
   /  r  r       |          |
 (P) (C) (C)    (A)        (A)
 /|\            /|\       
[PCC]          [CCC]

Both upper trees already look like implicit LMR.

I don't think there is a general answer. Depends on how singularity is determined. Already searched the youngest brother with nominal depth to fail high or improve alpha, and use a reduced search of all siblings to prove they are all worse by margin, implies re-search the singular move with an extended depth.

[jwes]

Quote from you

I don't see they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

You said the difference between the two programs is one ply which is completely wrong. We (I count three) tried to point out to you the difference in nominal depth is more than that.You completely forgot the recursive part there. I think this issue is done and dusted, unless you still insist on that the difference in nominal
depth between program A and B is still 1.


Moving on, right from the beginning when I asked the question ,I was talking about the case where we have a singular move, and whether to decide to extend the singular move Or reduce the non-singular moves.If there is no singular move at a node , no reductions or extensions are done. It doesn't make sense to reduce the non-relevant part of the tree. So lets discuss this case in particular.

Please re-read. I did not say "one ply always". For the example I gave, where we were just searching one ply, the difference would be one ply. But I clearly said, several times, that the depths will be different, not different by just 1 ply, but the trees will be identical, given identical amounts of search time.

Then you are talking about 3 classes of moves, as I originaly mentioned. Some you reduce, some you extend, and some you do nothing about. As an equivalent alternative, you could reduce some by 2 plies, some by 1 plies, and some not at all, and achieve the _same_ result. That's been my point. Extensions and reductions are opposites that achieve the same results if applied in the opposite way.

For SE, you could extend singular moves, or reduce everything else. If you are already reducing many moves, reduce the ones you normally reduce by 2 plies, reduce all that is left (except a singular move) by 1 ply, and don't reduce the singular move at all. Same result in the same amount of time.

If what you mean is:

depth += {-1,0,1}(depending on reductions/extensions)
value = search(tree, alpha, beta, depth-1);

is the same as:

depth += {0,1,2}(depending on reductions/extensions)
value = search(tree, alpha, beta, depth-2);

then it is trivially true. If you mean something else, then you will have difficulty having the same tree. I think most of the posters had something else in mind.

[bob]

Quote from you

I don't see they could behave otherwise, once you think about it a bit. You just have to ignore the "depth" number since the two will be off by one ply the one that reduces everything but checks will search one ply deeper in the same time required by the one that extends only checks to reach depth N-1.

You said the difference between the two programs is one ply which is completely wrong. We (I count three) tried to point out to you the difference in nominal depth is more than that.You completely forgot the recursive part there. I think this issue is done and dusted, unless you still insist on that the difference in nominal
depth between program A and B is still 1.


Moving on, right from the beginning when I asked the question ,I was talking about the case where we have a singular move, and whether to decide to extend the singular move Or reduce the non-singular moves.If there is no singular move at a node , no reductions or extensions are done. It doesn't make sense to reduce the non-relevant part of the tree. So lets discuss this case in particular.

Please re-read. I did not say "one ply always". For the example I gave, where we were just searching one ply, the difference would be one ply. But I clearly said, several times, that the depths will be different, not different by just 1 ply, but the trees will be identical, given identical amounts of search time.

Then you are talking about 3 classes of moves, as I originaly mentioned. Some you reduce, some you extend, and some you do nothing about. As an equivalent alternative, you could reduce some by 2 plies, some by 1 plies, and some not at all, and achieve the _same_ result. That's been my point. Extensions and reductions are opposites that achieve the same results if applied in the opposite way.

For SE, you could extend singular moves, or reduce everything else. If you are already reducing many moves, reduce the ones you normally reduce by 2 plies, reduce all that is left (except a singular move) by 1 ply, and don't reduce the singular move at all. Same result in the same amount of time.

Ahh, I got it. On extension of singular move versus reductions of all its sibling moves, while keeping nodes without singular moves uneffected, Daniel is of course right with different trees. Sample with one singular move s:
depth 2, x - extension of singular moves (r some LMR)

Code: Select all

                (P)
               / | \
             /   |   \
           /     |     r
         /       |       \
       /         |         \
     [P]        [C]        [C]
    s | \        |         
   x  |  \       |         
 (P) (C) (C)    (A)
 /|\  
[PCC]

to get the same tree with depth 3, requires not only reducing the siblings of a singular moves bit also all other moves.

Code: Select all

                (P)
               / | \
             /   |   \
           /     r     r
         /       |       r
       /         |         \
     [P]        [C]        [C]
    s | \        |         
   /  r  r       |         
 (P) (C) (C)    (A)
 /|\  
[PCC]

Daniel's question was about this different tree, also depth 3, but only reduction of siblings of singular moves

Code: Select all

                (P)
               / | \
             /   |   \
           /     |     r
         /       |       \
       /         |         \
     [P]        [C]        [C]
    s | \        |          | 
   /  r  r       |          |
 (P) (C) (C)    (A)        (A)
 /|\            /|\       
[PCC]          [CCC]

Both upper trees already look like implicit LMR.

I don't think there is a general answer. Depends on how singularity is determined. Already searched the youngest brother with nominal depth to fail high or improve alpha, and use a reduced search of all siblings to prove they are all worse by margin, implies re-search the singular move with an extended depth.

I'm talking about something more like what Junior does. Rather than extend, it increments ply by 3 for each iteration, and then rather than always doing depth-3, it varies the "3" to effect an extension. It might change it to 0 or 1 or 2 even. Amir explained his approach several years ago when we were discussing the recapture extension.

But the idea is that you reduce _everywhere_, not just on singular nodes. Think about this:

In a normal search, some moves get searched to depth -1 -1 (if reduce value is 1), some get searched to depth -1 (the normal moves that don't get reduced or extended, say captures or whatever) and some get searched to depth (the ones that get extended to make the recursive call with depth -1 + extension (1);

In my example, I am going to search the moves that would be reduced to depth -1 -2 (depth -3), the captures and other non-reduced / non-extended moves to depth -1 -1 (depth -2), and the moves to be extended to depth -1.

The basic idea is that lousy moves are searched 2 plies less deeply than checking moves, and 1 ply less deeply than the non-reduced moves. Which is exactly what happens in a normal search. But the tree for the reduce-only search will be much smaller. So you have to search deeper to get the same tactical quality (search a specific forcing line to a final mate score). But the time remains the same as does the size of the tree. There are quirks right at the horizon, but so what? The only point is that there are some moves you want to search less deeply, some that you want to search normally, and some you want to search more deeply. How you arrive at that is completely up to you, but the effect on the search space is the same.

Which is better, extending a checking move, or extending when you escape check? Similar idea. Depending on how you handle the frontier nodes, this might make a difference, or it might not. But the overall results are the same.

The only thing you can't do is allow the tree to explode by doing ridiculous things like extending by two plies or whatever. Reductions can have the same effect, since on wild checking lines, you don't reduce much, while you do on the others, so you still can "hang for a long time" following the checking line, just like you do when you extend by 1 ply...

edit:

almost missed your last paragraph. yes, that is exactly what you do once you prove a move is singular, you do a re-search to depth + 1. But there are issues, as Hsu/Campbell pointed out. The singular tests might take a long time, as A is best, then you start searching with a lowered window and reduced depth to attempt to prove singularity, but move B fails high. Now you have a re-test, since you have to get a good score for both A and B (re-search B to normal depth to see if it is significantly better than A) and then repeat. This can be time-consuming in very complex positions. I did this in the last two years of Cray Blitz development. There were a ton of details, and it was quite easy to go nuts extending. pawn-only endgames had to disable this completely, as one case in point that is counter-intuitive.

The way Bruce and I played with this in 1996 was to simply do a reduced-depth search over all moves. After getting the first result back, we lowered the window for the rest of the moves and hoped they all failed low. If so, we flagged the "best move" as singular and passed this into the search. When the real search was done, and this move was chosen for search, it was extended by a ply. It is an expensive test, but it produces some nice PVs. I never got something that I thought was usable, but was not able to do significant testing back then...

Several others took this idea. There was one SE version of Crafty released. I think I still have the SingularSearch() module tucked away to test again one day when other new ideas come less frequently.