All and Cut nodes

[lucasart]

Code: Select all

if (node_type == PV && first)
   // search full window
   score = -search(B, -beta, -alpha, new_depth, PV, ss+1);
else
{
   // zero window search (reduced)
   // we expect the child node to fail high, so we predict a 'Cut' node, right ?
   score = -search(B, -alpha-1, -alpha, new_depth - ss->reduction, Cut, ss+1);

   // doesn't fail low: verify at full depth, with zero window
   if (score > alpha && ss->reduction)
      // we expect the child node to fail low again, so we predict a 'All' node, right ?
      score = -search(B, -alpha-1, -alpha, new_depth, All, ss+1);

   // still doesn't fail low at PV node: full depth and full window
   if (node_type == PV && score > alpha)
      score = -search(B, -beta, -alpha, new_depth , PV, ss+1);
} 

doing it this way you tell the engine to search a first CUT node and it it fail an ALL node, but you don't tell anything about their child.

If you search a node as a CUT node then you search all his child as a cut node too ..
maybe you can find some idea here http://chessprogramming.wikispaces.com/ ... rd+Pruning

Yes, indeed. This code should hopefully be correct:

Code: Select all

if (node_type == PV && first)
	// search full window
	score = -search(B, -beta, -alpha, new_depth, PV, ss+1);
else
{
	const int prediction = node_type == PV ? Cut : (node_type == Cut ? All : Cut);

	// zero window search (reduced)
	score = -search(B, -alpha-1, -alpha, new_depth - ss->reduction, prediction, ss+1);

	// doesn't fail low: verify at full depth, with zero window
	if (score > alpha && ss->reduction)
/* should we do 'All' or 'prediction' here ? we expect the child to fail low (with or without reduction). but at the same time, we need to give it a chance to fail high, so if search behaves differently for types of nodes, this can be dangerous. */
		score = -search(B, -alpha-1, -alpha, new_depth, prediction, ss+1);

	// still doesn't fail low at PV node: full depth and full window
	if (is_pv && score > alpha)
		score = -search(B, -beta, -alpha, new_depth , PV, ss+1);
}

What do you think about the node type of the re-search at full depth (when reduced search fails low) ?

[elcabesa]

i really don't know, maybe CUT, because it has not failed down.

how do you think to make different CUT and ALL node search ?

[lucasart]

i really don't know, maybe CUT, because it has not failed down.

how do you think to make different CUT and ALL node search ?

In the end, I decided to do some simple counting (% of fail low) to decide. And it was All instead of Cut. With that my % of predicted All nodes that fail low is a bit better (as expected).

In theory, it also makes sense: when you failed high on the zero window reduced search, you will most often also fail high on the zero window full depth re-search (ie. child node fails low and is an All node).

As for how to treat Cut and All differently. Well I have plenty of ideas, most of which will be proven wrong in testing. But who knows? Maybe one of them will work!

First patch I'm testing is simply to change the min depth condition between All and Cut nodes, for IID. Before I was using depth >= 7 condition for all non PV nodes, and now

Code: Select all

depth >= (node_type == Cut ? 6 : 8)

I really don't know if it works yet. Test is running. Fingers crossed, and we'll see!

As for not doing IID at All nodes, as suggested by Richard, I think that's too extreme. Or perhaps my move ordering is nowhere near as good as Critter's, but my %age of All nodes that fail low is quite low (though significantly higher than the %age of Cut nodes that fail low, so in this sense the predictor is not completely useless).

PS: I really hate these names All and Cut. I think I'll rewrite the code
- rename variable "node_type" to "expectation"
- values will be PV, FailLow (All), FailHigh (Cut)
This is much more self-documenting, I think.

[Sven]

That really clarified the node type thing for me (my mistake was, as pointed out by marco above, that child of cut would still be cut).

Gentlemen,

the successor of a Cut-Node is an All-Node.

Sven

[Desperado]

That really clarified the node type thing for me (my mistake was, as pointed out by marco above, that child of cut would still be cut).

Gentlemen,

the successor of a Cut-Node is an All-Node.

Sven

Hello Sven,

What is the point please ?

I guess that is already clarified. But what may be discussed further is
how to handle "expectations". When you do a move inside the search
you can pass the expected node type or simply call the corresponding search function.

Of course you can handle it trivial, just switching between ALL and CUT
nodes (based on the perfect, or at least well ordered tree assumption).
That would be at least consistent.
( And that is the way i handle currently the type of a node).

