TT with Null Move Cuts A PV Node/Line

[Cheney]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

[bob]

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

I solved this in crafty years ago.

When you store an EXACT hash entry, store the complete PV from the node you are at to the endpoint in ANOTHER smaller hash table. When you get an EXACT match, append that stored PV for that position on the current PV. Problem cured. I looked at four long test games I played last night, and I had exactly two PVs displayed that were short, terminated by <HT>.

[Sven]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

Hi Cheney,

I think you should either rename your flag into "foundPV", or invert its boolean value (i.e., initialize it to true and set it to false after one child raises alpha) and then rename it into something like "useFullWindowSearch".

I also see one difference of your PVS implementation to the "standard": you are using fail-hard but your re-search condition is "score > alpha && score < beta" which is common for a fail-soft implementation only. I can't tell whether it leads to severe problems in case of fail-hard but at least you might give it a try to omit the "&& score < beta" part.

Your observation that null-move pruning has some negative impact on your PVs might indicate a bug either in your null-move code or your PV-collecting code. Normally those parts of the search tree that are part of a subtree of a null-move should never have any impact on the root PV. If your case is different then something might go wrong. A null move will either refute the previous move of the opponent - then both that previous move as well as the null move that refuted him do not become part of the root PV -, or it won't refute that previous move, then the null move still does not make it into the root PV. Any information that you store in order to display a root PV later on should not be related to any null move.

Is it possible that you store information from a null move subtree in your "PVTT" by accident? That should not happen ...

Sven

[bob]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

Hi Cheney,

I think you should either rename your flag into "foundPV", or invert its boolean value (i.e., initialize it to true and set it to false after one child raises alpha) and then rename it into something like "useFullWindowSearch".

I also see one difference of your PVS implementation to the "standard": you are using fail-hard but your re-search condition is "score > alpha && score < beta" which is common for a fail-soft implementation only. I can't tell whether it leads to severe problems in case of fail-hard but at least you might give it a try to omit the "&& score < beta" part.

Your observation that null-move pruning has some negative impact on your PVs might indicate a bug either in your null-move code or your PV-collecting code. Normally those parts of the search tree that are part of a subtree of a null-move should never have any impact on the root PV. If your case is different then something might go wrong. A null move will either refute the previous move of the opponent - then both that previous move as well as the null move that refuted him do not become part of the root PV -, or it won't refute that previous move, then the null move still does not make it into the root PV. Any information that you store in order to display a root PV later on should not be related to any null move.

Is it possible that you store information from a null move subtree in your "PVTT" by accident? That should not happen ...

Sven

that >alpha < beta sounds like pure PVS.

Only way that can happen is if the original alpha/beta passed in is not a null-window. After establishing the score for the first move, you search the remainder with alpha, alpha+1 (but alpha+1 is less than the original beta) If you get a score back > alpha and less than beta, in fail hard it would be "alpha+1" and you need to re-search. If you enter search with a null-window, this can never happen.

[Edsel Apostol]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

You should probably read Fruit 2.1 on how it handles principal variation collection and how it implements null move and TT cutoff. One of it's design idiosyncrasies is to make sure that it displays the full principal variation.

[Sven]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

Hi Cheney,

I think you should either rename your flag into "foundPV", or invert its boolean value (i.e., initialize it to true and set it to false after one child raises alpha) and then rename it into something like "useFullWindowSearch".

I also see one difference of your PVS implementation to the "standard": you are using fail-hard but your re-search condition is "score > alpha && score < beta" which is common for a fail-soft implementation only. I can't tell whether it leads to severe problems in case of fail-hard but at least you might give it a try to omit the "&& score < beta" part.

Your observation that null-move pruning has some negative impact on your PVs might indicate a bug either in your null-move code or your PV-collecting code. Normally those parts of the search tree that are part of a subtree of a null-move should never have any impact on the root PV. If your case is different then something might go wrong. A null move will either refute the previous move of the opponent - then both that previous move as well as the null move that refuted him do not become part of the root PV -, or it won't refute that previous move, then the null move still does not make it into the root PV. Any information that you store in order to display a root PV later on should not be related to any null move.

Is it possible that you store information from a null move subtree in your "PVTT" by accident? That should not happen ...

Sven

that >alpha < beta sounds like pure PVS.

Only way that can happen is if the original alpha/beta passed in is not a null-window. After establishing the score for the first move, you search the remainder with alpha, alpha+1 (but alpha+1 is less than the original beta) If you get a score back > alpha and less than beta, in fail hard it would be "alpha+1" and you need to re-search. If you enter search with a null-window, this can never happen.

[I deleted my first attempt of this reply and restarted after finding that it was wrong.]

I think you are right. We can deduct that the "score < beta" is actually not redundant in fail hard (despite my first thoughts about it) but that it is in fact necessary to avoid some useless re-searches:

