Killer Moves

[cms271828]

Hi, I don't understand how killer moves work.

How can a move at X ply deep be a good choice for all positions X ply deep?

Is there any good psuedocode available for this?

Thanks

[bob]

Hi, I don't understand how killer moves work.

How can a move at X ply deep be a good choice for all positions X ply deep?

Is there any good psuedocode available for this?

Thanks

Because of the nature of the search. For example, suppose you are white and you can play Nxc7+ forking the black king and rook. Move ordering won't help you pick a better move before the Nxc7+ so you can only try each move one at a time, in more or less random order. And almost all of them will result in Nxc7 winning at least the exchange. By making Nxc7 a killer move, we will always try it first after each of your moves, until you eventually move the king, move the rook, or defend c7.

That's the basic idea, it works because the search is a very uninformed way of finding the best move.

[CRoberson]

It is not the way you state it.

If the move is best at this ply at this point in the search,
it "might" be good at several other points. The killer move concept
often works in tactical positions.

Does it always work? No. Does it improve search speeds? Yes.

Simple Pseudo code:

------------------------------------------------------------------------
before the progressive deepening code for each new position:
------------------------------------------------------------------------

Reset all killer array elements to 0.

---------------------------
In move choice
---------------------------
bonus the move ordering value of any move
that matches the killer move for this ply.

----------------------
In the search
----------------------
If (this move value exceeds beta)
{
save the move for this ply as a killer move
}

[mjlef]

Actually, most programs I know only have non-captures as killers. Most captures are well ordered base don what they capture plus SEE. But in any case, the idea is to push good moves higher to be searched sooner. A typical ordering is:

Hash/IID move
good/equal captures
killers
non-captures
losing captures

Some programs have a killer move that leads to mate, an insterst is before the good/equal captures. If Bob is proposing making a "checking move killer", that is certainly worth a try. It might order a low valued capture above the others if it leads to a fork.

[hgm]

If a move at ply X is good, it is in fact very unlikely to be good everywere at ply X. But the way the killer heuristic is implemented, and the order in which you walk the tree, makes it that you won't try it at every node at ply X. As you only keep one or two killers for the entire X-level, the killers are very quickly overwritten, and thus very local.

Most of the time you only try a killer in a node that is a brother of the one where the killer was found (or worked last time). I.e. they have the same parent, at X-1 ply. And under those conditions, it is not unlikely at all that the killer will work. E.g. if the killer is a fork, delivered by a Knight on two Rooks. It is very likely that this same fork refutes most of what the opponent does, if it refuted his null move first. Only moves that specifically prevent the fork (by covering the square it would be given on, or moving one of the Rooks away pre-emptively) might help, and on those you would try the killer in vain.

So the main use of the killer is that pre-existing fatal threats are tried before other non-captures. (Captures you try before the killer anyway, so it makes no sense to make a capture killer. Unless you try bad captures after the killer. In that case you might benifit from allowing the killer to be a bad capture.)

[bob]

Actually, most programs I know only have non-captures as killers. Most captures are well ordered base don what they capture plus SEE. But in any case, the idea is to push good moves higher to be searched sooner. A typical ordering is:

Correct. So change my Nxc7+ to just Nc7+ where c7 is vacant.

Hash/IID move
good/equal captures
killers
non-captures
losing captures

Some programs have a killer move that leads to mate, an insterst is before the good/equal captures. If Bob is proposing making a "checking move killer", that is certainly worth a try. It might order a low valued capture above the others if it leads to a fork.

[bob]

If a move at ply X is good, it is in fact very unlikely to be good everywere at ply X. But the way the killer heuristic is implemented, and the order in which you walk the tree, makes it that you won't try it at every node at ply X. As you only keep one or two killers for the entire X-level, the killers are very quickly overwritten, and thus very local.

Most of the time you only try a killer in a node that is a brother of the one where the killer was found (or worked last time). I.e. they have the same parent, at X-1 ply. And under those conditions, it is not unlikely at all that the killer will work. E.g. if the killer is a fork, delivered by a Knight on two Rooks. It is very likely that this same fork refutes most of what the opponent does, if it refuted his null move first. Only moves that specifically prevent the fork (by covering the square it would be given on, or moving one of the Rooks away pre-emptively) might help, and on those you would try the killer in vain.

So the main use of the killer is that pre-existing fatal threats are tried before other non-captures. (Captures you try before the killer anyway, so it makes no sense to make a capture killer. Unless you try bad captures after the killer. In that case you might benifit from allowing the killer to be a bad capture.)

Actually killers from other ply levels also often work well at this ply. In Cray Blitz (and other programmers have also done this in the past) we tried killers from other plies after trying the killers from the current ply. Most of the time the killer is not the best move, but fortunately we try other moves first. Hash move. Good captures. But once you are into the "whatever is left stage, killers from any ply are good choices when compared to just random moves.

[Michael Sherwin]

If a move at ply X is good, it is in fact very unlikely to be good everywere at ply X. But the way the killer heuristic is implemented, and the order in which you walk the tree, makes it that you won't try it at every node at ply X. As you only keep one or two killers for the entire X-level, the killers are very quickly overwritten, and thus very local.

Most of the time you only try a killer in a node that is a brother of the one where the killer was found (or worked last time). I.e. they have the same parent, at X-1 ply. And under those conditions, it is not unlikely at all that the killer will work. E.g. if the killer is a fork, delivered by a Knight on two Rooks. It is very likely that this same fork refutes most of what the opponent does, if it refuted his null move first. Only moves that specifically prevent the fork (by covering the square it would be given on, or moving one of the Rooks away pre-emptively) might help, and on those you would try the killer in vain.

So the main use of the killer is that pre-existing fatal threats are tried before other non-captures. (Captures you try before the killer anyway, so it makes no sense to make a capture killer. Unless you try bad captures after the killer. In that case you might benifit from allowing the killer to be a bad capture.)

Actually killers from other ply levels also often work well at this ply. In Cray Blitz (and other programmers have also done this in the past) we tried killers from other plies after trying the killers from the current ply. Most of the time the killer is not the best move, but fortunately we try other moves first. Hash move. Good captures. But once you are into the "whatever is left stage, killers from any ply are good choices when compared to just random moves.

They are also good choices when the rest of the moves are not ordered randomly. In RomiChess when the remaining depth > 3 ply the remaining moves are ordered by a shallow search for each move with an open window (-beta - 100, -alpha + 100). Not searching the killers first performes worse.

[Bill Rogers]

I have a small problems understanding also. I realize that the 'killer' gives the best refutation for a given ply but we also save the principal variation which give us the best move at each ply. Is there a real difference or can they sometimes be one and the same?
Bill

[bob]

I have a small problems understanding also. I realize that the 'killer' gives the best refutation for a given ply but we also save the principal variation which give us the best move at each ply. Is there a real difference or can they sometimes be one and the same?
Bill

The PV is a single path, while we search millions of different paths. And each path has to be ordered reasonably. So yes, the PV moves will be killers for a while, perhaps during an entire iteration. Because many times, a move on the PV is a good move whether the path is actually played as given or the moves are changed around a bit..