When does a cut-node became an all-node?

[bob]

According to chess wiki programming is when after all candidate moves are tried, but fruit does it after first move is tried.

I thinking of trying doing things differently according node type, for example:
cut-node - use static null move (like stockfish) and don't do razoring (eval + margin < beta).
all-node - no static null move, try razor, no ordering for quiet moves...

What you guys think is a good time to switch a cut-node to all-node?

Thanks.

First, why does it matter? Are you somehow trying to type a node as PV, CUT or ALL, and then do things differently if it is CUT as opposed to ALL? A "CUT" node becomes an ALL node when there is no cutoff to be found. Most common reason is poor move ordering. This is not the best move here although we thought it was, so another move will cause a cutoff later. On occasion, it is not ordering, but is a depth issue. Suddenly you see deep enough to see that the score is worse than you expect, no matter which move you try, so none cause a cutoff...

[bob]

Switching after N moves have been tried is not very useful because decisions like LMR and pruning have already been made. The question of CUT/ALL distinctin is very interesting to me. Stockfish is the strongest program that doesn't make any such distinction. For Rybka, Ippo, Ivanhoe, Houdini, and Critter, the distinction is critical as the two types are treated very differently in many ways, such as vastly more aggressive LMR at CUT nodes and doing singular extension at CUT but not ALL nodes. In the case of Komodo, we do make the distinction, but have found it to be only marginally useful, we don't make the huge distinctions that the above programs do.

So for me it is a very puzzling question of why these huge distinctions appear to work so well in the above named programs but not in Stockfish or (to any important degree) Komodo. Anyone want to venture a guess?

Suggestion. Before going too far with this reasoning, make SURE that the idea you are talking about actually helps those other programs. A case in point. Fruit's "history pruning" that uses a history counter approach to determine which moves to reduce or not. I wrote this code in Crafty way back. Tested it. Tried to tune the history counter threshold optimally using the cluster. No luck at all, changing the history counter produced random Elo changes, all very close. I tried several different history counter approaches, as mentioned previously (and mentioned in Crafty''s main.c changelog.) Nothing helped. Uri Blass had mentioned that he had a better threshold for fruit (70 I think rather than the default 50 or whatever it was). I decided to test fruit. Changing the threshold made random Elo changes just like in Crafty. I removed the history counter from the pruning decision and it was very slightly stronger (Fruit). Same result I had found in Crafty. I spent a couple of months trying to figure out why something worked in Fruit but not in Crafty. Turns out it didn't work in Fruit either. The testing that had been done was apparently based on too few games. This was early in my cluster testing and was the first major flaw in (then) current reasoning about reductions.

So before you pull hair out, make sure it actually helps. I removed the TT singular stuff from stockfish and found no Elo change. I posted those results here a couple of years back. You might just be chasing a mirage, for all you know...

[diep]

Switching after N moves have been tried is not very useful because decisions like LMR and pruning have already been made. The question of CUT/ALL distinctin is very interesting to me. Stockfish is the strongest program that doesn't make any such distinction. For Rybka, Ippo, Ivanhoe, Houdini, and Critter, the distinction is critical as the two types are treated very differently in many ways, such as vastly more aggressive LMR at CUT nodes and doing singular extension at CUT but not ALL nodes. In the case of Komodo, we do make the distinction, but have found it to be only marginally useful, we don't make the huge distinctions that the above programs do.

So for me it is a very puzzling question of why these huge distinctions appear to work so well in the above named programs but not in Stockfish or (to any important degree) Komodo. Anyone want to venture a guess?

Suggestion. Before going too far with this reasoning, make SURE that the idea you are talking about actually helps those other programs. A case in point. Fruit's "history pruning" that uses a history counter approach to determine which moves to reduce or not. I wrote this code in Crafty way back. Tested it. Tried to tune the history counter threshold optimally using the cluster. No luck at all, changing the history counter produced random Elo changes, all very close. I tried several different history counter approaches, as mentioned previously (and mentioned in Crafty''s main.c changelog.) Nothing helped. Uri Blass had mentioned that he had a better threshold for fruit (70 I think rather than the default 50 or whatever it was). I decided to test fruit. Changing the threshold made random Elo changes just like in Crafty. I removed the history counter from the pruning decision and it was very slightly stronger (Fruit). Same result I had found in Crafty. I spent a couple of months trying to figure out why something worked in Fruit but not in Crafty. Turns out it didn't work in Fruit either. The testing that had been done was apparently based on too few games. This was early in my cluster testing and was the first major flaw in (then) current reasoning about reductions.

