TT with Null Move Cuts A PV Node/Line

[Cheney]

Hi,

I am hitting problem with my PV line being cut short (when displayed and recorded). I see this is not a new topic and have researched a fair amount. Sorry for an redundancy with this subject but I am stuck on how to resolve.

My search uses PVS, retains history for ordering, has an always overwrite TT, and I added null move pruning. I thought I saw this issue, rarely, before null move pruning was added, but it is noticeable now and seems as if the combination of a TT and null move pruning make some PV lines short.

After debugging, it appears there are PV nodes being discovered, written to the TT (this is expected), and then overwritten later by a cut move in the TT (well, this is expected but not understood ). As the search continues, it gets a TT hit which happens to actually make a cut in the line.

I have tried saving/extracting the PV via the following methods to compare them all and see what's going on:
* main TT bucket
* a PV TT bucket that holds PV moves
* a triangular array
* a linked PV list.

All see a similar cut at various points. There are PLYs where one is not altered or all are altered the same.

If I disable the probe TT, the Triangular array and PV list seem to be just fine while extracting the PV from the PVTT is not.

I read about "do not cut at PV nodes". When score > alpha, I set "isPvNode=true". Where I check for a cut (if score >=beta) I have modified to if(score >=beta && !isPvNode) but no dice. I even applied various "if(something) writeTT()" to not write the TT with the cutting move/score. I have also tried preventing overwrites in the TT of an exact entry with a lower bound entry.

I have somewhat tried not setting the TT with a move within the null move search tree that cuts.

I just cannot seem to prevent this from happening.

Any advice is greatly appreciated

Thanks!

[Edsel Apostol]

You can try the following:

-don't do null move in the PV nodes
-don't do cutoff from the hash table in the PV nodes, just use the hash move
-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already

[Cheney]

-don't do null move in the PV nodes

I think I can try this. In my PVS function:
1. I check for TT hit and return score if there is a hit.
2. Check if is horizon and call qsearch
3. attempt null move pruning
4. Generate sorted moves
5. Play a move and call PVS.
6. Perform alpha/beta checks, history/TT updating.

I will try to set a flag "is parent a PV node" or something like that to avoid null moves if the child moves are that of a PV.

-don't do cutoff from the hash table in the PV nodes, just use the hash move

I may not be following this statement. I do not cut based on what is in the TT. My ProbeTT function validates the hash and that the stored depth is deeper than the current search depth. If the stored entry is deeper then it returns the score if an exact entry. If it is a lower or upper bounds, I have tried both returning the stored score and beta or alpha respectively (fail hard or soft).

It is these returned scores that cause the cutoff.

When I generate moves and order them for a given position, if the position has a stored move in the TT, it is ordered high in the move list. I do not just "cut" right there. Is this what you are thinking I am doing?

-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already

I believe I am doing this. I have a separate TT just for exact nodes where I extract the PV between iterations. However, somewhere deep in the search, a new PV is found but a few plys shallower, a TT entry is probed with a score that causes that whole PV to cut. This leads to me losing the chaining or connection of stored PV moves in the PV TT.

[bob]

Hi,

I am hitting problem with my PV line being cut short (when displayed and recorded). I see this is not a new topic and have researched a fair amount. Sorry for an redundancy with this subject but I am stuck on how to resolve.

My search uses PVS, retains history for ordering, has an always overwrite TT, and I added null move pruning. I thought I saw this issue, rarely, before null move pruning was added, but it is noticeable now and seems as if the combination of a TT and null move pruning make some PV lines short.

After debugging, it appears there are PV nodes being discovered, written to the TT (this is expected), and then overwritten later by a cut move in the TT (well, this is expected but not understood ). As the search continues, it gets a TT hit which happens to actually make a cut in the line.

I have tried saving/extracting the PV via the following methods to compare them all and see what's going on:
* main TT bucket
* a PV TT bucket that holds PV moves
* a triangular array
* a linked PV list.

All see a similar cut at various points. There are PLYs where one is not altered or all are altered the same.

If I disable the probe TT, the Triangular array and PV list seem to be just fine while extracting the PV from the PVTT is not.

I read about "do not cut at PV nodes". When score > alpha, I set "isPvNode=true". Where I check for a cut (if score >=beta) I have modified to if(score >=beta && !isPvNode) but no dice. I even applied various "if(something) writeTT()" to not write the TT with the cutting move/score. I have also tried preventing overwrites in the TT of an exact entry with a lower bound entry.

I have somewhat tried not setting the TT with a move within the null move search tree that cuts.

I just cannot seem to prevent this from happening.

Any advice is greatly appreciated

Thanks!

Can't be avoided without a LOT of overhead. Simple solution, don't do the PV like that. Back it up as most of us do. No measurable overhead, and that way you get the exact PV that takes you to the endpoint that produced the reported best score, which is nice for debugging.

[bob]

You can try the following:

-don't do null move in the PV nodes
-don't do cutoff from the hash table in the PV nodes, just use the hash move
-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already

