bob wrote: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}.
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_ !
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.
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...
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.
bob wrote: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.
bob wrote: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.
bob wrote: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.
Daniel Shawul wrote: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:
Bob wrote: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.
jwes wrote: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.
Why? I think the only difference is the reported search depth.
jwes wrote: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.
Why? I think the only difference is the reported search depth.
The difference is with iterative deepening. Try it and see.
BubbaTough wrote: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.
.