Killer and move encoding

[Sven]

6 bit for origin square
6 bit for destination square
2 bit promotion or flag
2 bit flag

I would like to use the same encoding for hash, killer and move lists but it seems that validate killers with only "from" and "to" squares behave differently from validate them with "piece type", "from", and "to".

In the second way the engine is stronger but if I want to use this move encoding in the engine I should use a different one for the killer moves

I do the same as you do but I did not notice such a big strength difference. But of course you are free to store a "KillerMove" instead of only a "Move", and let the "KillerMove" entry include "from", "to" and "movingPiece" instead of the original "Move" data, still requiring 16 bit only. Then your functions to store and to validate killer moves might both need to take the type of the moving piece as an additional argument.

[Fabio Gobbato]

It could swap a bishop move with a queen move but also a rook move with a pawn move.
I haven't checked every time the search use such a killer, I have only made a test with the two different solutions.

[Sven]

It could swap a bishop move with a queen move but also a rook move with a pawn move.
I haven't checked every time the search use such a killer, I have only made a test with the two different solutions.

How do you check pseudo-legality of a killer move? Do you try killer moves after having tried all captures and prior to generating all quiet moves, so that you check a killer move's pseudo-legality with a separate function? Or do you generate moves and only later detect whether a move is a killer move, and use this information for move ordering (e.g. by assigning a higher score)?

In the former case it might be possible that the pseudo-legality check has some problem, for instance that a pawn double step is accepted even if one of the two squares in front of the pawn is occupied.

[hgm]

I don't get it. A killer is a move that was put in the killer table by a sibbling node. So say for the sake of argument that white is to move. The killer moves are now moves that were good in a position reached from the same parent, where black did a different move.

So how can the piece type not match if the from-square matches? neither taking back the black move leading to the current position, nor the black move leading to the position supplying the killer can have displaced any of your pieces. Except when the piece that performed the killer move originally is now captured, in which case the move would certainly be illegal, as there is an opponent piece on the from-square now.

[ZirconiumX]

To extend HGM's point, you can keep the last move in the board, and simply skip the killer if the dest square of the last move is equal to the from square of the killer move.

Matthew:out

[Sven]

I don't get it. A killer is a move that was put in the killer table by a sibbling node. So say for the sake of argument that white is to move. The killer moves are now moves that were good in a position reached from the same parent, where black did a different move.

This is only true if you understand the killer move table exactly like this, and you therefore always clear the killer moves of ply p+1 when entering a new node at ply p. I also think that your interpretation is quite common. But aren't other interpretations possible as well?

Maybe clearing killer moves of ply p+1 would already help the OP to solve his case but I think it would be better to find out first why he gets such an unusual strength difference (since that might indicate another problem).

[bob]

I don't get it. A killer is a move that was put in the killer table by a sibbling node. So say for the sake of argument that white is to move. The killer moves are now moves that were good in a position reached from the same parent, where black did a different move.

So how can the piece type not match if the from-square matches? neither taking back the black move leading to the current position, nor the black move leading to the position supplying the killer can have displaced any of your pieces. Except when the piece that performed the killer move originally is now captured, in which case the move would certainly be illegal, as there is an opponent piece on the from-square now.

Killers don't necessarily come from same parent. And, at least in my case, I also try killers from earlier plies as well, which produces a measurable speed gain in time to depth (better ordering).

Also, if you store 2 killers, the "parent" node can cause you to repeatedly store the same killer that works, but killer#2 is still there, and comes from who-knows-what position.

Another also, when you walk down a deep line, don't you try killers at the current ply that might have come from a totally different position since the first time you get back to this node, you might have made 20 moves in the preceding path to get here, yet the killers are still sitting there waiting for you to try what worked the last time this specific ply was reached, no matter what the parent position was.

[bob]

I don't get it. A killer is a move that was put in the killer table by a sibbling node. So say for the sake of argument that white is to move. The killer moves are now moves that were good in a position reached from the same parent, where black did a different move.

This is only true if you understand the killer move table exactly like this, and you therefore always clear the killer moves of ply p+1 when entering a new node at ply p. I also think that your interpretation is quite common. But aren't other interpretations possible as well?

Maybe clearing killer moves of ply p+1 would already help the OP to solve his case but I think it would be better to find out first why he gets such an unusual strength difference (since that might indicate another problem).

You should test this. I did and I do NOT clear the killers, period. There are killers that work everywhere in the tree. o-o is a common one. No matter where it is tried, if it is legal, it is often good. Why avoid trying moves that were good in the past? I've not seen any program that does clear p+1 although I have not looked at most since the idea seems quite odd and counter-productive to me.

[Fabio Gobbato]

I use killer moves from the same ply but not necessary have the same parent node.
And I also reuse killers from the last search shifted by two ply.

[DavidEather]

Will he get any speed up at all? I assume he is on a 32-bit PC. In general programing I haven't noticed any improvement in using 16-bits when the machine is 32-bit native. I imagine some speed up could come from reduced cache misses but is that going to be significant?