singular moves

[Daniel Shawul]

Even better is to not do reductions on nodes without a checking move
in their move list. The object of the selectivity is prefer one move over the other.If you don't have a better move (singular) just search everything at the original depth. This will be better than reducing every non-checking move everywhere, which doesn't make much sense in the first place.

[bob]

Well that surely won't work! Say you have only one singular move somewhere down the tree.
When you extend that move, you increase the depth of the sub-tree below it by 1. Now if you reduce
every non-singular move _everywhere_, the depth would be reduced a lot. Non-singular moves at ply 1 are reduced
by 1, at ply 2 by 1, at ply 3 by 1 etc... will add up to a large reduction. This is _recursive_ !

You are not reading. I simply said "reduce _all_ moves that are not singular." You want to "extend all moves that _are_ singular". The two ideas are absolutely identical. They will search to a different reported depth, but in the same amount of time they will search the _same_ tree, and produce identical results. And yes, that is recursive.

It is not only a one time reduction as you said...So much so that the tree might degenerate into nothing. We need to
have a few moves which are not reduced at every ply to avoid this behaviour (This is much like LMR).

If you want a _non-recursive_ reduction, you apply the reduction for the non-singular moves only at nodes
where you have the singular move.It makes absolutely no sense to reduce the depths of moves outside nodes
where you have that singular move.

I don't understand what part of this simple idea you don't get, but to restate:

(1) if you only extend a certain type of move; or

(2) you reduce all moves except for that same certain type of move;

you will search _exactly_ the same tree. It works perfectly, unless you have some sort of bug. The second option will need to go deeper to reach the same PV and score, but even though it goes deeper, it searches the _same_ tree, in the _same_ amount of time.

There is simply no difference between reducing all except X, or just extending X, so long as the extension/reduction value is the same. If you reduce, you will have to reach a deeper depth to see the same PV, but you will reach that deeper depth in the same amount of time that the extending search takes. And since we play games based on time, we get exactly the same move, exactly the same PV, exactly the same score. Only the depths are reported differently, but that number is meaningless when comparing programs that reduce/extend differently, anyway.

This works, it is a pretty simple idea, once you think about it. At some node P, I can either extend a move one extra ply, or reduce all moves except that move by one ply (and since I am reducing I will get to go one ply deeper before I run out of time) and and reach the same result in the same amount of time.

[bob]

Because you are doing a flawed search. Yes, one search will really search one ply less deeply.

No, it will search _half_ of the _nominal_ plies of the other program, not _one_ ply less deeply. This is because the other program only searches the tree to half of the _nominal_ depth.

No, it will not. If you search to the same reported depth, you would be correct. But I am going to search the same amount of _time_ which will let the reduction-only search reach the _same_ PV.

This is not something open to debate, any more than we would debate whether alpha/beta produces the same result as a pure minimax search (it does).

But it will use far less time and be able to go yet another ply deeper before running out of time.

You will even be able to go twice as deep before running out of time.

Depends. What if every ply has moves that don't get reduced? You can't just blanket say "it will go 2x deeper". You can only safely say "it will search exactly the same tree, given the same time, ignoring the reported depths which can't be compared."

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.

That's true. I only referred to the Program A:Depth N = Program B:Depth N+1 thesis of some people. _That_, however, would be true if you only reduce non-checking moves at the root. But as you reduce non-checking moves everywhere, the consequence is that the "real" search depth of program B is only half of the _reported_ search depth. Consequently, Program B's _reported_ search depth is twice as much as the one of Program A. The _trees_, however, will be identical. The only difference is in the _reported_ search depth, and that's why fixed-depth games are not useful in my opinion because Program A, in that case, would perform better than Program B although they are actually _exactly the same_ program with the only difference being the reported search depth. One can even construct cases in which a program X would perform better in a fixed-depth test although it is actually worse.

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

Would you be willing to hack crafty and prove this, because I believe that you will find it very difficult to have the same search tree using extensions rather than reductions? You might want to use equal nodes rather than time to eliminate jitter.

It has already been done once. The idea is really trivial once you think about it. Ed and I had this _same_ discussion years ago, I did exactly what I suggested, and produced big search depths but identical results. Hashing can introduce some quirks, but that is a different problem.

[bob]

If you really want to see a difference, trying reducing all non-check moves by 3, compared with extending all check moves by 3 .

-Sam

The difference is clear
If you reduce all non check moves by 3 you can get high depth easily that may be equivalent to small depth of other programs but at least you can
always search deep enough to avoid stupid mistakes.

If you extend all checks moves by 3 your search is going to explode and you may never finish depth 1 in some cases if the first move is check because you may have some line like

remaining depth 1
after 1.Qh5+(remaining depth 3)
after 1...Kg8(remaining depth 2)
after 2.Qg5+(remaining depth 4)
after 2...Kf8(remaining depth 3)
...

after 20.Ra4+(remaining depth 22)
....

You may simply miss some mate in 1 because you did not get to search it because you started with the wrong check.

It is clear that reducing all non checks moves by 3 plies is going to be stronger relative to extending all check moves by 3 plies.

Uri

It is only clear that they are going to produce _identical_ results.

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

Daniel, you are simply in way over your head if you can't grasp this simple idea. The two approaches _will_ produce the same tree in the same amount of time. You can even find references to this if you search enough with google. This idea is so simple I do not understand why there is any need to continue arguing about it. It is one of those ideas that most in-depth books would call "intuitively obvious to the casual observer." It is not open to debate, it is a simple statement of fact. Just as when we say "alpha/beta produces the _identical_ result that pure minimax produces, just by searching a much smaller tree." In this case, we get the same results by searching significantly deeper, but in the same amount of time.

[bob]

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.

I do recaptures to avoid horizon effects. The capture recapture will delay tactics after the sequence is done. Bruce moreland's programming website has that as the reason. I though that was why everybody does it. Even if after the capture/re-capture sequence gains nobody nothing, we do it to avoid horizon effects...

"everybody" doesn't do recapture extensions. I do not, for example. The _only_ extension in Crafty is the check extension. This was done during the early cluster testing stuff and was proven to be stronger.

If you search shallow trees, the horizon effect is much stronger and needs such extensions. But the deeper you go, the less this affects the final results because the deeper a tactical issue is in the tree, the less likely it is a really forced pitfall since you have lots of opportunity to deviate in a deep tree.

Code: Select all

What this amounts to is a forcing sequence that I can initiate in order to eat up some depth.  This is most likely a case where I am trying to avoid getting beaten.

So the extension is on the recapture.  An obvious way to implement this is to make the recapture a free ply.

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.

I will look into their paper. But it seems to me from your explanation that the reason for the singular extension is to do "win-seeking or loss-avoiding" (Bruce's terms). They disregard the neutral extensions which help to avoid horizon effects.

Singular extensions get rid of the static extensions pretty much. Anything "static" is generally bad, because it is something with no context driving it. The old "patzer sees check, patzer plays check" comes to mind. I only look at checks that appear to be interesting, as a human, not all checks.

[bob]

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.

I completely agree with this statement.

Doesn't matter whether you agree or not. This is wrong. I've explained why, I'm not going to continue trying to convince you.

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

[Zach Wegner]

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.