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.
konsolas
Posts: 141
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 7:06 pm

Cardoso wrote:
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?
-25 +/- 15, 1250 games, 40/2

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

Re: Killers and forward pruning test searches

Post by Cardoso » Mon Feb 04, 2019 11:33 pm

RubiChess wrote:
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
I guess this is very engine dependant. But what HGM said in this thread sure makes sense.
I did a search here and it looks Ippolit did clear killers at ply+2.
viewtopic.php?f=7&t=56540&p=626730&hili ... it#p626730

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

Re: Killers and forward pruning test searches

Post by RubiChess » Tue Feb 05, 2019 6:01 am

Cardoso wrote:
Mon Feb 04, 2019 11:33 pm
RubiChess wrote:
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
I guess this is very engine dependant. But what HGM said in this thread sure makes sense.
I did a search here and it looks Ippolit did clear killers at ply+2.
viewtopic.php?f=7&t=56540&p=626730&hili ... it#p626730
Maybe the rest of my move values and ordering is bad if I still can make use of the killers of distant relatives and I should focus on that :-)

What I find confusing is this: "...clear the ply+2 slot before calling any children to make sure you cannot inherit any killer from a cousin..."

In my understanding it is:
Clear at ply+1 = Use killers of siblings but not more distant relatives
Clear at ply+2 = Use killers of cousins (and of course siblings) but not more distant relatives

Maybe we have a different definition of ply here??

./Andreas

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

Re: Killers and forward pruning test searches

Post by RubiChess » Wed Feb 06, 2019 5:32 am

RubiChess wrote:
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
Clearing at ply+2 also doesn't gain ELO in RubiChess.

./Andreas

Harald
Posts: 264
Joined: Thu Mar 09, 2006 12:07 am

Re: Killers and forward pruning test searches

Post by Harald » Wed Feb 06, 2019 9:43 am

Just an untested idea:

What if there is a dynamic array
int killer_reliability[MAX_PLY]
that measures distances in the search tree and is initialised in the root with
killer_reliability[0] = 100
and in each node (at ply) when we make the first move set
killer_reliability[ply + 1] = killer_reliability[ply] + 1
and when we make other moves in that node set
killer_reliability[ply + 1] = 1

When we generate moves and want to try killer moves we look at this array
if (killer_reliability[ply] < 5) trust and use the killer information
else don't
Or use another threshold than 5.
Or give the move some weight for move ordering depending on killer_reliability[ply].

Draw a typical tree and look at the numbers. That helps to understand the array.
It is a kind of distance to common ancestors.

Harald

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 » Sat Feb 09, 2019 6:25 am

RubiChess wrote:
Wed Feb 06, 2019 5:32 am
RubiChess wrote:
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
Clearing at ply+2 also doesn't gain ELO in RubiChess.

./Andreas
What I do in Andscacs:

Code: Select all

if (king in (state - 1) is not in check) {
	(state + 2)->killers[0] = invalidmove;
	(state + 2)->killers[1] = invalidmove;
state is the current node, state +2 is two nodes ahead.

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

Re: Killers and forward pruning test searches

Post by RubiChess » Sat Feb 09, 2019 3:02 pm

cdani wrote:
Sat Feb 09, 2019 6:25 am
What I do in Andscacs:

Code: Select all

if (king in (state - 1) is not in check) {
	(state + 2)->killers[0] = invalidmove;
	(state + 2)->killers[1] = invalidmove;
state is the current node, state +2 is two nodes ahead.
Thanks for the idea but... nope. Doesn't work here.

Post Reply