Killer moves heuristic not working in my engine.

[mathmoi]

Hi,

I implemented the killer moves heuristic in my engine and it does have an adverse effect on the number of nodes searched.

I add a move to the killers[depth] list if a) it causes a beta cutoff and b) it's not a capture or a promotion. I have tried with one, two or three killers per depth. when there is more than one I discard the oldest first.

When ordering my moves it goes like this :

1) try the TT move
2) generate and try captures ordered by MVV/LVA
3) try the killers moves (youngest first)
4) generate and try the normals moves ordered by history heuristic.

The problem is my engine explore more moves when I use the step 3) than when I skip it. That makes me think that maybe, the history heuristic is already good enough and that introducing the killer heuristic only weaken the move ordering.

Can this be the case? and how would you do to verify this? I don't really know what metrics I should extract in order to evaluate my move ordering with and without the killer move heuristic.

Thanks for your help.

[Sven]

Hi Mathieu,

have you checked that all your four sections are perfectly disjoint? You mentioned it only for section 3 (= killers) that does not include section 2 moves (= captures). But also the TT move should not be tried twice, same for the killer moves when it comes to section 4.

Just as a quick idea.

Sven

[hgm]

With a good TT it should not hurt so much to search a move twice, though: the second time will be a direct hash hit. In micro-Max I intentionally did not bother to prevent a re-search of the hash move when it gets to earching the other moves in move-en order, and this hardly caused any slowdown.

[bob]

With a good TT it should not hurt so much to search a move twice, though: the second time will be a direct hash hit. In micro-Max I intentionally did not bother to prevent a re-search of the hash move when it gets to earching the other moves in move-en order, and this hardly caused any slowdown.

On long searches the problem is more pronounced. You try the same move twice at ply=2, where the remaining depth is large, and you can get transposition misses because of all the intervening search nodes...

[mathmoi]

Hi Mathieu,

have you checked that all your four sections are perfectly disjoint? You mentioned it only for section 3 (= killers) that does not include section 2 moves (= captures). But also the TT move should not be tried twice, same for the killer moves when it comes to section 4.

Just as a quick idea.

Sven

Hi Sven, thanks for your post.

Indeed, my four sections are not totally disjoint. I though they were, but now that you mention it and I think about it, they're not.

However, as H.G. said, i'm not sure if it has any impact. I'll correct this bug and verify.

Thanks,

[mathmoi]

Hi Mathieu,

have you checked that all your four sections are perfectly disjoint? You mentioned it only for section 3 (= killers) that does not include section 2 moves (= captures). But also the TT move should not be tried twice, same for the killer moves when it comes to section 4.

Just as a quick idea.

Sven

Hi,

As I said in my other message all my sections were not disjoint. In fact the TT move could be sent again as a killer move. I have now corrected this problem and I did not saw any improvment. The search three is still bigger with the killer move heuristic than it is whitout.

[bob]

Hi Mathieu,

have you checked that all your four sections are perfectly disjoint? You mentioned it only for section 3 (= killers) that does not include section 2 moves (= captures). But also the TT move should not be tried twice, same for the killer moves when it comes to section 4.

Just as a quick idea.

Sven

Hi,

As I said in my other message all my sections were not disjoint. In fact the TT move could be sent again as a killer move. I have now corrected this problem and I did not saw any improvment. The search three is still bigger with the killer move heuristic than it is whitout.

There can only be one explanation in that case, somehow you are not maintaining the killer move list properly. You should be able to do a 6 ply search and dump the tree as it is searched. At many nodes, you will get a fail high on a non-capture. The next time you search at that ply, after the TT and capture moves, that same move should be searched first. I'd bet it is not happening. I've never seen killers fail, although for a single position anything can happen... you need to test over multiple positions to avoid this mistake.

[AndrewShort]

Hi,

I implemented the killer moves heuristic in my engine and it does have an adverse effect on the number of nodes searched.

I add a move to the killers[depth] list if a) it causes a beta cutoff and b) it's not a capture or a promotion. I have tried with one, two or three killers per depth. when there is more than one I discard the oldest first.

When ordering my moves it goes like this :

1) try the TT move
2) generate and try captures ordered by MVV/LVA
3) try the killers moves (youngest first)
4) generate and try the normals moves ordered by history heuristic.

The problem is my engine explore more moves when I use the step 3) than when I skip it. That makes me think that maybe, the history heuristic is already good enough and that introducing the killer heuristic only weaken the move ordering.

Can this be the case? and how would you do to verify this? I don't really know what metrics I should extract in order to evaluate my move ordering with and without the killer move heuristic.

Thanks for your help.

To add to the advice given, you should make sure if you have 2 killers per ply, for example, that you don't have duplicate killers. In other words, your 2 killer moves should always be unique moves. This will help, although I don't think it's the source of your problem - frankly I'm not sure what the real problem is, as killer moves are ply specific, and they do help a lot.

[Sven]

Mathieu,
how do you guarantee that your killer moves are (pseudo-)legal?
Sven

[hgm]

On long searches the problem is more pronounced. You try the same move twice at ply=2, where the remaining depth is large, and you can get transposition misses because of all the intervening search nodes...

In micro-Max you are right, as it uses a completely dumb replace-always TT. But a soon as you have some kind of depth-preferred replacement, te entry at ply=2 will never be replaced, as only some 50 entries in the entire tree can have a larger depth.

Even in Joker, which already starts flushing deep entries if their draft occupies more than its fair share in the hash tabe, there will never be enough nodes so close to the root to exceed those qouta.