In fail hard, after establishing the score for the first move and searching with a zero window, "score > alpha" implies "score == alpha+1", just as you say. So there is one case in fail hard where the two conditions
A) if (score > alpha)
and
B) if (score > alpha && score < beta)
are not logically identical, and this is "alpha+1 >= beta", since in that case A is true but B is false so B would not perform the re-search. In fail hard "alpha+1 > beta" would be impossible IMO so "alpha+1 >= beta" would in fact mean "alpha+1 == beta", so the difference between A and B occurs exactly if the node has already been entered with a zero window, or if alpha has been raised to beta-1 in the meantime. In both cases a re-search would also not be required at all since in fail hard it would not return a different result (the "full window" is already the same as the zero window), so "missing the re-research" actually misses nothing.

This means that B correctly avoids some redundant re-searches in fail hard while A does not. When entering a node with a non-zero window, A and B are identical since "alpha+1 < beta" is always true. The code can be written slightly more efficiently by using a separate zwSearch() function for the zero-window search where no re-search is even attempted.

Do you agree?

I never stumbled upon this fine detail in my engines since I always used fail soft for ages.

Sven

[Cheney]

I currently store all positions into one array and any that are exact do go into a separate array for walking/extracting the PV line later.

When you store an EXACT hash entry, store the complete PV from the node you are at to the endpoint in ANOTHER smaller hash table.

By writing "endpoint", are you referring to the leaf which produced the value? Expecting the answer is yes, is this not similar to the Triangular Array?

Also, just a little status where I am at .

I have tried all kinds of things and reverted back. Somewhere in there my Triangular array does not seem to get truncated any more and I cannot reproduce its original failures. Walking the PV TT, however, still has consistent issues.

I performed some heavy TT debugging, it makes my head spin .

I looked a bit more at my MakeNullMove... I pulled the covers back and found bugs - unmaking it did not properly restore by board state. Then, I discovered my bitboards are getting corrupted somewhere while making moves at depths around 10.

Back to the drawing board for now.

Thanks to all who have offered help . I'll provide an update later if I get this all resolved.

[bob]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

Hi Cheney,

I think you should either rename your flag into "foundPV", or invert its boolean value (i.e., initialize it to true and set it to false after one child raises alpha) and then rename it into something like "useFullWindowSearch".

I also see one difference of your PVS implementation to the "standard": you are using fail-hard but your re-search condition is "score > alpha && score < beta" which is common for a fail-soft implementation only. I can't tell whether it leads to severe problems in case of fail-hard but at least you might give it a try to omit the "&& score < beta" part.

Your observation that null-move pruning has some negative impact on your PVs might indicate a bug either in your null-move code or your PV-collecting code. Normally those parts of the search tree that are part of a subtree of a null-move should never have any impact on the root PV. If your case is different then something might go wrong. A null move will either refute the previous move of the opponent - then both that previous move as well as the null move that refuted him do not become part of the root PV -, or it won't refute that previous move, then the null move still does not make it into the root PV. Any information that you store in order to display a root PV later on should not be related to any null move.

Is it possible that you store information from a null move subtree in your "PVTT" by accident? That should not happen ...

Sven

that >alpha < beta sounds like pure PVS.

Only way that can happen is if the original alpha/beta passed in is not a null-window. After establishing the score for the first move, you search the remainder with alpha, alpha+1 (but alpha+1 is less than the original beta) If you get a score back > alpha and less than beta, in fail hard it would be "alpha+1" and you need to re-search. If you enter search with a null-window, this can never happen.

[I deleted my first attempt of this reply and restarted after finding that it was wrong.]

I think you are right. We can deduct that the "score < beta" is actually not redundant in fail hard (despite my first thoughts about it) but that it is in fact necessary to avoid some useless re-searches:

In fail hard, after establishing the score for the first move and searching with a zero window, "score > alpha" implies "score == alpha+1", just as you say. So there is one case in fail hard where the two conditions
A) if (score > alpha)
and
B) if (score > alpha && score < beta)
are not logically identical, and this is "alpha+1 >= beta", since in that case A is true but B is false so B would not perform the re-search. In fail hard "alpha+1 > beta" would be impossible IMO so "alpha+1 >= beta" would in fact mean "alpha+1 == beta", so the difference between A and B occurs exactly if the node has already been entered with a zero window, or if alpha has been raised to beta-1 in the meantime. In both cases a re-search would also not be required at all since in fail hard it would not return a different result (the "full window" is already the same as the zero window), so "missing the re-research" actually misses nothing.

This means that B correctly avoids some redundant re-searches in fail hard while A does not. When entering a node with a non-zero window, A and B are identical since "alpha+1 < beta" is always true. The code can be written slightly more efficiently by using a separate zwSearch() function for the zero-window search where no re-search is even attempted.

Do you agree?

I never stumbled upon this fine detail in my engines since I always used fail soft for ages.

Sven

I am not sure I understand your question, so let me provide a better explanation of what I was writing.

In classic PVS, you initially do a v = Search(alpha,beta,etc.) at the root, where alpha and beta are not a null interval (beta > alpha+1).

Inside the search, most of the time, Search() is recursively called with a null window, alpha, alpha+1.

When you recurse with those values, you can never do the "if (value > alpha && value < beta) because beta = alpha+1 99+% of the time, and therefore if value > alpha, then it is at least == beta and for fail-soft it could be even higher.

