All and Cut nodes

[lucasart]

Currently, I only use PV and nonPV nodes, and do not distinguish the 'All' and 'Cut' ones from my non PV nodes. But I'm wondering if this distinction can be useful.

From your experience, what kind of things are worth experimenting with distinguishing all and cut nodes. For example, does it work to have a different min depth and reduction for IID between 'All' and 'Cut' nodes, and same question for Null move.

[rvida]

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.

[bob]

Currently, I only use PV and nonPV nodes, and do not distinguish the 'All' and 'Cut' ones from my non PV nodes. But I'm wondering if this distinction can be useful.

From your experience, what kind of things are worth experimenting with distinguishing all and cut nodes. For example, does it work to have a different min depth and reduction for IID between 'All' and 'Cut' nodes, and same question for Null move.

Personally, I don't see any reason to differentiate. If ply X is a CUT node, by definition, ply X-1 and X+1 are ALL nodes, unless move ordering is broken.

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

[bob]

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.

[lucasart]

Currently, I only use PV and nonPV nodes, and do not distinguish the 'All' and 'Cut' ones from my non PV nodes. But I'm wondering if this distinction can be useful.

From your experience, what kind of things are worth experimenting with distinguishing all and cut nodes. For example, does it work to have a different min depth and reduction for IID between 'All' and 'Cut' nodes, and same question for Null move.

Personally, I don't see any reason to differentiate. If ply X is a CUT node, by definition, ply X-1 and X+1 are ALL nodes, unless move ordering is broken.

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).
I started by putting !PV conditions before many search features, because Stockfish was doing it, so I thought: If they do it, and SF is so strong, it must be the right thing to do. But after some testing, I started to remove them one by one: testing confirming every time that it was either useless of even harmful.

But differentiating All and Cut nodes seems very weird. For example, the assumption is that an All node will fail low, so why bother with move ordering and IID. But what if it doesn't ? This could be a serious source of search inconsistencies, no ? We never know in advance whether a node is going to fail low or not: if we did, why would we bother searching it ?

Anyway, sometimes theoretically unsound things are practically useful. So the only way to find out is to test. But I'm still very skeptical about this All/Cut node type 'hype'...

[michiguel]

Currently, I only use PV and nonPV nodes, and do not distinguish the 'All' and 'Cut' ones from my non PV nodes. But I'm wondering if this distinction can be useful.

From your experience, what kind of things are worth experimenting with distinguishing all and cut nodes. For example, does it work to have a different min depth and reduction for IID between 'All' and 'Cut' nodes, and same question for Null move.

Personally, I don't see any reason to differentiate. If ply X is a CUT node, by definition, ply X-1 and X+1 are ALL nodes, unless move ordering is broken.

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).
I started by putting !PV conditions before many search features, because Stockfish was doing it, so I thought: If they do it, and SF is so strong, it must be the right thing to do. But after some testing, I started to remove them one by one: testing confirming every time that it was either useless of even harmful.

But differentiating All and Cut nodes seems very weird. For example, the assumption is that an All node will fail low, so why bother with move ordering and IID. But what if it doesn't ? This could be a serious source of search inconsistencies, no ? We never know in advance whether a node is going to fail low or not: if we did, why would we bother searching it ?

Anyway, sometimes theoretically unsound things are practically useful. So the only way to find out is to test. But I'm still very skeptical about this All/Cut node type 'hype'...

The problem is how accurate you prediction of ALL or CUT nodes is. So, the issue is probabilistic. I think there is room for treating them differently. For instance, the way you divide the parallel search could be one (but I have no tried it yet). So, if the prediction is wrong, nothing serioulsy wrong happened but you may need not search more nodes, which is compensated by what you save if the prediction is right.

I do not believe that the prediction of an ALL or CUT node should be use to do or not do something, but it could alter some parameters about how it is done. In other words, you gamble differently.

Miguel

[lucasart]

I just want to be sure I'm doing this right. Here's the recursive search() call in me search() function (only one search function for all nodes, root, PV, non PV). The true/false penultimate parameter is the node type (PV=true, nonPV=false) of the child node:

