PV based decisions

[mjlef]

Looking over recent source code from Fruit and its derivative, I find a number of choices which differ from what has been done in many older programs. I would be interested in what other programmers have found useful in these ideas:

a. Do not accept hash table scores if you are in the PV
b. Allow most extensions only if you are in the PV
c. Do not allow Null Pruning if in the PV
d. Allow other pruning (futility, history reduction) only if not in the PV

Which of these make a difference in your programs? Which improved playing strength? Which did not help or hurt?

Mark

[Tom Likens]

Looking over recent source code from Fruit and its derivative, I find a number of choices which differ from what has been done in many older programs. I would be interested in what other programmers have found useful in these ideas:

a. Do not accept hash table scores if you are in the PV
b. Allow most extensions only if you are in the PV
c. Do not allow Null Pruning if in the PV
d. Allow other pruning (futility, history reduction) only if not in the PV

Which of these make a difference in your programs? Which improved playing strength? Which did not help or hurt?

Mark

Mark,

I'm glad you're back. I have fond memories of the days when "Now" competed. To answer your question, I've been experimenting with these ideas--essentially, basing the search on a more solid theoretical footing using Knuth-node classification. My understanding is that Fabien made the above design decisions so that he wouldn't inadvertently truncate the PVs produced by Fruit. In addition these items laid the ground work for future modifications (which we may see in Fruit 3.0). To really make this work you also need to throw out the root aspiration window, as too narrow a window can also cause an incorrect truncation of your PV.

I've been experimenting with a, c and d above. The most important item for Djinn was item d. The elo increase for me was less than 50 elo, but there was a definite increase. I believe the ideas have promise, but like so many things, the actual benefit is program dependent. Interestingly, though when I eliminated the root aspiration window, I saw a decrease in playing strength. Which was a bit depressing since I really like the idea of having complete PVs.

One item that has increased Djinn's playing strength lately, is that I no longer allow null-move searches if the ply is less than or equal to 2, (where the root is 0, 1... etc.). I've experimented with 1, 2 and 3 and 2 is the best value for my engine. Of course, I never allowed null-move searches at the root

regards,
--tom

[mjlef]

Looking over recent source code from Fruit and its derivative, I find a number of choices which differ from what has been done in many older programs. I would be interested in what other programmers have found useful in these ideas:

a. Do not accept hash table scores if you are in the PV
b. Allow most extensions only if you are in the PV
c. Do not allow Null Pruning if in the PV
d. Allow other pruning (futility, history reduction) only if not in the PV

Which of these make a difference in your programs? Which improved playing strength? Which did not help or hurt?

Mark

Mark,

I'm glad you're back. I have fond memories of the days when "Now" competed. To answer your question, I've been experimenting with these ideas--essentially, basing the search on a more solid theoretical footing using Knuth-node classification. My understanding is that Fabien made the above design decisions so that he wouldn't inadvertently truncate the PVs produced by Fruit. In addition these items laid the ground work for future modifications (which we may see in Fruit 3.0). To really make this work you also need to throw out the root aspiration window, as too narrow a window can also cause an incorrect truncation of your PV.

I've been experimenting with a, c and d above. The most important item for Djinn was item d. The elo increase for me was less than 50 elo, but there was a definite increase. I believe the ideas have promise, but like so many things, the actual benefit is program dependent. Interestingly, though when I eliminated the root aspiration window, I saw a decrease in playing strength. Which was a bit depressing since I really like the idea of having complete PVs.

One item that has increased Djinn's playing strength lately, is that I no longer allow null-move searches if the ply is less than or equal to 2, (where the root is 0, 1... etc.). I've experimented with 1, 2 and 3 and 2 is the best value for my engine. Of course, I never allowed null-move searches at the root

regards,
--tom

One of these things I tested in NOW was "a", and it seemed to hurt by about 50 points. Of course, NOW for over 10 years has had a test and research when it detects bad things happening from chaning widnow limits from values in the hash table, so I think it does not have as severe a problem in this regard. I could send the change to someone if anyone wants to see if it would help Fruit.