But along the PV, where beta != alpha+1, you search the first move at such a node with the normal alpha/beta window, then you search the remainder of the moves at that ply with alpha, alpha+1. On occasion, here, you CAN get the value > alpha & value < beta, because the window you just failed high on was alpha, alpha+1, and you want to re-search with alpha,beta to see if it still fails high or if you get a real score back.

It definitely looks odd to see code like:

Code: Select all

          value = -Search(tree, -alpha-1, -alpha, ...)
          if (value > alpha && value < beta)
            value = -Search(-beta, -alpha, ...

That if is hardly ever true because as I mentioned, almost all recursive search calls specify a null-window, so if value > alpha, it is also at least == beta and the if will never be true.

I remember when Murray Campbell first showed me this in 1978 and I inserted the idea into my chess program because he had not tested it out as of then.  It looked really odd.  But after sitting down for a bit with it, suddenly the light came on.  This idea was not particularly new, as Belle used this same sort of algorithm in 1978 as well, although only at the root of the tree.

Hope that explains what I was trying to describe.  Now, if you have a question, fire away and maybe I can follow given the context above.  I don't see where it matters about fail-soft or fail-hard.  I have done both at various points in time inside Crafty and I didn't have to change that part of the basic PVS search at all as I remember...

[bob]

OK, thanks.

My bool isPVNode is misleading when compared to bSearchPv. However, both are serving the same purpose in my search and they start a null/zero window search when alpha is raised within a node.

I never understood that a PV-Node is defined by beta-alpha>1, a root node, and all leftmost nodes. However, later in the tree, on some central branch, if alpha is raised, am I correct at saying: (1) I have a new Principal Variation, (2) I am now playing a new set of PV-Nodes? I am interpreting a position/node where alpha is raised then that node becomes a PV-Node and this can happen anywhere in the tree.

I have tried various adjustments to the search following your recommendations, but no luck, the lines are still chopped short at certain depths. Further testing continues to show it is the null move pruning causing this. If I change the R value, the shorter lines are more frequent for both the PVTT and the Triangular Array. If I completely turn it off, no truncated PV Line walked from my PV TT.

I guess part of the problem, too, is I do not understand why one should not perform null move pruning within a PV-Node.

I'll continue to dig, and code, and code some more , and post back any findings. My hunch is that a nullmove performing a cut is breaking that chain when walking through the PVTT because later in the tree, where alpha was raised, it then becomes a cut node.

Thanks again.

You should probably read Fruit 2.1 on how it handles principal variation collection and how it implements null move and TT cutoff. One of it's design idiosyncrasies is to make sure that it displays the full principal variation.

Doesn't Fruit use the ugly hack of not allowing Exact matches or even cutoffs on PV nodes???

That's NOT the way to solve this problem.

[bob]

I currently store all positions into one array and any that are exact do go into a separate array for walking/extracting the PV line later.

When you store an EXACT hash entry, store the complete PV from the node you are at to the endpoint in ANOTHER smaller hash table.

By writing "endpoint", are you referring to the leaf which produced the value? Expecting the answer is yes, is this not similar to the Triangular Array?

Also, just a little status where I am at .

I have tried all kinds of things and reverted back. Somewhere in there my Triangular array does not seem to get truncated any more and I cannot reproduce its original failures. Walking the PV TT, however, still has consistent issues.

I performed some heavy TT debugging, it makes my head spin .

I looked a bit more at my MakeNullMove... I pulled the covers back and found bugs - unmaking it did not properly restore by board state. Then, I discovered my bitboards are getting corrupted somewhere while making moves at depths around 10.

Back to the drawing board for now.

Thanks to all who have offered help . I'll provide an update later if I get this all resolved.

No. What I am talking about is this.

Let's suppose you search a PV that goes like this (I will use letters to represent each new position produced by making a new move):

a-b-c-d-e-f-g-h-i-j-k-l-m-n-o-p-q-r-s-t-u-v-w-x-y-z. Position Z is a quiet quiescence node that we return a static evaluation from. As you back up, you will likely store EXACT hash entries at each of those positions above, correct?

What I am suggesting is this. When you get to any one of those nodes in the tree, say node P above, you will store an EXACT hash entry. In another hash table, you store the PV from position P to position Z where you did the evaluation. Now later, you search some other sequence of moves like

a1-b1-c1-d1-e1-f1-g1-h1-i1-j1-k1-l1-m1-n1-o1-P and there you reach the position from before. You find the EXACT hash entry, and you would normally cut the PV off at that point. But if you look in that second hash table where you stored that PV, you just graft q-r-s-t-u-v-w-x-y-z on to the end of your existing pv, which takes you directly to the endpoint that produced that score, and you get a full PV, not one that is cut off short. Very simple, very effective, and it works. Main point is "very simple". I can measure no cost for doing this because you RARELY back up a real score (EXACT) anyway, with PVS most are either UPPER or LOWER type entries and there is no PV for such positions anyway.

Let me know if you have any questions. You can look at Crafty's source, hash.c, the comments and code are pretty clear and very short.