Seemed to me he was describing a problem trying to construct the PV from the hash table. The above don't help that at all. Perhaps I misunderstood his question?

[Cheney]

... Back it up as most of us do...

I'm sorry, I am not sure I follow. Do you mean by saving it in an array, like a triangular array or linked/chained list? These I have tried and show the same issue. I am not aware of another way to back up the PV.

Thanks!

[Edsel Apostol]

-don't do null move in the PV nodes

I think I can try this. In my PVS function:
1. I check for TT hit and return score if there is a hit.
2. Check if is horizon and call qsearch
3. attempt null move pruning
4. Generate sorted moves
5. Play a move and call PVS.
6. Perform alpha/beta checks, history/TT updating.

I will try to set a flag "is parent a PV node" or something like that to avoid null moves if the child moves are that of a PV.

-don't do cutoff from the hash table in the PV nodes, just use the hash move

I may not be following this statement. I do not cut based on what is in the TT. My ProbeTT function validates the hash and that the stored depth is deeper than the current search depth. If the stored entry is deeper then it returns the score if an exact entry. If it is a lower or upper bounds, I have tried both returning the stored score and beta or alpha respectively (fail hard or soft).

It is these returned scores that cause the cutoff.

When I generate moves and order them for a given position, if the position has a stored move in the TT, it is ordered high in the move list. I do not just "cut" right there. Is this what you are thinking I am doing?

-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already

I believe I am doing this. I have a separate TT just for exact nodes where I extract the PV between iterations. However, somewhere deep in the search, a new PV is found but a few plys shallower, a TT entry is probed with a score that causes that whole PV to cut. This leads to me losing the chaining or connection of stored PV moves in the PV TT.

In your PVS function, don't do this:

1. I check for TT hit and return score if there is a hit.
3. attempt null move pruning

when (beta-alpha > 1). There's no need to set a flag that the parent node is a PV. It is already assumed that non-PV nodes are searched with zero window (beta-alpha == 1).

It is these returned scores that cause the cutoff.

What I mean with "don't cutoff from the hash table" is you shouldn't do the cutoff as you've described above when in PV nodes (beta-alpha>1). Just use the hash move in move ordering. Maybe a pseudocode would explain it much better.

Code: Select all

int PVS(int alpha, int beta, int depth) {
    bool inPvNode = (beta-alpha>1) ? true : false;
    
    if (!inPvNode) {
        "check for TT hit and return score if there is a hit"
    }
    "use the hash move from the TT for move ordering"

    if (!inPvNode) {
        "attempt null move pruning '
    }

    ....
}

Code: Select all

for &#40;int depth = 1; depth <= MAXPLY; ++depth&#41; &#123;
    do &#123;
        "assign alpha and beta here based on previous score"
        score = PVS&#40;alpha, beta, depth&#41;;
    while &#40;score <= alpha || score >= beta&#41;;

    "use a triangular array, a PV TT bucket for more accurate principal variation collection, don't use the main TT as there is a big chance that exact node entries are overwritten"
    "populate the main TT with the principal variation collected from the just finished search iteration, this way overwritten hash table entries that has the exact nodes will be restored, and the next iteration will search that line first."
&#125;

[Edsel Apostol]

You can try the following:

-don't do null move in the PV nodes
-don't do cutoff from the hash table in the PV nodes, just use the hash move
-store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already

Seemed to me he was describing a problem trying to construct the PV from the hash table. The above don't help that at all. Perhaps I misunderstood his question?

I think his problem is incomplete PV. He tried various ways to collect the PV (one of them is using the exact nodes from the main TT, others are triangular array, etc) but still fails to display the PV at it's full length from time to time. I'm suggesting ways on how it can be solved. That's what we've been doing in our engine and we don't have that truncated PV issue.

[Cheney]

Thanks for taking the time to help with this
I see what you are writing with the code:

Code: Select all

bool inPvNode = (beta-alpha>1) ? true : false; 

But maybe my vocabulary and mathematical understanding are off in regards to PVS?

In your PVS function, don't do this:

1. I check for TT hit and return score if there is a hit.
3. attempt null move pruning

when (beta-alpha > 1). There's no need to set a flag that the parent node is a PV. It is already assumed that non-PV nodes are searched with zero window (beta-alpha == 1).

When I start a search, alpha and beta are -infinity and +infinity. When alpha is raised at a particular node I then make the next move (at that same node) and call the same search but set alpha to -alpha-1 and beta to -alpha (see my pseudocode - I use isPVNode to help flag that within the node). This means in all child nodes that beta-alpha == 1.

Code: Select all

