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.

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.

I do check that my killer moves are not duplicates.

[mathmoi]

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

I check for pseudo-legality. A move is pseudo-legal if the moved piece is on the from square and is attacking the "to" square. I also check if the captured piece is on the "to" square (or not if it's not a capture). I have special checks for castling and prises en passant.

[bob]

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.

It is possible that several of those "50 entries" have the same depth, _and_ have the same lower N bits so that they point to the same table entry. I store the last one (most recent with same depth) which would overwrite the first and lose that entry.

[Sven]

The problem is my engine explore more moves when I use the step 3) than when I skip it.

Just to be sure: with "more moves" you mean that you compare a fixed-depth search with killer moves to a search to the same fixed depth without killer moves, is that right?

Sven

[hgm]

[quote="bob]It is possible that several of those "50 entries" have the same depth, _and_ have the same lower N bits so that they point to the same table entry. I store the last one (most recent with same depth) which would overwrite the first and lose that entry.[/quote]
Yes, this is possible. But the chances are very low in a table of a few million entries. Most people juse shallowest-of-4 replacement, so you would need 4 of those entries to map to the same bucket to flush any of them out. The chances of hat happening at level = 2 are asronomicaly small.

And even if it would occasionally happen through a fluke, the cost is very low, as all the level-3 daughter nodes would be very unlikely to experience the same fluke at the same time. So in stead of getting the hash hit in the node itslf, you would get hash hits in it daughters. So a 1-ply search would make you recover, no matter what the remaining depth was.

[bob]

[quote="bob]It is possible that several of those "50 entries" have the same depth, _and_ have the same lower N bits so that they point to the same table entry. I store the last one (most recent with same depth) which would overwrite the first and lose that entry.

Yes, this is possible. But the chances are very low in a table of a few million entries. Most people juse shallowest-of-4 replacement, so you would need 4 of those entries to map to the same bucket to flush any of them out. The chances of hat happening at level = 2 are asronomicaly small.

And even if it would occasionally happen through a fluke, the cost is very low, as all the level-3 daughter nodes would be very unlikely to experience the same fluke at the same time. So in stead of getting the hash hit in the node itslf, you would get hash hits in it daughters. So a 1-ply search would make you recover, no matter what the remaining depth was.[/quote]

I don't disagree, but don't forget that this can happen _anywhere_ in the tree, and the idea of searching the same node twice several times certainly offends my sense of optimization.

[mathmoi]

The problem is my engine explore more moves when I use the step 3) than when I skip it.

Just to be sure: with "more moves" you mean that you compare a fixed-depth search with killer moves to a search to the same fixed depth without killer moves, is that right?

Sven

Yes, that's righ. I should have said "more nodes". And yes it's at a fixed depth and I tried multiple positions.

[adams161]

one interesting stat to keep when debugging killer moves, is when you play a kilerr move have 2 counters, one is the number of times you play a killer move in search the other is the number of times this played killer move produces a beta cuttoff.

I.e if you might play 500 killer moves and get 100 beta cuttofs ( just making up the numbers ). if you see something funny, like your playing not X killer moves but some huge amount, thats a problem. if you are not getting any cuttoffs at all, thats a problem.

Mike

[mathmoi]

one interesting stat to keep when debugging killer moves, is when you play a kilerr move have 2 counters, one is the number of times you play a killer move in search the other is the number of times this played killer move produces a beta cuttoff.

I.e if you might play 500 killer moves and get 100 beta cuttofs ( just making up the numbers ). if you see something funny, like your playing not X killer moves but some huge amount, thats a problem. if you are not getting any cuttoffs at all, thats a problem.

Mike

Hi Mike,

That's a good idea I did not think of. I will try this.

Thanks

[adams161]

i'm a little confused by your answer to the do you generate legal killer moves, you said something like i check for pseudo legality. and you mentioned that you check that the captured pieces is on the 'to' square if its a capture or its not if its a non capture. That sort of implies you're generating capture moves as killer moves.

but earlier when you gave your move ordering you said you tried all captures before you do killer moves.

the way i do any move sorting is i reorder the move list.

i.e. if i have moves 1, 2, 3, 4, 5 and its the first move so top is 0,

if i want 4 to be the first move i do a swap,

4, 1, 2, 3, 5
and top is now 1. this way its impossible if i have a move that i'm looking for twice to ever find it twice since with top 1 all i see on my next pass is

1, 2, 3, and 5 because 4 is a move below top.

If you are doing something like that then i would think the effect of having killer moves be also captures is you would not find your move and this can produce two things,

one, if your smoothly transitioning to the next move ordering scheme you would play a history move
two, if your not smoothly transitioning you would not play one unordered move before transitioning to history.

the other possiblity is if the move is a capture in killers, you play it twice.

Mike