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!
TT with Null Move Cuts A PV Node/Line
Moderators: hgm, Rebel, chrisw
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: TT with Null Move Cuts A PV Node/Line
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
-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
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: TT with Null Move Cuts A PV Node/Line
I think I can try this. In my PVS function:Edsel Apostol wrote: -don't do null move in the PV nodes
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.
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).Edsel Apostol wrote: -don't do cutoff from the hash table in the PV nodes, just use the hash move
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?
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.Edsel Apostol wrote: -store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: TT with Null Move Cuts A PV Node/Line
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.Cheney wrote: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!
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: TT with Null Move Cuts A PV Node/Line
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?Edsel Apostol wrote: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
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: TT with Null Move Cuts A PV Node/Line
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.bob wrote: ... Back it up as most of us do...
Thanks!
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: TT with Null Move Cuts A PV Node/Line
In your PVS function, don't do this:Cheney wrote:I think I can try this. In my PVS function:Edsel Apostol wrote: -don't do null move in the PV nodes
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.
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).Edsel Apostol wrote: -don't do cutoff from the hash table in the PV nodes, just use the hash move
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?
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.Edsel Apostol wrote: -store the principal variation to the hash table after every iteration in case the PV positions stored in it has been overwritten already
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 (int depth = 1; depth <= MAXPLY; ++depth) {
do {
"assign alpha and beta here based on previous score"
score = PVS(alpha, beta, depth);
while (score <= alpha || score >= beta);
"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."
}
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: TT with Null Move Cuts A PV Node/Line
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.bob wrote: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?Edsel Apostol wrote: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
-
- Posts: 104
- Joined: Thu Sep 27, 2012 2:24 am
Re: TT with Null Move Cuts A PV Node/Line
Thanks for taking the time to help with this
I see what you are writing with the code:
But maybe my vocabulary and mathematical understanding are off in regards to PVS?
I see what you are writing with the code:
Code: Select all
bool inPvNode = (beta-alpha>1) ? true : false;
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.Edsel Apostol wrote: 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).
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((score > alpha) && (score < beta))
// Need to research with full window
score=-PVS(b, depth-1, ply+1, -beta, -alpha, extension, ss);
}
b.UnmakeMove();
// Alpha/Beta analysis
if(score>alpha)
{
if(score>=beta)
{
// Set TT as lower bound, record history
return beta;
}
// record best move for TT writing later
alpha=score;
isPVNode=true;
}
// Set TT as exact or upper bound based on this node
}
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: TT with Null Move Cuts A PV Node/Line
You're probably confused about the "bSearchPv" here in the PVS algorithm which is just a flag:Cheney wrote:Thanks for taking the time to help with this
I see what you are writing with the code:But maybe my vocabulary and mathematical understanding are off in regards to PVS?Code: Select all
bool inPvNode = (beta-alpha>1) ? true : false;
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.Edsel Apostol wrote: 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).
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((score > alpha) && (score < beta)) // Need to research with full window score=-PVS(b, depth-1, ply+1, -beta, -alpha, extension, ss); } b.UnmakeMove(); // Alpha/Beta analysis if(score>alpha) { if(score>=beta) { // Set TT as lower bound, record history return beta; } // record best move for TT writing later alpha=score; isPVNode=true; } // Set TT as exact or upper bound based on this node }
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(-beta, -alpha, depth - 1); // re-search
}
unmake
if( score >= beta )
return beta; // fail-hard beta-cutoff
if( score > alpha ) {
alpha = score; // alpha acts like max in MiniMax
bSearchPv = false; // *1)
}
}
return alpha; // fail-hard
}
with this Node type classification:
taken from http://chessprogramming.wikispaces.com/Node+TypesPV-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
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.