Killers and forward pruning test searches

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Cardoso
Posts: 284
Joined: Thu Mar 16, 2006 6:39 pm

Killers and forward pruning test searches

Post by Cardoso » Sun Jan 27, 2019 11:33 pm

When we do a reduced/test search to try to make a beta cuttof like Null Move Search / ProbCut / Multi-Cut Pruning, Internal iterative deepening (for getting a best move to try first), etc, it came to my mind that killers generated inside those searches must be of inferior quality because of the reduced depths of those searches. We are creating kiilers up in the tree with shallow searches. I mean if there is already a good killer at the current ply that came from a deep search, but we then start a reduced search to try a beta cutoff, that killer could be replaced because it has an higher score although it came from a considerably reduced search. All of this in the context of calling the search with search(pos, color, ply, ...", I could use "ply+1" for the test search, but then the side to move of two consecutive plies in some of those test searches will be the same and that interfers with other stuff.
I tried to avoid replacing killers inside those "test" searches but still use whatever killers are available for move ordering, but this resulted in generally bigger trees.
I guess the "fact" of killers being ply dependant is the root of the problem and offcourse the fact of some of those test searches being called with alpha/beta shifted by a certain margin triggers new best moves more easily that end up in the killer array.
Another thing I observed is lower numbers on fail highs on the first move percentage statistic.
In fact I don't use just one variable to test the rate of FH on the first move, I use 4.
So if I use all the forward pruning test searches I usually have 80%10%3%1%, that means 80% of FH were on the first move, 10% on the second move and so on. Now if I switch off those algorithms with test searches I now get 93%2%1%0%, but offcourse the engine gets weaker.
So those test searches to try to make an early cutoff do make the engine stronger but move ordering seems to be affected.
I really don't pay to much attention to these FH on the first 4 moves statistics, but... something doesn't look right.
Another thing that improves those numbers a lot is if I only do those statistic using "if (depth > 5*PLY)", but this might mean very little.

I don't remember anyone mention this. Maybe it's not a problem at all and I'm just seeing things.
What do you guys say about this?

User avatar
hgm
Posts: 23364
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Killers and forward pruning test searches

Post by hgm » Mon Jan 28, 2019 9:17 am

Killers are very local. Some engines even enforce that (presumably because it was shown to gain Elo) by explicitly clearing the killer slots for the daughter level when they enter a node. This means you could never inherit a killer from any node other than a sibbling in the same search. Then the situation you escribe can never occur. Even if you don't clear killer slots it is very unlikely this situation would ever occur. Killers from more distant relatives are unlikely to be any good, no mater what depth they are for. The position they came from is usually too different.

User avatar
cdani
Posts: 2103
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Killers and forward pruning test searches

Post by cdani » Mon Jan 28, 2019 10:06 pm

hgm wrote:
Mon Jan 28, 2019 9:17 am
Killers are very local. Some engines even enforce that (presumably because it was shown to gain Elo) by explicitly clearing the killer slots for the daughter level when they enter a node.
Yes, some elo win.

Cardoso
Posts: 284
Joined: Thu Mar 16, 2006 6:39 pm

Re: Killers and forward pruning test searches

Post by Cardoso » Sun Feb 03, 2019 4:43 pm

hgm wrote:
Mon Jan 28, 2019 9:17 am
Killers are very local. Some engines even enforce that (presumably because it was shown to gain Elo) by explicitly clearing the killer slots for the daughter level when they enter a node. This means you could never inherit a killer from any node other than a sibbling in the same search. Then the situation you escribe can never occur. Even if you don't clear killer slots it is very unlikely this situation would ever occur. Killers from more distant relatives are unlikely to be any good, no mater what depth they are for. The position they came from is usually too different.
"daughter level" means ply+1 or ply+2 ?
For example when entering a node at ply=20, should I clear all killers at ply=21 or ply=22 ?

thanks,
Alvaro

RubiChess
Posts: 95
Joined: Fri Mar 30, 2018 5:20 am

Re: Killers and forward pruning test searches

Post by RubiChess » Sun Feb 03, 2019 6:22 pm

cdani wrote:
Mon Jan 28, 2019 10:06 pm
hgm wrote:
Mon Jan 28, 2019 9:17 am
Killers are very local. Some engines even enforce that (presumably because it was shown to gain Elo) by explicitly clearing the killer slots for the daughter level when they enter a node.
Yes, some elo win.
Interesting Information. I will try that. Thanks.

./Andreas

User avatar
cdani
Posts: 2103
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Killers and forward pruning test searches

Post by cdani » Sun Feb 03, 2019 10:15 pm

Cardoso wrote:
Sun Feb 03, 2019 4:43 pm
hgm wrote:
Mon Jan 28, 2019 9:17 am
Killers are very local. Some engines even enforce that (presumably because it was shown to gain Elo) by explicitly clearing the killer slots for the daughter level when they enter a node. This means you could never inherit a killer from any node other than a sibbling in the same search. Then the situation you escribe can never occur. Even if you don't clear killer slots it is very unlikely this situation would ever occur. Killers from more distant relatives are unlikely to be any good, no mater what depth they are for. The position they came from is usually too different.
"daughter level" means ply+1 or ply+2 ?
For example when entering a node at ply=20, should I clear all killers at ply=21 or ply=22 ?

thanks,
Alvaro
viewtopic.php?t=56540

User avatar
hgm
Posts: 23364
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Killers and forward pruning test searches

Post by hgm » Mon Feb 04, 2019 9:22 am

Cardoso wrote:
Sun Feb 03, 2019 4:43 pm
"daughter level" means ply+1 or ply+2 ?
For example when entering a node at ply=20, should I clear all killers at ply=21 or ply=22 ?
It means ply+1. This prevents inheriting killers from cousins or more distant relatives. So only children of the same node can share their cut-moves as killers.

konsolas
Posts: 178
Joined: Sun Jun 12, 2016 3:44 pm
Location: London
Full name: Vincent
Contact:

Re: Killers and forward pruning test searches

Post by konsolas » Mon Feb 04, 2019 4:41 pm

Hmm, Topple loses about 10 Elo if I implement this. It uses less nodes for the same depth on some positions, but more nodes on other positions. Strange.

Cardoso
Posts: 284
Joined: Thu Mar 16, 2006 6:39 pm

Re: Killers and forward pruning test searches

Post by Cardoso » Mon Feb 04, 2019 5:34 pm

konsolas wrote:
Mon Feb 04, 2019 4:41 pm
Hmm, Topple loses about 10 Elo if I implement this. It uses less nodes for the same depth on some positions, but more nodes on other positions. Strange.
Could you please post the number of games you used and the statistics details?

RubiChess
Posts: 95
Joined: Fri Mar 30, 2018 5:20 am

Re: Killers and forward pruning test searches

Post by RubiChess » Mon Feb 04, 2019 6:44 pm

konsolas wrote:
Mon Feb 04, 2019 4:41 pm
Hmm, Topple loses about 10 Elo if I implement this. It uses less nodes for the same depth on some positions, but more nodes on other positions. Strange.
RubiChess also loses Elo when clearing killers of ply+1. Clearing at ply+2 is more promising but tests still running.

./Andreas

Post Reply