Killer moves?

[mike_bike_kite]

I tried to implement what I think are killer moves in my program and was expecting great things but sadly saw no improvement at all.

When a move causes an alpha beta cutoff (and it isn't a capture) then I put the move into a list of killer moves for that side. The score for each move is just the number of cutoffs it produced. The moves stay in this array until they get "aged out".

At the start of the computers turn I age all the moves by dividing their scores by 4. If the score drops to zero I remove it. If the move is no longer valid then I remove it. The moves it's keeping look like the moves I would expect it to keep and the ageing seems to keep the moves fresh.

When I generate my list of moves I use MVV-LVA plus I weight moves towards the centre, moves that cause checks and moves that move away from a square that was attacked by an enemy pawn. I'm now adding my killer move scores to the score each time I generate moves for a level. This should place the killer moves after all the captures.

I hoped that the killer moves would allow it to search a little deeper and that that would allow it to play better. Unfortunately it can't beat the old program and comes out pretty even.

Perhaps someone could advise what I'm doing wrong?

[Don]

I tried to implement what I think are killer moves in my program and was expecting great things but sadly saw no improvement at all.

When a move causes an alpha beta cutoff (and it isn't a capture) then I put the move into a list of killer moves for that side. The score for each move is just the number of cutoffs it produced. The moves stay in this array until they get "aged out".

At the start of the computers turn I age all the moves by dividing their scores by 4. If the score drops to zero I remove it. If the move is no longer valid then I remove it. The moves it's keeping look like the moves I would expect it to keep and the ageing seems to keep the moves fresh.

When I generate my list of moves I use MVV-LVA plus I weight moves towards the centre, moves that cause checks and moves that move away from a square that was attacked by an enemy pawn. I'm now adding my killer move scores to the score each time I generate moves for a level. This should place the killer moves after all the captures.

I hoped that the killer moves would allow it to search a little deeper and that that would allow it to play better. Unfortunately it can't beat the old program and comes out pretty even.

Perhaps someone could advise what I'm doing wrong?

It sounds like you are mixing up killers with history moves.

A killer is generally just 2 moves and it's indexed by ply of search. So there are just 2 killers for every ply. Let's call them Killer A and killer B. When you get a beta cutoff you put this move in the killer list if it's not already there, always doing whatever shuffling or replacing needed to make sure it's in slot A. (If you have to put it in slot A be sure to move the previous slot A move to slot B and lose the old B move.)

When you generate moves, you should try the hash table move first, then non-losing captures. After the captures you try killer A, then killer B, then either losing captures or the rest of the moves.

You should not store captures as killers - but I see you are doing that correctly.

The history is a different thing. For each move (for most programs indexed by Piece/TO) you try to keep statistics on what percentage of time it's the best move (out of times it was actually searched) and you sort the move list by this percentage. As you say, it's important to age it frequently. Komodo ages on the fly by giving the most recent stat update more weight but it doesn't make a lot of difference although it's important to tune this.

[marcelk]

I tried to implement what I think are killer moves in my program and was expecting great things but sadly saw no improvement at all.

When a move causes an alpha beta cutoff (and it isn't a capture) then I put the move into a list of killer moves for that side. The score for each move is just the number of cutoffs it produced. The moves stay in this array until they get "aged out".

At the start of the computers turn I age all the moves by dividing their scores by 4. If the score drops to zero I remove it. If the move is no longer valid then I remove it. The moves it's keeping look like the moves I would expect it to keep and the ageing seems to keep the moves fresh.

When I generate my list of moves I use MVV-LVA plus I weight moves towards the centre, moves that cause checks and moves that move away from a square that was attacked by an enemy pawn. I'm now adding my killer move scores to the score each time I generate moves for a level. This should place the killer moves after all the captures.

I hoped that the killer moves would allow it to search a little deeper and that that would allow it to play better. Unfortunately it can't beat the old program and comes out pretty even.

Perhaps someone could advise what I'm doing wrong?

Killer moves work when you associate them with the current level in the tree. Killer moves from level - 2 are also useful for ordering. Outside that scope they lose relevance. So if you don't split them by level you are possibly just distorting the search randomly.

[hgm]

The killer heuristic works because the refutation of one move in many positions is also the refutation of another move. This because most moves are pretty passive,and don't really alter the character of the position. So basically most moves are refuted by the same move that also refuted the null move.

Now if this refutation is a capture (e.g. beause your Queen was hanging, and if you now do nothing or something useless, he will take it), this is not much help, because with MVV/LVA sorting you would try that first anyway. But if the move is a non-capture, e.g. move away a valuable attacked piece, deliver a fork, move a Rook to the 6th rank, castle, they could be hidden amongst many non-captures, and it would take a lot of tries before you finally find it. So it is a real help if you make that move 'jump the queue', and try it first. The refutation of your sister move is much more likely to refute the current move than the move with the best positional score for moving towards the center, (say), because the latter might be tactially unsound, (e.g. goto an unsafe square, ignore a major threat to another piece, etc.). While the refutation to the sister move has been fully searched and found OK in that situation.

So what you do is remember the refutation of your sister move, in an array killer[depth]. Usually people remember two, because sometimes a move does alter the situation, and the usual refutation does not work, and a refutation peculiar to this move does, but the original refutation still might work against many other moves.

I once tried specifially remembering the null-move refutation (at each ply) plus the most recent other one, and it had about the same performance as remembering the most recent two (non-capture) cut moves at that level.

[mike_bike_kite]

That explains things. It did look kind of like it might of worked
And the name alone of "killer moves" meant I had to try and implement it.
Do I get points for trying?

I must read the wiki more closely
I must read the wiki more closely
I must read the wiki more closely
I must read the wiki more closely
I must read the wiki more closely

[Don]

You should definitely get a pretty good gain from this - depending on how good or bad your current move order is.

Even more important than this is that the captures are in the right order. I assume you know that, but just in case you do not ..... You must put the highest piece captured first, and given a tie the lowest piece doing the capture. If you have a see() routine you still want to do this, the only difference being that you want losing captures to be considered later (at least after the killers.) see() is static exchange evaluator and it basically figures out whether a capture move is winning or losing using superficial methods. If you don't have that, you can approximate one with a couple of simple rules. I can tell you more if you ask.

That explains things. It did look kind of like it might of worked
And the name alone of "killer moves" meant I had to try and implement it.
Do I get points for trying?

I must read the wiki more closely
I must read the wiki more closely
I must read the wiki more closely
I must read the wiki more closely
I must read the wiki more closely

[marcelk]

Do I get points for trying?

Lots of them.... Computer chess is not rocket science, it is a lot harder than that!

Seriously, thinking existing concepts through and tinkering with them yourself might cause some dead ends but also new discoveries. Welcome to our strange (and sometimes frustrating) hobby. New and original engines are highly appreciated.

[bob]

I tried to implement what I think are killer moves in my program and was expecting great things but sadly saw no improvement at all.

When a move causes an alpha beta cutoff (and it isn't a capture) then I put the move into a list of killer moves for that side. The score for each move is just the number of cutoffs it produced. The moves stay in this array until they get "aged out".

At the start of the computers turn I age all the moves by dividing their scores by 4. If the score drops to zero I remove it. If the move is no longer valid then I remove it. The moves it's keeping look like the moves I would expect it to keep and the ageing seems to keep the moves fresh.

When I generate my list of moves I use MVV-LVA plus I weight moves towards the centre, moves that cause checks and moves that move away from a square that was attacked by an enemy pawn. I'm now adding my killer move scores to the score each time I generate moves for a level. This should place the killer moves after all the captures.

I hoped that the killer moves would allow it to search a little deeper and that that would allow it to play better. Unfortunately it can't beat the old program and comes out pretty even.

Perhaps someone could advise what I'm doing wrong?

Killers are a "local" concept. That is, they apply to positions that are similar. In chess, "similar" means from the same area of a tree. Normally you have a small killer list for each ply in the tree. Then killers for ply=16 are only used at ply=16 for ordering. Some have tried successfully, to use killers from earlier plies as well. Cray Blitz tried current ply, then current ply - 2, etc... But you do need to keep them separate by ply because what causes a cutoff at ply=20 is probably totally unrelated to what causes a cutoff at ply=2 in the same tree...

[mike_bike_kite]

It's working nicely now and the improvement is noticeable. I'm still not where I want it to be but I'm moving in the right direction.

[Don]

It's working nicely now and the improvement is noticeable. I'm still not where I want it to be but I'm moving in the right direction.

Take care not to have the same killer twice.

Here is the code I use where "mv" is the move that produced a beta (fail hi) cutoff and it's not a capture move:

Code: Select all

    
if (mv != ka[ply])  {
  kb[ply] = ka[ply];
  ka[ply] = mv;
}