So before you pull hair out, make sure it actually helps. I removed the TT singular stuff from stockfish and found no Elo change. I posted those results here a couple of years back. You might just be chasing a mirage, for all you know...

Well Bob, history pruning is a special case.

We did do some statistics regarding Fruit 2.1 and figured out to our big amazement that:

a) on average history pruning was looking at 10-12 moves (versus LMR usually 1, 2 or 3 or so)

b) the history pruning concept as implemented in Fruit worked very well for Fruit, basically any difficult position where a fail high was needed at a tad larger search depth, Fruit lost on average less than 1 ply to history pruning failing high. So with and without history pruning usually it would find something at depth X simply and not X+3.

When i did do for those same set of positions statistics with Diep and history pruning, Diep needed on average X+4 ply to X+5 to fail high WITH history pruning in that same set of positions i tried.

With that i could prove that history pruning could not work for Diep.

So history pruning for Fruit back then was similar to Fruit like a normal nullmove search, as it just hardly ever needed an additional ply to fail high.

Some free search depth for Fruit in short without much of a risk.

Vincent

[sedicla]

According to chess wiki programming is when after all candidate moves are tried, but fruit does it after first move is tried.

I thinking of trying doing things differently according node type, for example:
cut-node - use static null move (like stockfish) and don't do razoring (eval + margin < beta).
all-node - no static null move, try razor, no ordering for quiet moves...

What you guys think is a good time to switch a cut-node to all-node?

Thanks.

First, why does it matter? Are you somehow trying to type a node as PV, CUT or ALL, and then do things differently if it is CUT as opposed to ALL? A
"CUT" node becomes an ALL node when there is no cutoff to be found. Most common reason is poor move ordering. This is not the best move here although we thought it was, so another move will cause a cutoff later. On occasion, it is not ordering, but is a depth issue. Suddenly you see deep enough to see that the score is worse than you expect, no matter which
move you try, so none cause a cutoff...

Well, thats what im trying to figure it out, if it matters or not. I can see that is your opinion that it does not matter.
My idea is exactly that, do different things at all and cut nodes.

[Steve Maughan]

Hi Larry,

snip...
So for me it is a very puzzling question of why these huge distinctions appear to work so well in the above named programs but not in Stockfish or (to any important degree) Komodo. Anyone want to venture a guess?

I think it's all to do with local optimums.

If we think of writing a chess program as an optimization solution there are bazillions of dimension. Each author will have their own preferences as to which path they should pursue. Maybe they try a basic piece-square evaluation and then add null move and then hash tables. At each point they will test different configurations of the element they are optimizing until they find something which they are happy with. Virtually all elements of the program interact with each other (i.e. the elements are not orthogonal); so as the program is improved it becomes a well-tuned system, where no small individual change improves the playing strength, However, if we could look across the optimization valley we could possibly see another mountain much higher than the one we're on. But to get to it require large adjustments of multiple elements of the engine.

I don't think you'll ever completely get around this problem. However, maybe one possible way to alleviate the problem is to tune different aspects of the program at the same time. For example instead of just tuning null move, also tune the passed pawn code. So you'd maybe have a pool of six candidate engines - three null move tuned and three passed pawn tuned. You'd then evaluate any improvements in on a more holistic basis.

Just my 2 cents,

Steve

[lkaufman]

Switching after N moves have been tried is not very useful because decisions like LMR and pruning have already been made. The question of CUT/ALL distinctin is very interesting to me. Stockfish is the strongest program that doesn't make any such distinction. For Rybka, Ippo, Ivanhoe, Houdini, and Critter, the distinction is critical as the two types are treated very differently in many ways, such as vastly more aggressive LMR at CUT nodes and doing singular extension at CUT but not ALL nodes. In the case of Komodo, we do make the distinction, but have found it to be only marginally useful, we don't make the huge distinctions that the above programs do.

So for me it is a very puzzling question of why these huge distinctions appear to work so well in the above named programs but not in Stockfish or (to any important degree) Komodo. Anyone want to venture a guess?

Not sure which version of Rybka you refer to, but strictly spoken Rybka search is more dependant upon a window around the rootscore.

By not treating nodes similar one takes a risk simply.

Vincent

