singular moves

[Daniel Shawul]

There are lots of other classes of singular moves besides the ones you mention. In fact, the ones you mention were _specifically_ excluded in the DB singular extensions paper. You don't want to extend recaptures. Those are non-interesting. If the recap is not best, you are already screwed. But what about the subtle moves that create a threat that leave you with just one way to defend against it? That "one way to defend" move is interesting and needs to be searched deeper to see if it _really_ defends or just postpones.

This is new information for me. Sure I do not extend loosing recaptures too. But why would you not want to extend if the recapture seems even or better ? The point of the recapture is to compensate for the depth lost due to the capture-recapture sequence. Single reply to check could also delay threats.Why do you want to exclude single reply to check or winning captures from the singular moves ?

[/quote]

[Michael Sherwin]

if singular move extensions do work, why do we spend time
proving that the most obvious singular moves (single reply to check
and recapture extenensions) are useless ? Or is it that the non-obvious
singular moves (may be non-captures found by shallow search) are more important
than the obvious ones ? We usually don't reduce the obvious singular moves. Most
don't reduce the first move or captures. So extending those could be redundant in a way
because we never reduce them in the first place. But singular non-captures could get reduced.
Another form of favouring singular moves, could be to reduce all but the singular move.
For example when you have a winning capture (foretold by SEE) then reduce the rest of the moves
by a ply. I presume extending the singular winning capture, and doing nothing on the rest should
give the same effect. But again captures are never reduced by LMR so this extention/reduction could
be redundant. My question is if LMR changed the picture regarding singular moves.

I am also not convinced if the two methods, extending the singular move AND reducing all but the singular moves,
have the same effect. Simplest case is the single reply to check extension. Here we can not use the second method
because we only have one move, so we end up doing nothing. But in the first case we may search a d+1 sub tree.
So the trees searched by the two methods are different. If that happens at the root, it is like doing a d+1 ID ,but not
otherwise. This simple case study made me think that the above methods of doing selectivity may not give similar results when
we have a few moves ?? Doing selectivity (pruning/extensions) for the first few moves and later moves may have a different
effect, basically becuase the differnce in size of sub-treees under those moves is significantly different.
So may be reducing non-singular moves when we have a singlular move is an idea worth testing.

I appreciate your thoughts.

Daniel

Here is another way to think about extending the search through reductions. Since all reductions in depth searched can miss tactics, all methods involve a trade off. Most extensions fail because the trade off is negative. Take for example extending all permanent change of position moves. It makes sense to the novice to try this, but it is weakening. Then the novice will try extending all non permanent change of position moves. This is also weakening (maybe not as much though). The lesson is that there are tactics in both kinds of lines. But, what I wonder is if (deep) tactics tend to group themselves in one or the other for any given position. If they do then it is possible to do two really deep searches in less time for each root move (maybe separate hashes needed) and then compare their values. Then the value worse for the engine can be assigned or further processing can be done. Just some thoughts.

[metax]

Two points to consider.
a) The extension/reductions are not necessarily done at the root. Program B's N+1 th iteration
will be same as A's Nth below the node where selectivity is applied. When B does its N+1 th iteration
it spends more work on other parts of the tree first, then when it reaches that node where selectivity is
applied everything below will be similar. B's N+1 th iteration is D + 1 _everywhere_ and D at reduced moves,
and A's Nth iteration D everywhere, and D + 1 only at the check move.I think A's way of doing it is more aggressive and hence why
it sometimes leads to tree explosions.

b) As I tried to point out with the specific case of single reply to check, if we simplify Program A and B's behaviour to the
absurd, Program A's behaviour will be to extend single replies, and Program B's is to do nothing. We already
know that Program A will have higher BF with the extension (at least for me). The reason why we been doing it is that
the selectivity will result in a better search overall. Note here that if the single reply extension was done only at the
root, the behaviour would have been the same.Taking this further, where the good moves take a lot more nodes than the bad ones (which is usually the case),
similar behaviour could be found.

Maybe you misread or misunderstood Bob's example:

Here's a question to ponder. Program A extends checks by 1 ply. And nothing else. Program B reduces everything but checks by 1 ply. How do they compare?

