Killer heuristic

[cms271828]

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).

I presume we have a killer move for each ply of the search, so if we are in some branch at some ply p, and we get a cutoff, would we overwrite the killermove at ply p in the killer array? Or, would we store the score with the killer move, and overwrite if this new move has a greater or equal score?

Also, wouldn't it be wise to try killers from previous plies too, instead of just from the ply we are in? I'm thinking we could do all even/odd ply, as half the entries in killer array will be for other side.

Thanks

[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 presume we have a killer move for each ply of the search, so if we are in some branch at some ply p, and we get a cutoff, would we overwrite the killermove at ply p in the killer array? Or, would we store the score with the killer move, and overwrite if this new move has a greater or equal score?

Scores are meaningless as most killers come from a fail-high where you have no idea about how high the score really is. This is also why we normally use 2 killers, That lets you keep one sort of long-lasting killer when you have an occasional one-shot killer that only refutes the previous move.

Also, wouldn't it be wise to try killers from previous plies too, instead of just from the ply we are in? I'm thinking we could do all even/odd ply, as half the entries in killer array will be for other side.

Thanks

We did that in Cray Blitz and it worked. Certainly worth testing in your program.

[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 presume we have a killer move for each ply of the search, so if we are in some branch at some ply p, and we get a cutoff, would we overwrite the killermove at ply p in the killer array? Or, would we store the score with the killer move, and overwrite if this new move has a greater or equal score?

Scores are meaningless as most killers come from a fail-high where you have no idea about how high the score really is. This is also why we normally use 2 killers, That lets you keep one sort of long-lasting killer when you have an occasional one-shot killer that only refutes the previous move.

Also, wouldn't it be wise to try killers from previous plies too, instead of just from the ply we are in? I'm thinking we could do all even/odd ply, as half the entries in killer array will be for other side.

Thanks

We did that in Cray Blitz and it worked. Certainly worth testing in your program.

You might not want to go too far back as the positions start to be way different.

[cms271828]

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?

[opraus]

This is what I do

Code: Select all

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

[Edmund]

[...]

Also, wouldn't it be wise to try killers from previous plies too, instead of just from the ply we are in? I'm thinking we could do all even/odd ply, as half the entries in killer array will be for other side.

Thanks

We did that in Cray Blitz and it worked. Certainly worth testing in your program.

You might not want to go too far back as the positions start to be way different.

Killermoves are usually refered to when assigning good moves to certain plies.

More general approaches are:

Countermove Heuristic: assign good moves as answer to certain opponent moves

and

History Heuristic: count the number of cutoffs a certain move brings and order according to that

[Martin Brown]

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.

[cms271828]

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?

[Edsel Apostol]

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.

Hi Martin,

Most strong engines are already doing that. They try hash move first without generating any move. There is only a routine to check if that hash move is valid for that position. After that most strong engines generate captures only but defer the losing captures determined by SEE to be tried last. The losing captures are being saved in a list. After good captures, they are trying the killer moves without generating the remaining non-capture moves. It is tested for legality as usual just like what is done in hash move. If it still didn't produce a cutoff at this stage, then it generates all the remaining moves. Note that after this and there is still no cutoff the losing captures that was saved previously are tried last. Hope this helps.

[Edsel Apostol]

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?

This has been discussed a lot before. There seems to a topic just like this in one of the recent threads. By the way, you can try to visit the chess wiki here for reference:

http://chessprogramming.wikispaces.com/Move+Ordering