I refer to all versions at least from 2.2 thru 3, those are the ones I worked on. I know little about earlier versions.
Bob asks whether I'm sure that making this CUT/ALL distinction helped Rybka and derivatives. I can only say that I worked closely enough with Vasik to be convinced that he would not have something like that in Rybka without convincing data to prove its worth. His test facilities then may not have been as good as Bob's, but they were substantial. Whether Ippo and other later programs tested as thoroughly I can't say.
It is clear that Rybka and derivatives use much less LMR than Stockfish at ALL nodes, but use more at CUT nodes. Since LMR at CUT nodes has much less effect, the net result is that Stockfish prunes more and reaches greater depths, though at considerable cost.
So my question is, does any strong program successfully differentiate between CUT and ALL nodes, other than the above-named programs (and to a small extent Komodo)? If not, what feature of Rybka et al makes this particular distinction work for them and not for other programs?

[diep]

Switching after N moves have been tried is not very useful because decisions like LMR and pruning have already been made. The question of CUT/ALL distinctin is very interesting to me. Stockfish is the strongest program that doesn't make any such distinction. For Rybka, Ippo, Ivanhoe, Houdini, and Critter, the distinction is critical as the two types are treated very differently in many ways, such as vastly more aggressive LMR at CUT nodes and doing singular extension at CUT but not ALL nodes. In the case of Komodo, we do make the distinction, but have found it to be only marginally useful, we don't make the huge distinctions that the above programs do.

So for me it is a very puzzling question of why these huge distinctions appear to work so well in the above named programs but not in Stockfish or (to any important degree) Komodo. Anyone want to venture a guess?

Not sure which version of Rybka you refer to, but strictly spoken Rybka search is more dependant upon a window around the rootscore.

By not treating nodes similar one takes a risk simply.

Vincent

I refer to all versions at least from 2.2 thru 3, those are the ones I worked on. I know little about earlier versions.
Bob asks whether I'm sure that making this CUT/ALL distinction helped Rybka and derivatives. I can only say that I worked closely enough with Vasik to be convinced that he would not have something like that in Rybka without convincing data to prove its worth. His test facilities then may not have been as good as Bob's, but they were substantial. Whether Ippo and other later programs tested as thoroughly I can't say.
It is clear that Rybka and derivatives use much less LMR than Stockfish at ALL nodes, but use more at CUT nodes. Since LMR at CUT nodes has much less effect, the net result is that Stockfish prunes more and reaches greater depths, though at considerable cost.
So my question is, does any strong program successfully differentiate between CUT and ALL nodes, other than the above-named programs (and to a small extent Komodo)? If not, what feature of Rybka et al makes this particular distinction work for them and not for other programs?

You're looking at one aspect Larry.

Rybka is using a trick i hadn't disclosed except for example to Anthony Cozzie, this trick i invented, namely using a bigger reduction factor when eval being some margin above beta; Rybka uses that everywhere in the search.

I simply had ZERO testhardware to test it out fully and only used it last few plies. Rybka uses that everywhere.

I'm the inventor of that trick though (now pay me royalties) and didn't dare to use it everywhere in search; limited it to last few plies. You can maybe imagine that Rybka, which in search is doing nothing new, using that trick mine, wasn't making me overall very happy.

So it reduces a full ply more with a nullmove, or more, when eval >= beta+1 pawn

SF is reducing the reduction factor based upon a table based upon search depth left.

I didn't figure out full details for every version there of any program - i don't have the time to do that.

But this is the type of risk i refer to Larry. If you reduce based upon a simple static evaluation another ply at several spots in the search, that's taking more risk with your evaluation function as search can correct your evaluation to lesser extend then.

A simple static eval gets used at start of the search. So if it has captured some material or advanced at queenside - meanwhile not seeing yet it gets overwhelmed at kingside - there is some sort of extra reduction if its eval doesn't notice it.

So when Rybka's static evaluation at start of search lines is wrong, it's sitting duck. In Diep i'm not prepared to have my own invention create a worst case for it.

In short Rybka's search can only work if its evaluation produces less errors per second than of the opponent.

Vincent

[lkaufman]

Switching after N moves have been tried is not very useful because decisions like LMR and pruning have already been made. The question of CUT/ALL distinctin is very interesting to me. Stockfish is the strongest program that doesn't make any such distinction. For Rybka, Ippo, Ivanhoe, Houdini, and Critter, the distinction is critical as the two types are treated very differently in many ways, such as vastly more aggressive LMR at CUT nodes and doing singular extension at CUT but not ALL nodes. In the case of Komodo, we do make the distinction, but have found it to be only marginally useful, we don't make the huge distinctions that the above programs do.