Mark

[Volker Böhm]

Hi,

some answeres for Spike:

a. This must be done if any of b,c,d is answered with "yes". Else it must not be done. Alternative (not tested yet): Store a PV flag in hash.

b. This doesn?t work well for Spike. It does not reduce extensions to pv.

c, d: No pruning is done in PV.

As an example History pruning in PV is about 40 Elo less.

In PV the value keeps between Alpha, Beta. Thus there is no Cut node. Consequence: Trying history in PV seems ridiculous (exception: one ply mate check to get the history based extension).

Same for futility, how can you get your score that low that a futility cutoff can be made, but still keeping in Alpha, Beta window?


Greetings Volker

[H.G.Muller]

I am not sure that I understand what it means "not to do null-move pruning in the PV".

NMP can only have an effect when the null move fails high. How can something fail high in the PV? If we can find a move that fails high, we are obviously not in the PV, because another branch is better. If my initial window is (-INF, + INF), and I search the best (=PV) move first with minimax, the window will remain such all along the PV. So the usual condition of eval>beta should prevent me from trying NMP, because eval can never be above +INF.

In addition, if there are any problems that a true PV is unjustly cut by a null move, I don't see how you would discover it. Because of the cutoff it does not seem like a PV, and if the cutoff was made at a search depth where it was not yet the PV, by the time the previous PV is refuted, how would you ever know?

40 ELO points is a lot, so I would really like to understand what's behind this. My intuition tells me that it has something to do with positions like this:

[diag]1r6/4kppp/3pp3/N4b2/P2R4/4P1P1/5PBP/6K1 b[/diag]
In this position uMax blundered, because he did not see the 1. ..., Ra2+ in time. This puzzled me, because although the check-mate can be delayed many plies by a check and interposing the Rook and Bishop, this sacrifices material, which should be sufficient reason to avoid this branch.

When I analyzed why it did not consider Ra2 dangerous, it turned out it had a 'refutation' 2. Bf1, Bh3; 3. Nc6+, Ke8; 4. null, after which the depth was so much reduced that the mate was beyond the horizon. OK, so my QS is not very clever, missing the capture of the insufficiently defended Bishop. But that is beside the point here, unreduced branches would suffer from that as well. The main point is that it thinks it can afford a reduction on the null move, while the move that could push the trouble over the horizon (3. Nc6+) has already been played out.

So in short: because all stall-attempts have been played out the position has been relaxed to one where no delaying tactics are left. In such a position reducing the null move is not justified, and gives erroneous search results. But how to know it?

I think this is very much related to the PV issue: in the face of an unavoidable loss the PV tends to incorporate all delaying tactics for as long as the loss can still be pushed over the horizon. So this makes it more likely that NMP is unsound in the deep nodes of the PV. All branches that do not have the Nc6+ will have material losses even with the NMP at this depth, at least after Bh3. The problem is that it considers Bh3 a poor positional move (to the edge...), so it is not even in the PV (which continues with 2. ..., Pd5).

[Daniel Shawul]

a. Do not accept hash table scores if you are in the PV

this is done to avoid trimming of the pv, strenght wise it makes the engine weaker

b. Allow most extensions only if you are in the PV

I think the idea behind this is to search the pv more thoroughly.
IMO hash table move extension (IE extending pv lines by a quarter of a ply) will do as good as limiting extensions only to pv nodes.
I dont understand the reason why one would want to do extensions only at pv nodes. It means we are blind to tactics at non-pv nodes.

c. Do not allow Null Pruning if in the PV

Ofcoure we will not get a null move cut off at this nodes but we will have a better mover ordering.

d. Allow other pruning (futility, history reduction) only if not in the PV

At a pv node, only the first child is a pv node the others are cut nodes. It is obvious that we should not do these prunings before we search the first move but I dont see why we shouldnt apply it at the other children of the pv node.

Daniel

[diepeveen]