But if you are inside an ALL node, that indicates you will not get a beta cut
and on the other side there are candidate moves that will produce a cut anyway, or at least we "expect" them to get a cut...

Now, dont you see a conflict inside an ALL node where we "do not expect" a cut ( by definition )
but on the other hand we only do a NullMove because we "do expect" a cut ?

Code: Select all

1.
Well, what do you pass as expected node type or which
corresponding search function will be called ?

Code: Select all

2.
What expectation has priority and why ?
That a child of an ALL-Node is an expected CUT-Node or that the child of
a NullMove is an expected ALL-Node ?!

Code: Select all

3.

a.
    Does the Wiki really give answers to handle expectation's priority if
    they are overlapping ones ?
b.
     examples:
    
    would you call an ALL-Node from a Cut-Node when the SEE value
    of a queen move is -800 and the static value is around alpha ?

    would you call a CUT-Node from an ALL-Node if the move is
    a winning capture and the static evaluation is already above alpha ?

    would you ignore such information and argue like: 
    expected child of a CUT is an ALL and expected 
    child of an ALL is a CUT node ?

Imho, it is a qualified question that is not that easy to answer.
There is enough room to discuss "expectation" and how to handle
it.

Best

Michael

[Sven]

That really clarified the node type thing for me (my mistake was, as pointed out by marco above, that child of cut would still be cut).

Gentlemen,

the successor of a Cut-Node is an All-Node.

Sven

Hello Sven,

What is the point please ?

I guess that is already clarified.

Hi Michael,

it did not appear to be clarified for me, if you read again what both Marco and Lucas had written. Maybe I misunderstood that part of Lucas' post.

But what may be discussed further is
how to handle "expectations". When you do a move inside the search
you can pass the expected node type or simply call the corresponding search function.

I think it is a minor implementation detail whether the expected node type is already defined with the recursive call of the search function (i.e., within the context of the parent node) or after entering the child node. Usually I think you will be doing a mixture of both, the function call setting the "initial value" for the expected node type of the child and the body of the (same) function possibly correcting the expectation based on certain conditions.

It is clear that there are enough cases where the prediction fails, and whenever this is detected, the prediction should be adapted to the new information. I hope that answers your questions 3a) and 3b).

Now, dont you see a conflict inside an ALL node where we "do not expect" a cut ( by definition )
but on the other hand we only do a NullMove because we "do expect" a cut ?

At a first glance, yes, but that ceases when taking a closer look. If you forget about null move for a moment then a node which you predict as ALL node can be either confirmed as such or not, in the latter case switching to a CUT node. Confirming the "ALL" type means making all moves and no cut appears, refuting it means there is some cut. Now add null move into the calculation. At an ALL node you can either say: null move is probably wasted since it won't produce a cutoff, so I skip it, or you can say, with probability P my "ALL" prediction is wrong, and for that case I want to try null move to get a cheaper cutoff, if any.

If you do the latter then the null move subtree bases on the "prediction is wrong with probability P" case in my opinion, so it should start from the viewpoint of a CUT node instead of an ALL node, meaning that the child node after making the nullmove would in turn be predicted as ALL. If the null move fails low then unfortunately the null move was somehow wasted, and we have to continue assuming we are at an ALL node.

So I do not see any "overlapping priorities" for node type prediction.

Sven

[Don]

For example, does it work to have a different min depth and reduction for IID between 'All' and 'Cut' nodes

In 'All' nodes you can omit IID entirely since all moves are expected to fail low.

Only problem is, you really don't know a node is an ALL node until you search all the moves without improving alpha. You can assume that if you get a fail high at depth D, then depth D-1 is likely to be an ALL node, but in DTS I found this to be prone to significant error, because move ordering is anything but perfect.

Komodo uses a simple definition which seems to work extremely well. We count the number of nodes since the last PV node and go by the odd/even parity.

So the when you are in the PV nodes and do a zero window PVS search, that is a cut node and it usually will cut off. The node after it is always an ALL node and every other node swaps back and forth.

This definition is always "correct" until a cut node does not fail or an all node does fail. When that happens, the search will unwind to some point and correct itself.

For example if an all node fails high, the parent node which is a cut node will simply have to try more moves. One of them will either produce the cut node that it should, or else none of them will. In that case the parent did not produce a cutoff and it's parent now gets involved - which is an all node. Eventually it will reset itself perfectly, or else it actually back up all the way back to a PV node and get researched as a PV node.

