Killer heuristic

[bob]

Hi, I'm looking at killer moves again, and trying to figure out what I want to do.

To make it simple, suppose we just store 1 killer move, so this will be a non-capture that causes a cutoff (not sure why captures aren't included).

Captures are not included because you _always_ try captures _before_ killers. By the time you are ready to try a killer move, the captures have been done.

This seems like a good time to ask why there isn't some advantage to storing any killer move (including captures) and trying out the killer with a slightly more complex test for legality before move generation at that ply.

I presume that in general this approach must be slower and that sorted favourable captures are so effective in their own right as to be not worth storing. Although in the toy program I have written it seems to be faster when the killer is tried before full move generation. My move generator is old and slow, but it is terminal node evaluations that dominate runtime.

Thanks for any enlightenment.

I don't quite follow. Here's my move ordering and an explanation of why this is:

(1) hash move (always). This move was proved best in a previous search, it should be tried first here. I do this without generating any moves at all.

(2) captures with SEE >= 0. I only generate captures here and try the ones that appear to not be bad.

(3) killer moves (2). I do this before generating any additional moves (I have already generated captures, I still have to generate non-captures).

(4) The rest of the moves. Here I have to generate the non-captures and search them in the order generated.

So back to the original question. Killers should not be captures, because we will try the good captures _before_ we try any killers at all. We would not want to search the same capture again (we should get an instant hash fail low if we did) which would simply waste that killer.

[bob]

Thanks,

So I can basically store the top 2 killers for each ply, but if scores are nothing to go by would I overwrite like this...

Currently at ply p:
1st move-A
2nd move-B

Now, at ply p, some other branch, we have a cut off, caused by move-C

Updating, at ply p:
1st move-C
2nd move-A

Then, when we get next one, C could slide down to 2nd place.. and so on.

I donno if this is reliable enough?


Also, what kind of improvement could I expect to see? A small fraction of a ply maybe?

First, I have two killers. When I get a cutoff or back up a score > alpha, I do this in the function Killer():

Code: Select all

if (killer[ply].move1 != this_move) {
  killer[ply].move2 = killer[ply].move1;
  killer[ply].move1 = this_move;
}

I always search move1 before move 2. So if this move is not the same as move1 (which it often is) I move move1 down to move2 and store the current move as move1 so it will be tried first next time around.

The effect will vary, but it should generally produce smaller trees. How much smaller depends on lots of things, but it should usually be smaller. Not always. nothing is "always". But generally, it should be faster. I have not tested Crafty without killers in years so I really don't remember. It would be quite easy to comment the above lines out in killer.c and run a test to see what it does to performance.

[bob]

Thanks, well I guess thats identical to what I said, but ensures the killers are different which is a must.

I think I need to cofigure my move ordering a little first, I'm doing...

Hash move
Captures (sorted by MVVLVA)
Non-captures

But I read this is better...

Hash Move
Good captures
Non-captures
Losing captures

So how can I differentiate between good and bad captures?
I'm thinking Q x P is generally bad, but P x Q is generally excellent.

So maybe something along those lines?

Some ideas. RxQ is almost a guaranteed win of material, whether the Q is defended or not. QxP requires testing, most commonly by a SEE function, in order to safely determine whether the P can be captured or not.

[JVMerlino]

Hi, I'm looking at killer moves again, and trying to figure out what I want to do.

To make it simple, suppose we just store 1 killer move, so this will be a non-capture that causes a cutoff (not sure why captures aren't included).

Captures are not included because you _always_ try captures _before_ killers. By the time you are ready to try a killer move, the captures have been done.

I don't have SEE in my engine, so I only use MVV/LVA for ordering captures. I put killers in between materially winning captures and losing ones. Is that likely to be worse than putting them after all captures, as you mention above?

jm

[bob]

Hi, I'm looking at killer moves again, and trying to figure out what I want to do.

To make it simple, suppose we just store 1 killer move, so this will be a non-capture that causes a cutoff (not sure why captures aren't included).

Captures are not included because you _always_ try captures _before_ killers. By the time you are ready to try a killer move, the captures have been done.

I don't have SEE in my engine, so I only use MVV/LVA for ordering captures. I put killers in between materially winning captures and losing ones. Is that likely to be worse than putting them after all captures, as you mention above?

jm

Sounds fine to me. I have to generate all captures, as I can't generate just those that appear to win material. But I do not try the apparently losing captures until after killers. So you are doing exactly the same thing. SEE will gain you some more speed as MVV/LVA will suggest QxR before RxP, where the Rook is defended and loses material, while the pawn is undefended and wins material. So it will make your tree a bit smaller by eliminating captures that MVV/LVA would try first.

[JVMerlino]

Hi, I'm looking at killer moves again, and trying to figure out what I want to do.

To make it simple, suppose we just store 1 killer move, so this will be a non-capture that causes a cutoff (not sure why captures aren't included).

Captures are not included because you _always_ try captures _before_ killers. By the time you are ready to try a killer move, the captures have been done.

I don't have SEE in my engine, so I only use MVV/LVA for ordering captures. I put killers in between materially winning captures and losing ones. Is that likely to be worse than putting them after all captures, as you mention above?

jm

Sounds fine to me. I have to generate all captures, as I can't generate just those that appear to win material. But I do not try the apparently losing captures until after killers. So you are doing exactly the same thing. SEE will gain you some more speed as MVV/LVA will suggest QxR before RxP, where the Rook is defended and loses material, while the pawn is undefended and wins material. So it will make your tree a bit smaller by eliminating captures that MVV/LVA would try first.

Excellent. Thanks, Bob!

jm

[JVMerlino]

Hi, I'm looking at killer moves again, and trying to figure out what I want to do.

To make it simple, suppose we just store 1 killer move, so this will be a non-capture that causes a cutoff (not sure why captures aren't included).

Captures are not included because you _always_ try captures _before_ killers. By the time you are ready to try a killer move, the captures have been done.

I don't have SEE in my engine, so I only use MVV/LVA for ordering captures. I put killers in between materially winning captures and losing ones. Is that likely to be worse than putting them after all captures, as you mention above?

jm

Sounds fine to me. I have to generate all captures, as I can't generate just those that appear to win material. But I do not try the apparently losing captures until after killers. So you are doing exactly the same thing. SEE will gain you some more speed as MVV/LVA will suggest QxR before RxP, where the Rook is defended and loses material, while the pawn is undefended and wins material. So it will make your tree a bit smaller by eliminating captures that MVV/LVA would try first.

Here's a wrinkle I just thought of with my non-SEE implementation. If you only add non-capture moves to the killer list, but a materially losing capture somehow causes a cutoff, it won't get placed higher in the move ordering, and will continue to be (admittedly slightly) lower, depending on the MVV/LVA score in comparison with all other potential captures.

Is this a potentially common loophole that I should close? I'm thinking not, but I'm appealing to the experts.

Or is this just another reason for me to implement SEE?

jm

[bob]

Hi, I'm looking at killer moves again, and trying to figure out what I want to do.

To make it simple, suppose we just store 1 killer move, so this will be a non-capture that causes a cutoff (not sure why captures aren't included).

Captures are not included because you _always_ try captures _before_ killers. By the time you are ready to try a killer move, the captures have been done.

I don't have SEE in my engine, so I only use MVV/LVA for ordering captures. I put killers in between materially winning captures and losing ones. Is that likely to be worse than putting them after all captures, as you mention above?

jm

Sounds fine to me. I have to generate all captures, as I can't generate just those that appear to win material. But I do not try the apparently losing captures until after killers. So you are doing exactly the same thing. SEE will gain you some more speed as MVV/LVA will suggest QxR before RxP, where the Rook is defended and loses material, while the pawn is undefended and wins material. So it will make your tree a bit smaller by eliminating captures that MVV/LVA would try first.

Here's a wrinkle I just thought of with my non-SEE implementation. If you only add non-capture moves to the killer list, but a materially losing capture somehow causes a cutoff, it won't get placed higher in the move ordering, and will continue to be (admittedly slightly) lower, depending on the MVV/LVA score in comparison with all other potential captures.

Is this a potentially common loophole that I should close? I'm thinking not, but I'm appealing to the experts.

Or is this just another reason for me to implement SEE?

jm

That's an interesting question, and here's the risk. You reach a position where at the last ply, your opponent moved a piece that removed a critical defender for a pawn. Now QxP is perfectly playable even though the pawn is defended. As the Queen can not be taken for some tactical reason. So this becomes a killer. And you keep trying it early in every search after this one for a while, and it fails low each time.

Whether that will hurt or not needs testing, but intuition says it will, although how much is a guess. It will replace a more normal capture (killers are not normally captures so you usually have two of 'em, but now you'd only have one. SEE solves this of course, for the most part, although it doesn't understand cases like above and QxP will still be searched late as it appears to lose material according to SEE as well.

[Martin Brown]

This seems like a good time to ask why there isn't some advantage to storing any killer move (including captures) and trying out the killer with a slightly more complex test for legality before move generation at that ply.

I presume that in general this approach must be slower and that sorted favourable captures are so effective in their own right as to be not worth storing. Although in the toy program I have written it seems to be faster when the killer is tried before full move generation. My move generator is old and slow, but it is terminal node evaluations that dominate runtime.

Thanks for any enlightenment.

I don't quite follow. Here's my move ordering and an explanation of why this is:

(1) hash move (always). This move was proved best in a previous search, it should be tried first here. I do this without generating any moves at all.

(2) captures with SEE >= 0. I only generate captures here and try the ones that appear to not be bad.

(3) killer moves (2). I do this before generating any additional moves (I have already generated captures, I still have to generate non-captures).

(4) The rest of the moves. Here I have to generate the non-captures and search them in the order generated.

So back to the original question. Killers should not be captures, because we will try the good captures _before_ we try any killers at all. We would not want to search the same capture again (we should get an instant hash fail low if we did) which would simply waste that killer.

I expect the problem here is my lack of understanding of the right way to do things. Thanks for your patience if this is a really dumb question. I am not sure what you mean here by hash move (lookup into the hash table of previous results for the position or PV from a shallower search?). The code I am resurrecting dates from the 1980's. The way it was done then was very crude:

Generate all moves
Try killer(s) {any move allowed as a killer}
Try sorted list of moves {excluding killers}

I changed it to apply the killers with a test for legality before move generation. So it is now

Test killer legal - try killer
Generate all moves
Try list of sorted moves excluding killers.

I can see that allowing captures as killers pollutes the killer line with responses to daft opponent moves that leave pieces en prise. But isn't that issue taken care of by having two killers and a usage heuristic?

And if a superficially bad capture that is tried after all other moves causes a beta cutoff why should it not enter the killer line ?

I am sure your way is better since that is how everybody seems to do it now, but I am curious to better understand why... Thanks again.

[Bo Persson]

This is what I do

Code: Select all

if (new_killer != killer1[ply]) {
killer2[ply] = killer1[ply];
killer1[ply] = new_killer;
}

Another option is to have a counter for each killer, incrementing it if the same move reappears, or replacing the least popular if it is a new one.