So iteration N of program A does depth N+1 if there is one check on the move path, and depth N everywhere else (I don't care about move paths with more than one check here). Iteration N+1 of program B does depth N+1 for the non-reduced checks, and depth N everywhere else. I can only see a difference for some leaf nodes where the last move gives check but program B does not extend checks. This should not make a huge difference - but o.k., it is not 100% perfectly the same search. At least the overall number of nodes searched by A and B would be very close, so A would finish N roughly when B finishes N+1.

@Bob: I hope I have interpreted your example correctly.

Sven

No, I don't think so. Let's regard a four-ply search and a move sequence of four plies without any checks first:

Program A will search the move sequence to a depth of four plies + qsearch.
Program B, however, will NOT search the move sequence to a depth of three plies, but only to a depth of two plies.

Why?

Given a Search() function which has the remaining depth to horizon as only parameter,
program A searches: RootSearch() calls (move 1) Search(3) calls (move 2) Search(2) calls (move 3) Search(1) calls (move 4) Search(0) which immediately returns Qsearch().
Program B searches: RootSearch calls (move 1) Search(2) calls (move 2) Search(0) which immediately returns Qsearch().

So Program B will search only HALF of the search depth of Program A.
However, Program B will reach the double nominal depth of program A. So PV and evaluation of Program B and A after a certain time _are_ equivalent.

Program B actually _has_ a lower branching factor than program A (EBF(B) = sqrt(EBF(A))) and can thus finish two _nominal_ plies when program A searches only one. _However_, this has no consequences for the difference of playing strength between B and A because two _nominal_ plies of program B are equivalent to _one_ ply of Program A.

Conclusion: Program B searches to a nominal depth which is twice as much as the one of program A. However, playing strength, PV and evaluation are exactly the same.

[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.

[bob]

Two points to consider.
a) The extension/reductions are not necessarily done at the root. Program B's N+1 th iteration
will be same as A's Nth below the node where selectivity is applied. When B does its N+1 th iteration
it spends more work on other parts of the tree first, then when it reaches that node where selectivity is
applied everything below will be similar. B's N+1 th iteration is D + 1 _everywhere_ and D at reduced moves,
and A's Nth iteration D everywhere, and D + 1 only at the check move.I think A's way of doing it is more aggressive and hence why
it sometimes leads to tree explosions.

b) As I tried to point out with the specific case of single reply to check, if we simplify Program A and B's behaviour to the
absurd, Program A's behaviour will be to extend single replies, and Program B's is to do nothing. We already
know that Program A will have higher BF with the extension (at least for me). The reason why we been doing it is that
the selectivity will result in a better search overall. Note here that if the single reply extension was done only at the
root, the behaviour would have been the same.Taking this further, where the good moves take a lot more nodes than the bad ones (which is usually the case),
similar behaviour could be found.

If you treat different nodes differently, then things might not be the same. But why would no not extend or reduce at the root, assuming you extend and reduce everywhere else? I certainly do.

As far as checks at the root, you are not thinking carefully. Suppose you do not extend "in check" at the root on one version, and you do on the other. Nothing else changes. How does this affect things? On positions where you start off in check, the program that extends will search one ply less deep in the same amount of time, because it extends every move to escape check. The program that does not extend will search one ply deeper. Yet they produce the exact same tree size, PV and score.

[bob]

Two points to consider.
a) The extension/reductions are not necessarily done at the root. Program B's N+1 th iteration
will be same as A's Nth below the node where selectivity is applied. When B does its N+1 th iteration
it spends more work on other parts of the tree first, then when it reaches that node where selectivity is
applied everything below will be similar. B's N+1 th iteration is D + 1 _everywhere_ and D at reduced moves,
and A's Nth iteration D everywhere, and D + 1 only at the check move.I think A's way of doing it is more aggressive and hence why
it sometimes leads to tree explosions.

b) As I tried to point out with the specific case of single reply to check, if we simplify Program A and B's behaviour to the
absurd, Program A's behaviour will be to extend single replies, and Program B's is to do nothing. We already
know that Program A will have higher BF with the extension (at least for me). The reason why we been doing it is that
the selectivity will result in a better search overall. Note here that if the single reply extension was done only at the
root, the behaviour would have been the same.Taking this further, where the good moves take a lot more nodes than the bad ones (which is usually the case),
similar behaviour could be found.

Maybe you misread or misunderstood Bob's example:

Here's a question to ponder. Program A extends checks by 1 ply. And nothing else. Program B reduces everything but checks by 1 ply. How do they compare?