But here is the beauty of that. If it gets back to PV node some of the same moves may get searched, but they will switch roles! The very same node that was considered a CUT becomes an ALL node and vice versa.

We only partially understand the repercussion of that but it seems to be a very nice quality for the search to have, especially if you want to treat the nodes differently. It essentially allows you to cheat move on some nodes by speculatively throwing t hem out or reducing them. If a research is triggered you are saved, if not you saved time.

[Desperado]

@Sven

Well, it is already late for me today, but just a short feedback and
maybe tomorrow a more detailed answer.

...
It is clear that there are enough cases where the prediction fails, and whenever this is detected, the prediction should be adapted to the new information. I hope that answers your questions 3a) and 3b).
...

Using information to decide how to search is different somehow to
handle an already entered node and confirming it.

If you would like to forget a moment of some naming conventions like
CUT and ALL nodes and think of different node types like TypeA,TypeB,
TypeC ...

Code: Select all

int TypeX()
{
    ...
    while( moves )
    {  
             if( condition  )   value = -TypeA();
      else if( condition1)    value = -TypeB();
      else if( condition2)    value = -WHATEVER();
    }
}

...the difference is that the condition doesnt necessarily depends
on the fact that we are at a node of TypeX.

Using the CUT,ALL node types i dont see a reason why a predicted CUT-node
cannot be a child of an already entered CUT-Node, _if_ a condition is met,
that a move will be refuted. The weakest prediction information maybe
the node type we are inside, but that seems to be the default condition used today.

Last but not least a point i have in mind

Code: Select all

// in this case the intention is to show
// that the prediction of a node will lead
// to completly different search behaviour
// eg.: we decide to search cut nodes with lmr
// and all nodes without lmr or something similiar

while( moves )
{
   if( condition ) value = -searchWithLMR();
   else              value = -searchWithoutLMR();
}

In that case the prediction of a child is essentially different
from confirming the child node. Isnt it ?

Maybe i am too tired for today

Good night everybody.

[Houdini]

More importantly, I am not convinced that it is reasonable to differentiate between PV and non-PV nodes, except for a few issues dealing with efficiency. For example, no reason to do a null-move search at a PV node since a null-move is illegal and can't be the best move. But I really don't see any justification for reducing non-PV moves more than PV moves, because the entire reason for searching those non-PV moves is to give them a chance to become real best moves...

I definitely agree with that. PV and non PV nodes should be treated equally, wherever possible, unless there is a good reason not to (null move, but also eval pruning and razoring).

There is a real advantage in doing different reductions and extensions at PV-nodes than at non-PV nodes. It's an integral part of the search strategy.

Depending on the details of the implementation, there can also be advantages in having a slightly different approach to pruning, extending, IID, LMR or SMP-related stuff for ALL and CUT nodes.

Houdini would be significantly weaker without these refinements.

Robert

[lucasart]

Yes, indeed. This code should hopefully be correct:

Actually, the code I posted is still not correct in all cases. The only thing that I'm missing, is that a Cut node becomes an All node, once all the "candidate moves" have been searched, and failed to give a beta cutoff. That's more like it (note that I have a single search function for all node types):

Code: Select all

if (node_type == PV && first)
	// search full window
	score = -search(B, -beta, -alpha, new_depth, PV, ss+1);
else
{
+	// Candidate moves have been searched, and failed to produce a cutoff. Cut node
+	// becomes All node, as it is less likely that later moves will produce a cutoff
+	if (node_type == Cut && ss->reduction)
+		node_type = All;
		
	// zero window search (reduced)
	score = -search(B, -alpha-1, -alpha, new_depth - ss->reduction,
		node_type == PV ? Cut : -node_type, ss+1);

	// doesn't fail low: verify at full depth, with zero window
	if (score > alpha && ss->reduction)
		score = -search(B, -alpha-1, -alpha, new_depth, All, ss+1);

	// still doesn't fail low at PV node: full depth and full window
	if (node_type == PV && score > alpha)
		score = -search(B, -beta, -alpha, new_depth , PV, ss+1);
}

For simplicity of implementation, I did like Fruit, and All = -1 Cut = +1+. That way, I can use -node_type to switch from All to Cut and vice versa (PV=0 is its own opposite). It may seem a bit hacky (as it wouldn't work if I changed the values of the constants integers All, Cut, PV), but I like it that way