Looking over recent source code from Fruit and its derivative, I find a number of choices which differ from what has been done in many older programs. I would be interested in what other programmers have found useful in these ideas:

a. Do not accept hash table scores if you are in the PV
b. Allow most extensions only if you are in the PV
c. Do not allow Null Pruning if in the PV
d. Allow other pruning (futility, history reduction) only if not in the PV

Which of these make a difference in your programs? Which improved playing strength? Which did not help or hurt?

Mark

A) this is pretty good idea by the way. I did do this in the past in Diep. Around a few years ago i changed it to also add 'true' bounds. Basically i only had alfa and beta bound, no true bounds before. That works pretty ok.

Not using a cutoff at all in PV is what i experimented lately with. A problem is the sequential overhead you need. You simply need several millions of nodes to get back your original search depth (minus the played moves).

I tend to belief that using alfa and beta bound is better.

There is some huge advantages getting things directly from hashtable with true bound and giving direct cutoffs; you directly get reasonable big depths from hashtable and don't need that huge overhead each ply.

A big problem is to test the differences between the 2.

Diep with its low nps i run into trouble now against move 60 or so. usually at 90 0 or 60 0 or something, you are nearly out of time there. like 10 minutes left or 15 minutes left.

Within 15 seconds you simply do NOT get those few millions of nodes to get back the original depth.

Dang there comes a 10 ply search for approach A, versus 16 ply for approach giving cutoffs.

Good example: ANT-Diep in ict6

I had a 10 ply search there in a crucial phase of the game, which took care ANT could escape to a draw.

Well done by ANT of course, nevertheless 12 ply already would've won the game for me.

B) i fundamentally disagree here.

C) i'm doing something similar there. When beta == infinite then i do not try nullmove. It would get a fail low anyway.

That's because i use PVS.

D) this i find very logical. Only in 1999 i tried it different. But then i used something like dividing my move list in 2 parts.

1 part was "good moves" and 1 part was bad moves.

the good moves were like normal moves. the bad moves had always 1 ply reduction (so no research when fail high). No alfabeta dependencies on the move selection by the way. Quite nice way to search. Quickly gets 15-17 ply and with some more work 20 ply.

Similar to what Junior is doing (nowadays they seem to have many enhancements such as moves that get 2 ply reduction).

In all other prunings experiments however i never applied pruning in PV nodes. I find this quite logical.

Please realize that Fruit's concept is basically checking out the mainline very deeply and pruning the rest.

The advantage of that is that if you have big holes in your evaluation function, for example because it has near to no chessknowledge, that you don't run into trouble too soon.

The disadvantage is that getting a fail high to a better move is near to impossible. Of course for Fruit that doesn't matter as its eval won't find soon a better move anyway.

So for Fruit the combination of its search and eval is a very strong one.

For many others i doubt that this approach is the right one.

Vincent

[diepeveen]

Hi,

some answeres for Spike:

a. This must be done if any of b,c,d is answered with "yes". Else it must not be done. Alternative (not tested yet): Store a PV flag in hash.

b. This doesn?t work well for Spike. It does not reduce extensions to pv.

c, d: No pruning is done in PV.

As an example History pruning in PV is about 40 Elo less.

In PV the value keeps between Alpha, Beta. Thus there is no Cut node. Consequence: Trying history in PV seems ridiculous (exception: one ply mate check to get the history based extension).

Same for futility, how can you get your score that low that a futility cutoff can be made, but still keeping in Alpha, Beta window?


Greetings Volker

With respect to C,
how do you define "PV" node?

In diep i have alfa and beta.

For example

PV node, alfa = 0.020, beta = 0.030

So there is 10 points difference between alfa and beta.

Yet we just tried giving away a queen.
Diep will simply nullmove here when the
double nullmove condition doesn't apply.

So i can cutoff in PV nodes in Diep.

Nullmove is a very strong demand on a node to apply in order to get pruned.

Therefore i don't see why not nullmove there!

Vincent