So iteration N of program A does depth N+1 if there is one check on the move path, and depth N everywhere else (I don't care about move paths with more than one check here). Iteration N+1 of program B does depth N+1 for the non-reduced checks, and depth N everywhere else. I can only see a difference for some leaf nodes where the last move gives check but program B does not extend checks. This should not make a huge difference - but o.k., it is not 100% perfectly the same search. At least the overall number of nodes searched by A and B would be very close, so A would finish N roughly when B finishes N+1.

@Bob: I hope I have interpreted your example correctly.

Sven

You are doing just fine. This identical issue comes up every 2-3 years, goes around the same circles until everyone thinks about it carefully...

[bob]

So iteration N of program A does depth N+1 if there is one check on the move path, and depth N everywhere else (I don't care about move paths with more than one check here). Iteration N+1 of program B does depth N+1 for the non-reduced checks, and depth N everywhere else. I can only see a difference for some leaf nodes where the last move gives check but program B does not extend checks. This should not make a huge difference - but o.k., it is not 100% perfectly the same search. At least the overall number of nodes searched by A and B would be very close, so A would finish N roughly when B finishes N+1.

I think you should look into both of my comments more carefully. It is not specific to checking moves rather to all singular moves. The question is when you have a singular move , do you want to extend that singular move or reduce every other move on that node ? I tried to point out the behavior is the same if the singular move is at the root (no other selectivity below it). Program B searches same tree at its N+1th iteration as B does at its N.

If I understand correctly, when Bob says everywhere he is talking about nodes where you have a singular move. It doesn't make sense to reduce moves at a node where there is no singular move. I suspect the search would degenerate into nothing if you reduce every non-singular move at every node.

No, that is not what I am saying. I am saying that you can either (a) extend singular moves everywhere, and extend nothing else; or (b) reduce non-singular moves everywhere. They produce the same trees, the same everything, _except_ for the reported search depth, which will be off by one, where the one that reduces all non-singular moves will go one ply deeper than the other, but with the exact same score and PV and tree size (nodes)

[bob]

Two points to consider.
a) The extension/reductions are not necessarily done at the root. Program B's N+1 th iteration
will be same as A's Nth below the node where selectivity is applied. When B does its N+1 th iteration
it spends more work on other parts of the tree first, then when it reaches that node where selectivity is
applied everything below will be similar. B's N+1 th iteration is D + 1 _everywhere_ and D at reduced moves,
and A's Nth iteration D everywhere, and D + 1 only at the check move.I think A's way of doing it is more aggressive and hence why
it sometimes leads to tree explosions.

b) As I tried to point out with the specific case of single reply to check, if we simplify Program A and B's behaviour to the
absurd, Program A's behaviour will be to extend single replies, and Program B's is to do nothing. We already
know that Program A will have higher BF with the extension (at least for me). The reason why we been doing it is that
the selectivity will result in a better search overall. Note here that if the single reply extension was done only at the
root, the behaviour would have been the same.Taking this further, where the good moves take a lot more nodes than the bad ones (which is usually the case),
similar behaviour could be found.

Maybe you misread or misunderstood Bob's example:

Here's a question to ponder. Program A extends checks by 1 ply. And nothing else. Program B reduces everything but checks by 1 ply. How do they compare?

