Killer moves based on distance to common ancestor

[matthewlai]

Random idea of the day -

In killer moves, we make the assumption that moves that are effective for other nodes at the same ply have a high probability of being effective on the position under consideration as well.

For deep positions, this is really only true when 2 positions have a deep common ancestor. If we have 2 positions at ply=20 from 2 different root moves, chances are they will be entirely unlike one another, and the killer move from one on the other would just be noise.

It is easy to compare ancestry using search stack. An alternative way is to compute the hamming distance between the position under consideration, and the position that generated the killer move.

Is there a way to make use of that information?

[jordanbray]

It should do that automatically. The killer moves list should be a queue, and when a new one is added, you should also be removing one. This means that nodes close to one another should have (mostly) the same killer moves, and moves with a different root should have different killers.

[hgm]

Killer moves are almost always moves from direct sibblings (i.e. with the same parent), because those are the nodes visited directly before (at that ply level) when you recursively walk the tree. Some engines (Ippolit) even clear the ply+2 slot before calling any children to make sure you cannot inherit any killer from a cousin..

[matthewlai]

It should do that automatically. The killer moves list should be a queue, and when a new one is added, you should also be removing one. This means that nodes close to one another should have (mostly) the same killer moves, and moves with a different root should have different killers.

Ah yes it does. I didn't think about the tree traversal order.

[matthewlai]

Killer moves are almost always moves from direct sibblings (i.e. with the same parent), because those are the nodes visited directly before (at that ply level) when you recursively walk the tree. Some engines (Ippolit) even clear the ply+2 slot before calling any children to make sure you cannot inherit any killer from a cousin..

I wonder if it would be beneficial to do killers based on position similarity (eg. hamming distance) instead of ply. Some sort of fuzzy transposition matching.

It would require a different data structure, though.

[hgm]

I think that would be called a 'refutation table'.

[matthewlai]

I think that would be called a 'refutation table'.

The difficult part is doing fuzzy matching efficiently.

[cdani]

Instead of position similarity, I use some little hashes of refutation moves for sequences of moves of different length (2, 4 and 6 moves) in Andscacs.

[cdani]

Some engines (Ippolit) even clear the ply+2 slot before calling any children to make sure you cannot inherit any killer from a cousin..

Thanks to you mentioning it, I just tried on Andscacs and was a little win!