Pruning / reduction depending on king safety

[xr_a_y]

Who has already tried this kind of search / eval dependency ? limiting pruning and reduction based on king danger.

[Alayan]

I'm not aware of a successful implementation of such an idea in a modern AB engine.

I discussed it a bit on SF's github : https://github.com/official-stockfish/S ... ssues/2016

One possible idea to improve on such positions without tanking overall performance is to do search extension/reduce pruning on lines where the position is seen as good despite a king danger lopsided against SF.

However, it didn't really lead to actual patch attempts.

Since a few months, one of my big long-term ideas is to not just compute "eval" from a position, but also another value, "messiness" or "uncertainty" which would be a measure of how likely the static eval is to be wrong, directing search to explore more the lines following uncertain positions and less the lines from "simple" positions.

But as there is no prior art and thus no reference frame as to how to do things, it's hard to get started. Passing more values around from the eval to the search involves some complications.

Using a tuning set to tune terms evaluating how messy a position is would be a big help once the basic tricks are established.

Regarding specifically king danger, I would guess that the higher (KD_white + KD_black) - abs(KD_white - KD_black) the more it is likely that one side is actually winning ; and so you'd want to explore more those subtrees.

[Rebel]

Who has already tried this kind of search / eval dependency ? limiting pruning and reduction based on king danger.

When a move (like Qd1-h5) improves the attack on the enemy king, reduce less or don't reduce at all.

[xr_a_y]

I'm not aware of a successful implementation of such an idea in a modern AB engine.

I discussed it a bit on SF's github : https://github.com/official-stockfish/S ... ssues/2016

One possible idea to improve on such positions without tanking overall performance is to do search extension/reduce pruning on lines where the position is seen as good despite a king danger lopsided against SF.

Good, so not a too bad idea i'll try something.

Regarding specifically king danger, I would guess that the higher (KD_white + KD_black) - abs(KD_white - KD_black) the more it is likely that one side is actually winning ; and so you'd want to explore more those subtrees.

The higher you say ? is that right ? if KDW is around KDB then this is KDW+KDB, but if there are far away this is KDW+KDB - max(KDW,KDB) which is thus a smaller number no ?

[xr_a_y]

Since a few months, one of my big long-term ideas is to not just compute "eval" from a position, but also another value, "messiness" or "uncertainty" which would be a measure of how likely the static eval is to be wrong, directing search to explore more the lines following uncertain positions and less the lines from "simple" positions.

I have in mind something somehow similar but using an NN. I wanna try to loop around texel tuning positions and try to fit a NN that will "correct" wrong values (the one where the sigmoid of the static score do not represent at all the final outcome of the game), giving at least a draw score.

So if static_score != 0 and sigmoid(static_score) * game_outcome < 0, the value to learn would be -static_score and the parameter would be many things/patterns from eval. I was planning to simply use a MLP for that.

[AndrewGrant]

A good starting point would be to make a new base version, named AlwaysComputeKS, where you get the KingSafety score at the top of each node. If you can then use that information to gain elo vs AlwaysComputeKS, then you can start thinking about ways to efficiently store the King Safety component.

Lets suppose that this gains elo:

Code: Select all

// Compute LMR value
...
if (KingSafety[US] > X) R -= 1;
if (KingSafety[THEM] > X) R -= 2;
...

For example, I believe I have 2 spare bits in each Transposition Table entry. Then you could have the following changes, from a usual function. Instead of evaluate() returning an integer, it could return a 3-pair, (eval, WhiteKS, BlackKS). You could then set those extra bits in the TT based on whether or not WhiteKS > X, and BlackKS > X.

I've not looked an your engine recently, but if you ALWAYS compute an eval at each node, as is done in Ethereal // Laser // Xiphos // Stockfish // Everyone(?), then 95% of the "slowdown" is easily resolved with these changes.

But chasing speed is an afterthought. Prove that the engine can play better chess with the knowledge first. Maybe I will try this myself.

[xr_a_y]

A good starting point would be to make a new base version, named AlwaysComputeKS, where you get the KingSafety score at the top of each node. If you can then use that information to gain elo vs AlwaysComputeKS, then you can start thinking about ways to efficiently store the King Safety component.

Lets suppose that this gains elo:

Code: Select all

// Compute LMR value
...
if (KingSafety[US] > X) R -= 1;
if (KingSafety[THEM] > X) R -= 2;
...

For example, I believe I have 2 spare bits in each Transposition Table entry. Then you could have the following changes, from a usual function. Instead of evaluate() returning an integer, it could return a 3-pair, (eval, WhiteKS, BlackKS). You could then set those extra bits in the TT based on whether or not WhiteKS > X, and BlackKS > X.

I've not looked an your engine recently, but if you ALWAYS compute an eval at each node, as is done in Ethereal // Laser // Xiphos // Stockfish // Everyone(?), then 95% of the "slowdown" is easily resolved with these changes.

But chasing speed is an afterthought. Prove that the engine can play better chess with the knowledge first. Maybe I will try this myself.

That is what I did indeed. I now have access to kdanger in search, and this does not affect strength. For now I didn't find a formula to use it to reduce pruning and/or reduction, but I'm trying to CLOP some parameters for 2 days now ... without great success ...

I'll post something if it worth some elo.