Code: Select all

if (is_pv && first)
	// search full window
	score = -search(B, -beta, -alpha, new_depth, true, ss+1);
else
{
	// zero window search (reduced)
	score = -search(B, -alpha-1, -alpha, new_depth - ss->reduction, false, 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, false, 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 , true, ss+1);
}

Now if I want to introduce PV, All, Cut instead of PV/nonPV, code would be:

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);
}

Is that correct ?

[elcabesa]

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

[Desperado]

Hello Lucas,

i think it is pretty hard to answer your question.

1.
===

The following way to handle pv,cut,all nodes may look like this.
This is based on the idea of a perfect ordered tree where the
expectation of a node type fits the real node type.

Code: Select all

int PV()
{
    // Loop Move List
    while( moves )
    {
         if( firstMove )
         {
          value = -PV();
         }
         else
         {
          value = -CUT();
          
          //research if alpha improved
          if( value > alpha ) // && value beta
              value = -PV()
         }
    }
}

int CUT()
{
    // Loop Move List
    while( moves )
    {
         value = -ALL();
    }
}

int ALL()
{
    // Loop Move List
    while( moves )
    {
         value = -CUT();
    }
}

Now i have a problem too, with the keyword in this place, which is "expectation".
For example.

Code: Select all

int ALL()
{
    if( doNullMove()  )
    {
         value = -???()
    }

    ...
}

From theoretical point of view we expect a cut node as successor. But on the
other hand we do a nullMove because we expect it to fail high, so a call to ALL()
would make sense too somehow.
In such a case I decided for me to go the theoretical way an to call a CUT() node.

2.
===

The most significant difference i was able to detect is the sensitivity to LMR
All nodes are much more sensitive to your LMR/LMP formulars.
So it makes absolutely sense to me to handle these formulars differently.

Code: Select all

int ALL()
{
    // Loop Move List
    while( moves )
    {
         // Lmr
         // somehow logical that lmr does have another impact
         // within all nodes.So to split the formulars for cut,all
         // nodes can make absolutely sense.
    }
}

Just my 2 cents on sunday morning

Michael

[lucasart]

Hello Lucas,

i think it is pretty hard to answer your question.

1.
===

The following way to handle pv,cut,all nodes may look like this.
This is based on the idea of a perfect ordered tree where the
expectation of a node type fits the real node type.

Code: Select all

int PV()
{
    // Loop Move List
    while( moves )
    {
         if( firstMove )
         {
          value = -PV();
         }
         else
         {
          value = -CUT();
          
          //research if alpha improved
          if( value > alpha ) // && value beta
              value = -PV()
         }
    }
}

int CUT()
{
    // Loop Move List
    while( moves )
    {
         value = -ALL();
    }
}

int ALL()
{
    // Loop Move List
    while( moves )
    {
         value = -CUT();
    }
}

Now i have a problem too, with the keyword in this place, which is "expectation".
For example.

Code: Select all

int ALL()
{
    if( doNullMove()  )
    {
         value = -???()
    }

    ...
}

From theoretical point of view we expect a cut node as successor. But on the
other hand we do a nullMove because we expect it to fail high, so a call to ALL()
would make sense too somehow.
In such a case I decided for me to go the theoretical way an to call a CUT() node.

2.
===

The most significant difference i was able to detect is the sensitivity to LMR
All nodes are much more sensitive to your LMR/LMP formulars.
So it makes absolutely sense to me to handle these formulars differently.

Code: Select all

int ALL()
{
    // Loop Move List
    while( moves )
    {
         // Lmr
         // somehow logical that lmr does have another impact
         // within all nodes.So to split the formulars for cut,all
         // nodes can make absolutely sense.
    }
}

Just my 2 cents on sunday morning

Michael

Thank you. 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).

But yes, null move is another recursive search() call, where you need to predict the node type. I just did a quick measure, and noticed that my null move fails low only 19% of the time (so I do null move pruning 81% of the time). So the child node of null move search should be predicted as an All node.

This 81% of null move pruning seems quite high. Does anyone have similar numbers with their engine ?