Killer heuristic

[hgm]

I have always stored killer moves as a (fromSqr, toSqr) pair. But I just realized there could be a problem with that: there could be another piece on that fromSqr, which happens to also has the move that created the killer had. E.g. the killer move could be Pe4-e5, forking a Bishop on d6 and Knight on f6, while protected by a Pawn on d4. But in the current position there could be a Queen on e4 instead...

It seems this can only happen if you don't clear the killer slots at ply+1 when you enter the node at ply. If you do clear those, killers at ply+1 can only be communicated between sisters, i.e. positions reached by different moves of player X, while they are moves of his opponent. Now moves of X never displace pieces of his opponent, so the piece making the kill must either be the same or have been captured. (In orthodox Chess, that is. In some variants there are 'catapult pieces' that displace other pieces, and in 'Magnetic Chess' a move to a square draws both enemies and friends closer to that square, so that different moves by X might have drawn different opponent pieces to the same square.)

But if you don't clear the killer slot, you can inherit killers from cousin nodes, sharing their grand-parent. Then it can really be that after having played e2-e4 in that grand parent, you refuted all, but in any case the last opponent move with e4-e5. And then you get to Qe4 in that grand parent (when the Q and P both captured something there this has even larger probability, as this would be MVV/LVA order!), and the Queen would now try to make the killer move of the Pawn. Which is more suicidal than killing...

Are there any programs that test if the piece of a killer move stays the same? Or should we just always clear the killer slots for the next level, atthe top of Search()?

[bob]

I have always stored killer moves as a (fromSqr, toSqr) pair. But I just realized there could be a problem with that: there could be another piece on that fromSqr, which happens to also has the move that created the killer had. E.g. the killer move could be Pe4-e5, forking a Bishop on d6 and Knight on f6, while protected by a Pawn on d4. But in the current position there could be a Queen on e4 instead...

It seems this can only happen if you don't clear the killer slots at ply+1 when you enter the node at ply. If you do clear those, killers at ply+1 can only be communicated between sisters, i.e. positions reached by different moves of player X, while they are moves of his opponent. Now moves of X never displace pieces of his opponent, so the piece making the kill must either be the same or have been captured. (In orthodox Chess, that is. In some variants there are 'catapult pieces' that displace other pieces, and in 'Magnetic Chess' a move to a square draws both enemies and friends closer to that square, so that different moves by X might have drawn different opponent pieces to the same square.)

But if you don't clear the killer slot, you can inherit killers from cousin nodes, sharing their grand-parent. Then it can really be that after having played e2-e4 in that grand parent, you refuted all, but in any case the last opponent move with e4-e5. And then you get to Qe4 in that grand parent (when the Q and P both captured something there this has even larger probability, as this would be MVV/LVA order!), and the Queen would now try to make the killer move of the Pawn. Which is more suicidal than killing...

Are there any programs that test if the piece of a killer move stays the same? Or should we just always clear the killer slots for the next level, atthe top of Search()?

I store the complete move. Moving piece, source/destination squares, captured piece, promotion piece...

Only takes a single 32 bit value and with that, I can do a simple validity check and try the move without going through a move generation.

[jwes]

I have always stored killer moves as a (fromSqr, toSqr) pair. But I just realized there could be a problem with that: there could be another piece on that fromSqr, which happens to also has the move that created the killer had. E.g. the killer move could be Pe4-e5, forking a Bishop on d6 and Knight on f6, while protected by a Pawn on d4. But in the current position there could be a Queen on e4 instead...

It seems this can only happen if you don't clear the killer slots at ply+1 when you enter the node at ply. If you do clear those, killers at ply+1 can only be communicated between sisters, i.e. positions reached by different moves of player X, while they are moves of his opponent. Now moves of X never displace pieces of his opponent, so the piece making the kill must either be the same or have been captured. (In orthodox Chess, that is. In some variants there are 'catapult pieces' that displace other pieces, and in 'Magnetic Chess' a move to a square draws both enemies and friends closer to that square, so that different moves by X might have drawn different opponent pieces to the same square.)

But if you don't clear the killer slot, you can inherit killers from cousin nodes, sharing their grand-parent. Then it can really be that after having played e2-e4 in that grand parent, you refuted all, but in any case the last opponent move with e4-e5. And then you get to Qe4 in that grand parent (when the Q and P both captured something there this has even larger probability, as this would be MVV/LVA order!), and the Queen would now try to make the killer move of the Pawn. Which is more suicidal than killing...

Are there any programs that test if the piece of a killer move stays the same? Or should we just always clear the killer slots for the next level, atthe top of Search()?

Or not worry about it, if it only rarely happens, as the consequence is slightly worse move ordering.

[Henk]

I store references to moves in an array of dictionaries that map them to statistics so I can compute their rating. It's not that easy to create the slowest engine.