So for me it is a very puzzling question of why these huge distinctions appear to work so well in the above named programs but not in Stockfish or (to any important degree) Komodo. Anyone want to venture a guess?

Not sure which version of Rybka you refer to, but strictly spoken Rybka search is more dependant upon a window around the rootscore.

By not treating nodes similar one takes a risk simply.

Vincent

I refer to all versions at least from 2.2 thru 3, those are the ones I worked on. I know little about earlier versions.
Bob asks whether I'm sure that making this CUT/ALL distinction helped Rybka and derivatives. I can only say that I worked closely enough with Vasik to be convinced that he would not have something like that in Rybka without convincing data to prove its worth. His test facilities then may not have been as good as Bob's, but they were substantial. Whether Ippo and other later programs tested as thoroughly I can't say.
It is clear that Rybka and derivatives use much less LMR than Stockfish at ALL nodes, but use more at CUT nodes. Since LMR at CUT nodes has much less effect, the net result is that Stockfish prunes more and reaches greater depths, though at considerable cost.
So my question is, does any strong program successfully differentiate between CUT and ALL nodes, other than the above-named programs (and to a small extent Komodo)? If not, what feature of Rybka et al makes this particular distinction work for them and not for other programs?

You're looking at one aspect Larry.

Rybka is using a trick i hadn't disclosed except for example to Anthony Cozzie, this trick i invented, namely using a bigger reduction factor when eval being some margin above beta; Rybka uses that everywhere in the search.

I simply had ZERO testhardware to test it out fully and only used it last few plies. Rybka uses that everywhere.

I'm the inventor of that trick though (now pay me royalties) and didn't dare to use it everywhere in search; limited it to last few plies.

So it reduces a full ply more with a nullmove, or more, when eval >= beta+1 pawn

SF is reducing the reduction factor based upon a table based upon search depth left.

I didn't figure out full details for every version there of any program - i don't have the time to do that.

But this is the type of risk i refer to Larry.

A simple static eval gets used at start of the search. So if it has captured some material or advanced at queenside - meanwhile not seeing yet it gets overwhelmed at kingside - there is some sort of extra reduction if its eval doesn't notice it.

Vincent

Please clarify -- are you simply talking about increasing the null move reduction (like from 3 plies to 4, or from 4 to 5) when the score is more than a pawn plus? If this is what you refer to, its effect is pretty minor, and everyone is using this now.
Or do you mean that when the score is more than a pawn plus, the search itself is being reduced a ply, not just the null move search? If this is so, it's something new to me. In that case, could you (or anyone else) point to where this is done in Ivanhoe code, assuming that Ivanhoe uses this same technique you say is in Rybka.
Thanks.

Larry

[mcostalba]

namely using a bigger reduction factor when eval being some margin above beta

Tested (I didn't think it was such a "great secret" when I figured out it), as also tested:

1) Higher reduction when abs(eval - beta) > thresold

2) Higher reduction when eval - beta > thresold

3) Higher reduction when beta - eval > thresold

4) Higher reduction when abs(eval - beta) < thresold

Nothing helped !! Thank you.

[diep]

Please clarify -- are you simply talking about increasing the null move reduction (like from 3 plies to 4, or from 4 to 5) when the score is more than a pawn plus? If this is what you refer to, its effect is pretty minor, and everyone is using this now.

I had editted my post. Yes, amongst others i do refer to this.

It's yet another few plies of search that are dependant upon a simple static evaluation and avoid the backtracking to correct the evaluation.

It is wrong to call this minor, as when you're getting outsearched, you're dead meat, and the dead meat is even more dead if its evaluation that's already wrong in this position, adds another ply of total search reduction, by means of increasing the reduction factor.

Nullmove is that powerful especially because it reduces also positional lines, it's not just a tactical form of search.

What rybka is doing there is in between not taking a risk and the full blown risk that SF takes there as its reduction factor is in a lookuptable.

The advantage of SF there is that it always profits from a bigger search depth because of it, whereas Rybka has a real worst case there.

In Diep for now i'm not willing to soon increase the R of nullmove and i don't want to reduce more than 1 ply either with reductions.

Note we can mathematically prove that the optimum to reduce is 1 ply.

When reducing more than that, some programs already SEEM to do that for a long period of time, like junior, you also take much bigger risks.

I did do this calculation back in 1999 by the way when i toyed with reductions a lot; diep world champs 1999 did use reductions.

Where each few years i do big experiments is the last few plies. So far they all failed, even though some were promising; so far only thing that works there very well is nullmove.

Vincent