All and Cut nodes

[mcostalba]

How could reducing the quality of the search possibly detect issues?

As I have written above: "So if we expect a node to fail-high at depth n, then we assume it should fail-high also at depth n-1, if this doesn't happen it means position is tricky enough to deserve a research at depth n+1."


I will try to be even more clear.

Question: Ok we have this position that should fail high at depth n. How can be verified if the position does not hide threats or risks ?

Answer: Search at n-1 and see if it _still_ fails high. If it fails high at n-1 then position assumed to be safe. If not then it means we eventually need even up to the last ply to prove it, so position is at border line and it is risky

Question: Ok, this position is risky because at n-1 it does not fails high. What we do next ?

Answer: We research at n+1

[Daniel Shawul]

Thanks for the test and code. From what i understood from the commit notes the explanation for why it may/may not work is not straigth forward and infact you had some failed tests which is interesting. Well I still have trouble getting my head around the fact that reducing by [2ply CUT+1ply ALL = 1ply ALL+2ply CUT], but that is just me. After CUT you go straight to ALL and vice versa. The reductions are recursive so it doesn't matter where the bigger reductions occurred because you are not going to stop there at CUT nodes. I stick with my simplistic explanation for why it may work i.e. that you have more CUT nodes on average, but hey every one seem to have own explanation. Hope you get to the bottom of everything concerning this issue.

[Houdini]

Thanks for the test and code. From what i understood from the commit notes the explanation for why it may/may not work is not straigth forward and infact you had some failed tests which is interesting. Well I still have trouble getting my head around the fact that reducing by [2ply CUT+1ply ALL = 1ply ALL+2ply CUT], but that is just me. After CUT you go straight to ALL and vice versa. The reductions are recursive so it doesn't matter where the bigger reductions occurred because you are not going to stop there at CUT nodes. I stick with my simplistic explanation for why it may work i.e. that you have more CUT nodes on average, but hey every one seem to have own explanation. Hope you get to the bottom of everything concerning this issue.

Miguel explains it very well at the previous page:

"Reducing more at a cut node works as a sort of IID. At a cut node, after few failed attempts, you may be eager to find the move that will fail high as quick as possible (this is the key). One way to explore this quickly is to reduce more, to scan all the moves fast. Once you find the move it fails high, you research it with a proper depth, so you win by skipping all the others with a low depth. What if I do not find the move that fails high? well, in that case, I may want to research ALL of them with a proper depth, since I started with the assumption this is a cut node. But that is not needed, since returning "fail-low" will automatically trigger a research in the parent node, and then the child node will become an ALL node, which will reduce less."

Not sure what more can be said if even this doesn't help.

[Daniel Shawul]

My intake for gibberish is full thank you.

[michiguel]

Reducing more at a cut node works as a sort of IID. At a cut node, after few failed attempts, you may be eager to find the move that will fail high as quick as possible (this is the key). One way to explore this quickly is to reduce more, to scan all the moves fast. Once you find the move it fails high, you research it with a proper depth, so you win by skipping all the others with a low depth.

This sounds indeed a lot my preferred way of doing IID. I usually deepen cut-moves in a separate loop, without going to the next iteration globally. Like:

Code: Select all

Search(depth)
{
  for(iterDepth=1; iterDepth<=depth; iterDepth++) {
    for(ALL_MOVES) {
      MakeMove();
      cutDepth = iterDepth;
      do {
        score = -Search(cutDepth);
      } while(++cutDepth <= depth);
      UnMake();
    }
  }
}

This increases the depth of cut-moves to the required depth as long as they fail high (like the normal IID loop would also do), but only through increasing cutDepth, not iterDepth. (You can of course increment these in steps other than 1.) So that if at any stage the move starts to fail low, you would continue looking for another cut move at the lowest possible depth, switching back to using iterDepth.

On later iterDepth iterations, the moves you have already deepened in the cutDepth loop will be satisfied by immediate hash hits.

If I understand correctly, you are right. This gives a little bit of a "breadth-first-like" flavor to this node.

Miguel

[Michel]

It is interesting to observe that the idea of reducing CUT nodes more works even if none of the ancestor nodes was reduced. Indeed an erroneous fail low at a CUT node is either irrelevant, or else the resulting score will be backed up all the way to a PV node, triggering a PVS research which makes the CUT node into an ALL node!

I know this is all obvious to many people here, but I like the idea so much that I wanted to state it once again for myself!

[Daniel Shawul]

It may or may not work but no one so far answered this simple question I posed. It is important question before we talk about researches. I am saying you can't save depth because AFAIK reducing by 121212 is same as 212121 except rarely at the leaves. eg. For a 22 ply search that started at CUT node somewhere along the search, how do you save big on depth when they both finish at the same ply?

Code: Select all

NT	Depth	CUT=2	ALL=2
CUT	22	22	22
ALL	21	20	21
CUT	20	19	19
ALL	19	17	18
CUT	18	16	16
ALL	17	14	15
CUT	16	13	13
ALL	15	11	12
CUT	14	10	10
ALL	13	8	9
CUT	12	7	7
ALL	11	5	6
CUT	10	4	4
ALL	9	2	3
CUT	8	1	1
ALL	7	-1	0
CUT	6		
ALL	5		
CUT	4		
ALL	3		

[Michel]

Your question is a good one.

The difference might be in the price of a mistake.

If a CUT node fails low erroneously it will often be researched immediately in the parent (if the move leading to the CUT node was reduced).

If an ALL node fails high erroneously this will never trigger a research in the immediate parent.

Of course if the fail low/fail high affects the value of the tree, I think PVS will trigger a research eventually. So it is not so obvious what is better.

[Henk]

Your question is a good one.

The difference might be in the price of a mistake.

If a CUT node fails low erroneously it will often be researched immediately in the parent (if the move leading to the CUT node was reduced).

If an ALL node fails high erroneously this will never trigger a research in the immediate parent.

Of course if the fail low/fail high affects the value of the tree, I think PVS will trigger a research eventually. So it is not so obvious what is better.

My conclusion:
All erroneously fail highs (whether All Node or Cut Node) are dangerous.
But also an evaluation error in the value of the selected "best move"

[Daniel Shawul]

Your question is a good one.

The difference might be in the price of a mistake.

If a CUT node fails low erroneously it will often be researched immediately in the parent (if the move leading to the CUT node was reduced).

If an ALL node fails high erroneously this will never trigger a research in the immediate parent.

Of course if the fail low/fail high affects the value of the tree, I think PVS will trigger a research eventually. So it is not so obvious what is better.

Ok at least we got that depth saving out of the way. The way I see it

Code: Select all

CUT node fail low = ALL node fail high
CUT node fail high = ALL node fail low

Ofcourse there is a one ply difference there but not so much otherwise so I don't see how it helps big (if it does at all). Some explanation offered here was that it works like Enhanced transposition cutoffs (ETC). You visit all the moves at CUT nodes with reduced depth first to see if their is a fail high. This doesn't work if you see that you are doing reductions recursively. That ETC type of assumptions assumes you reduce big at CUT nodes once (which is your saving if you get fail high) but in reality you might as well reduce big at ALL nodes for the same effect.
Anyway I think that anyone can come up with possible reasons, even Henk's idea is making sense to me , who woulda thought that