So iteration N of program A does depth N+1 if there is one check on the move path, and depth N everywhere else (I don't care about move paths with more than one check here). Iteration N+1 of program B does depth N+1 for the non-reduced checks, and depth N everywhere else. I can only see a difference for some leaf nodes where the last move gives check but program B does not extend checks. This should not make a huge difference - but o.k., it is not 100% perfectly the same search. At least the overall number of nodes searched by A and B would be very close, so A would finish N roughly when B finishes N+1.

@Bob: I hope I have interpreted your example correctly.

Sven

No, I don't think so. Let's regard a four-ply search and a move sequence of four plies without any checks first:

Program A will search the move sequence to a depth of four plies + qsearch.
Program B, however, will NOT search the move sequence to a depth of three plies, but only to a depth of two plies.

Why?

Because you are doing a flawed search. Yes, one search will really search one ply less deeply. But it will use far less time and be able to go yet another ply deeper before running out of time. Trust me. The trees will be _identical_ given the same amount of time. If you use the same depth, then the one that extends will be stronger than the one that reduces, because the one that extends will take far longer per move than the one that doesn't. But that is not a reasonable way to compare either, as this is getting hung up on the "reported search depth" which is irrelevant. All that is important is what will be searched by each program given the same amount of time. The answer is the same tree.

Given a Search() function which has the remaining depth to horizon as only parameter,
program A searches: RootSearch() calls (move 1) Search(3) calls (move 2) Search(2) calls (move 3) Search(1) calls (move 4) Search(0) which immediately returns Qsearch().
Program B searches: RootSearch calls (move 1) Search(2) calls (move 2) Search(0) which immediately returns Qsearch().

So Program B will search only HALF of the search depth of Program A.
However, Program B will reach the double nominal depth of program A. So PV and evaluation of Program B and A after a certain time _are_ equivalent.

Program B actually _has_ a lower branching factor than program A (EBF(B) = sqrt(EBF(A))) and can thus finish two _nominal_ plies when program A searches only one. _However_, this has no consequences for the difference of playing strength between B and A because two _nominal_ plies of program B are equivalent to _one_ ply of Program A.

Conclusion: Program B searches to a nominal depth which is twice as much as the one of program A. However, playing strength, PV and evaluation are exactly the same.

[bob]

There are lots of other classes of singular moves besides the ones you mention. In fact, the ones you mention were _specifically_ excluded in the DB singular extensions paper. You don't want to extend recaptures. Those are non-interesting. If the recap is not best, you are already screwed. But what about the subtle moves that create a threat that leave you with just one way to defend against it? That "one way to defend" move is interesting and needs to be searched deeper to see if it _really_ defends or just postpones.

This is new information for me. Sure I do not extend loosing recaptures too. But why would you not want to extend if the recapture seems even or better ? The point of the recapture is to compensate for the depth lost due to the capture-recapture sequence. Single reply to check could also delay threats.Why do you want to exclude single reply to check or winning captures from the singular moves ?

why would you want to extend a move that is _obviously_ the best move, which is exactly what a recapture is, when it is singular? You don't want to extend things that are obvious, you want to extend things that appear to be difficult to deal with. That is why the single-reply-to-check extension works so well in tactical positions, because if you have only one move, you really want to be sure that the score you get back is accurate, because once you reach this point in the game, you will have no alternative in case you suddenly see a problem now that you are deeper into the game/position.

You should find Campbell's SE paper in the JICCA and read it carefully, it explains all of this carefully and also points out other issues, such as a move that appears singular when doing iteration N, but then looks to be non-singular during iteration N+1. That can lead to search instabilities that they addressed with a "sticky transposition table" idea.

[bob]

if singular move extensions do work, why do we spend time
proving that the most obvious singular moves (single reply to check
and recapture extenensions) are useless ? Or is it that the non-obvious
singular moves (may be non-captures found by shallow search) are more important
than the obvious ones ? We usually don't reduce the obvious singular moves. Most
don't reduce the first move or captures. So extending those could be redundant in a way
because we never reduce them in the first place. But singular non-captures could get reduced.
Another form of favouring singular moves, could be to reduce all but the singular move.
For example when you have a winning capture (foretold by SEE) then reduce the rest of the moves
by a ply. I presume extending the singular winning capture, and doing nothing on the rest should
give the same effect. But again captures are never reduced by LMR so this extention/reduction could
be redundant. My question is if LMR changed the picture regarding singular moves.

I am also not convinced if the two methods, extending the singular move AND reducing all but the singular moves,
have the same effect. Simplest case is the single reply to check extension. Here we can not use the second method
because we only have one move, so we end up doing nothing. But in the first case we may search a d+1 sub tree.
So the trees searched by the two methods are different. If that happens at the root, it is like doing a d+1 ID ,but not
otherwise. This simple case study made me think that the above methods of doing selectivity may not give similar results when
we have a few moves ?? Doing selectivity (pruning/extensions) for the first few moves and later moves may have a different
effect, basically becuase the differnce in size of sub-treees under those moves is significantly different.
So may be reducing non-singular moves when we have a singlular move is an idea worth testing.

I appreciate your thoughts.

Daniel

This is about moves, rather than trees. Some moves ought to be extended. Some should not. How you implement that is a personal choice. You can choose to reduce the moves that should not be extended, and not reduce the rest, which gives you an effect just like extending some and not extending others.

We are (today) doing a 3-level approach. We extend some moves a lot. Others less. Others not at all. We make this happen by really extending some, not extending or reducing some, and reducing the rest, giving us three classes of moves.

I did not find any use for the single-reply-to-check extension and have not been using anything except for a "check" extension for a couple of years. Singular extensions are a completely different topic from this, as one-legal-reply is a very narrow subset of the entire class of "singular moves".

I wonder if you try to restrict the single reply to check to part of the cases.

For example you may restrict it to the cases when the side that reply to check(I will call him the defender) is not losing based on evaluation after the single reply(evaluation not more than 2 pawns against the defender after the single reply)

The point is that if the defender is already losing then this evaluation
is not going to be changed most of the time so extending is a waste of time and you may extend some simple winning endgames of many pieces against a single king because of checks that force the next move of the weaker side.

I think that it is better also not to have the check extension in these cases
and it is better to have check extension only if the attacker is not obviously winning.

Uri

I have tried some of that. And had no success. You could extend except when winning, or extend except when losing, or extend except when inside the root alpha/beta window. Or the opposite of any of those. I never had any success although I have not tried this recently.

I'm personally more interested in the cases as described by Hsu/Campbell, where one side has one move, and that one move is the only move that holds off a significant threat by the opponent. The question is, does it _really_ hold off the threat, or is it a horizon-type move that just postpones the "punch line" beyond the horizon of the search? Extending is one way to more carefully evaluate things to answer that question.