Killer Moves

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
cms271828
Posts: 316
Joined: Wed Apr 12, 2006 8:47 pm

Killer Moves

Post by cms271828 » Sun Mar 09, 2008 7:28 pm

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
Colin

bob
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Killer Moves

Post by bob » Sun Mar 09, 2008 10:04 pm

cms271828 wrote: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
Posts: 2037
Joined: Mon Mar 13, 2006 1:31 am
Location: North Carolina, USA
Contact:

Re: Killer Moves

Post by CRoberson » Sun Mar 09, 2008 10:05 pm

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
Posts: 1467
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Killer Moves

Post by mjlef » Mon Mar 10, 2008 6:39 am

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.

User avatar
hgm
Posts: 25905
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Killer Moves

Post by hgm » Mon Mar 10, 2008 8:42 am

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
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Killer Moves

Post by bob » Tue Mar 11, 2008 12:07 am

mjlef wrote: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
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Killer Moves

Post by bob » Thu Mar 13, 2008 12:43 am

hgm wrote: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
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Killer Moves

Post by Michael Sherwin » Thu Mar 13, 2008 5:20 am

bob wrote:
hgm wrote: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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

User avatar
Bill Rogers
Posts: 3562
Joined: Thu Mar 09, 2006 2:54 am
Location: San Jose, California

Re: Killer Moves

Post by Bill Rogers » Thu Mar 13, 2008 6:01 am

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
Posts: 20923
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Killer Moves

Post by bob » Thu Mar 13, 2008 6:11 am

Bill Rogers wrote: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..

Post Reply