Fuzzy killers

[Evert]

Inspired by the discussion in the history pruning thread, I did a quick experiment (no games though) with what I call "fuzzy killers". A fuzzy killer is a move that is not a killer move, but that has the same piece/to as a killer move (but a different from square, obviously). Another way may be "approximate killer". The idea is that if you can use piece/to for history (you don't are where the piece comes from, only where it's going), perhaps you can do something similar with killers.

I didn't have time to run any significant number of games, so I did an experiment with benchmark, the idea being that if it improves move ordering it probably improves the benchmark. As a matter of fact, it didn't - nodes searched went up by a few %. I also looked at a number of examples of fuzzy killers that turned up in the search and many of them look rather silly (so I decided to exclude moves with SEE<0 and not bother at all if the side to move is in check), but some looked quite reasonable.

The interesting thing is when I looked at statistics for number of beta cutoffs caused by "fuzzy killers" compared to the number of "fuzzy killers" that failed to produce a cut-off. To my surprise (because of the benchmark results) the number of fuzzy killers that produced a cutoff vastly outnumbered the number that didn't (I didn't save the numbers, but it was something like 1000 to 1). Unless I made a mistake somewhere (and I'll check that) this suggests to me that there is something to be gained from the idea, so I was wondering whether anyone has tried something similar?

[Don]

Inspired by the discussion in the history pruning thread, I did a quick experiment (no games though) with what I call "fuzzy killers". A fuzzy killer is a move that is not a killer move, but that has the same piece/to as a killer move (but a different from square, obviously). Another way may be "approximate killer". The idea is that if you can use piece/to for history (you don't are where the piece comes from, only where it's going), perhaps you can do something similar with killers.

I didn't have time to run any significant number of games, so I did an experiment with benchmark, the idea being that if it improves move ordering it probably improves the benchmark. As a matter of fact, it didn't - nodes searched went up by a few %. I also looked at a number of examples of fuzzy killers that turned up in the search and many of them look rather silly (so I decided to exclude moves with SEE<0 and not bother at all if the side to move is in check), but some looked quite reasonable.

The interesting thing is when I looked at statistics for number of beta cutoffs caused by "fuzzy killers" compared to the number of "fuzzy killers" that failed to produce a cut-off. To my surprise (because of the benchmark results) the number of fuzzy killers that produced a cutoff vastly outnumbered the number that didn't (I didn't save the numbers, but it was something like 1000 to 1). Unless I made a mistake somewhere (and I'll check that) this suggests to me that there is something to be gained from the idea, so I was wondering whether anyone has tried something similar?

I think you made a mistake somewhere to get 1000 to 1.

But the ideas is probably perfectly fine although I don't expect a gain. Killers are bit different that normal history moves because they are based on specific moves that VERY LIKELY are playable RIGHT NOW.

In Komodo the killers are alread semi-fuzzy by default. A move type in Komodo is just an integer with a from square and to square and depends on context. So it's fuzzy already. However, there are 3 bits used to signal special moves such as promotion type and other things and this also includes a pawn move forward 2 squares. So it's "semi-fuzzy"!

[Evert]

I think you made a mistake somewhere to get 1000 to 1.

Indeed: I didn't include moves that failed to improved alpha, only moves that improved alpha and then failed to improve beta.
Numbers are more even now, about 4:1 if I don't actually use the fuzzy killer for move ordering. If I do, however, the ratio drops to 4:3. This only directly affects some 10^4 nodes out of 10^7, so any potential savings are always going to be small. The killer (no pun intended) though is the increase in node count, which is much more than the potential savings. Clearly getting it wrong hurts more than getting it right, even when it's right more often than it's wrong.

Killers are bit different that normal history moves because they are based on specific moves that VERY LIKELY are playable RIGHT NOW.

It occurred to me that any potential benefit is also going to be reduced by history (it's somewhat redundant with that), which I don't have in Jazz.