Pruning / reduction depending on king safety

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
User avatar
xr_a_y
Posts: 1006
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Pruning / reduction depending on king safety

Post by xr_a_y » Sun Feb 02, 2020 4:42 pm

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

Alayan
Posts: 207
Joined: Tue Nov 19, 2019 7:48 pm
Full name: Alayan Feh

Re: Pruning / reduction depending on king safety

Post by Alayan » Sun Feb 02, 2020 5:34 pm

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.

User avatar
Rebel
Posts: 4998
Joined: Thu Aug 18, 2011 10:04 am

Re: Pruning / reduction depending on king safety

Post by Rebel » Sun Feb 02, 2020 5:54 pm

xr_a_y wrote:
Sun Feb 02, 2020 4:42 pm
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.
90% of coding is debugging, the other 10% is writing bugs.

User avatar
xr_a_y
Posts: 1006
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Pruning / reduction depending on king safety

Post by xr_a_y » Sun Feb 02, 2020 6:24 pm

Alayan wrote:
Sun Feb 02, 2020 5:34 pm
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.
Alayan wrote:
Sun Feb 02, 2020 5:34 pm
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 ?

User avatar
xr_a_y
Posts: 1006
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Pruning / reduction depending on king safety

Post by xr_a_y » Sun Feb 02, 2020 6:31 pm

Alayan wrote:
Sun Feb 02, 2020 5:34 pm
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
Posts: 529
Joined: Tue Apr 19, 2016 4:08 am
Location: U.S.A
Full name: Andrew Grant
Contact:

Re: Pruning / reduction depending on king safety

Post by AndrewGrant » Tue Feb 04, 2020 8:12 am

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.

User avatar
xr_a_y
Posts: 1006
Joined: Sat Nov 25, 2017 1:28 pm
Location: France

Re: Pruning / reduction depending on king safety

Post by xr_a_y » Tue Feb 04, 2020 8:20 am

AndrewGrant wrote:
Tue Feb 04, 2020 8:12 am
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.

Post Reply