int PVS(ChessBoard &b, int depth, int ply, int alpha, int beta, int extension, search::searchstate &ss)
{
  int score =0;
  bool isPVNode=false;
  // (1) Check for TT hit here and either return score or play on. (2) Play and return QSearch if horizon. (3) Attempt NullMove here. (4) Generate moves
  // Loop all moves here
  {
      mv=GetNextMove();
      b.MakeMove(*mv);
      if(!isPVNode)  // Call normal window search
            score=-PVS(b, depth-1, ply+1, -beta, -alpha, extension, ss);
      else
      {
            // Call PVS search since this node had alpha raised
            score = -PVS(b, depth-1, ply+1, -alpha-1, -alpha, extension, ss);
            if&#40;&#40;score > alpha&#41; && &#40;score < beta&#41;)
                  // Need to research with full window
                  score=-PVS&#40;b, depth-1, ply+1, -beta, -alpha, extension, ss&#41;;
      &#125;
      b.UnmakeMove&#40;);

      // Alpha/Beta analysis
      if&#40;score>alpha&#41;
      &#123;	
            if&#40;score>=beta&#41;
            &#123;
                  // Set TT as lower bound, record history
                  return beta;
            &#125;
            // record best move for TT writing later
            alpha=score;
            isPVNode=true;
      &#125;
      // Set TT as exact or upper bound based on this node
&#125;

[Edsel Apostol]

Thanks for taking the time to help with this
I see what you are writing with the code:

Code: Select all

bool inPvNode = (beta-alpha>1) ? true : false; 

But maybe my vocabulary and mathematical understanding are off in regards to PVS?

In your PVS function, don't do this:

1. I check for TT hit and return score if there is a hit.
3. attempt null move pruning

when (beta-alpha > 1). There's no need to set a flag that the parent node is a PV. It is already assumed that non-PV nodes are searched with zero window (beta-alpha == 1).

When I start a search, alpha and beta are -infinity and +infinity. When alpha is raised at a particular node I then make the next move (at that same node) and call the same search but set alpha to -alpha-1 and beta to -alpha (see my pseudocode - I use isPVNode to help flag that within the node). This means in all child nodes that beta-alpha == 1.

Code: Select all

int PVS(ChessBoard &b, int depth, int ply, int alpha, int beta, int extension, search::searchstate &ss)
{
  int score =0;
  bool isPVNode=false;
  // (1) Check for TT hit here and either return score or play on. (2) Play and return QSearch if horizon. (3) Attempt NullMove here. (4) Generate moves
  // Loop all moves here
  {
      mv=GetNextMove();
      b.MakeMove(*mv);
      if(!isPVNode)  // Call normal window search
            score=-PVS(b, depth-1, ply+1, -beta, -alpha, extension, ss);
      else
      {
            // Call PVS search since this node had alpha raised
            score = -PVS(b, depth-1, ply+1, -alpha-1, -alpha, extension, ss);
            if&#40;&#40;score > alpha&#41; && &#40;score < beta&#41;)
                  // Need to research with full window
                  score=-PVS&#40;b, depth-1, ply+1, -beta, -alpha, extension, ss&#41;;
      &#125;
      b.UnmakeMove&#40;);

      // Alpha/Beta analysis
      if&#40;score>alpha&#41;
      &#123;	
            if&#40;score>=beta&#41;
            &#123;
                  // Set TT as lower bound, record history
                  return beta;
            &#125;
            // record best move for TT writing later
            alpha=score;
            isPVNode=true;
      &#125;
      // Set TT as exact or upper bound based on this node
&#125;

You're probably confused about the "bSearchPv" here in the PVS algorithm which is just a flag:

Code: Select all

int pvSearch( int alpha, int beta, int depth ) {
   if( depth == 0 ) return quiesce( alpha, beta );
   bool bSearchPv = true;
   for ( all moves)  {
      make
      if ( bSearchPv ) {
         score = -pvSearch(-beta, -alpha, depth - 1);
      } else {
         score = -pvSearch(-alpha-1, -alpha, depth - 1);
         if ( score > alpha ) // in fail-soft ... && score < beta ) is common
            score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search
      &#125;
      unmake
      if&#40; score >= beta )
         return beta;   // fail-hard beta-cutoff
      if&#40; score > alpha ) &#123;
         alpha = score; // alpha acts like max in MiniMax
         bSearchPv = false;  // *1&#41;
      &#125;
   &#125;
   return alpha; // fail-hard
&#125;

taken from http://chessprogramming.wikispaces.com/ ... ion+Search

with this Node type classification:

PV-Nodes
PV-nodes (Knuth's Type 1) are nodes that have a score that ends up being inside the window. So if the bounds passed are [a,b], with the score returned s, a<s<b. These nodes have all moves searched, and the value returned is exact (i.e., not a bound), which propagates up to the root along with a principal variation.
Root Node and the Leftmost Nodes are always PV-nodes
In Principal Variation Search, PV-nodes are defined by beta-alpha>1
All Siblings of a PV-node are expected Cut-nodes

taken from http://chessprogramming.wikispaces.com/Node+Types


To avoid confusion, I'll rephrase my previous suggestions. On the top of the search, when (beta-alpha>1) don't "Check for TT hit here and return score", just use the hash move for move ordering instead, and don't attempt null move pruning.