Killer and move encoding

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Sven
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Killer and move encoding

Post by Sven » Thu Aug 14, 2014 10:15 pm

Fabio Gobbato wrote: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.

User avatar
Fabio Gobbato
Posts: 123
Joined: Fri Apr 11, 2014 8:45 am
Contact:

Re: Killer and move encoding

Post by Fabio Gobbato » Fri Aug 15, 2014 7:14 am

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
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Killer and move encoding

Post by Sven » Fri Aug 15, 2014 3:18 pm

Fabio Gobbato wrote: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.

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

Re: Killer and move encoding

Post by hgm » Sat Aug 16, 2014 5:38 pm

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
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Killer and move encoding

Post by ZirconiumX » Sat Aug 16, 2014 8:00 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Sven
Posts: 3820
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Killer and move encoding

Post by Sven » Sat Aug 16, 2014 9:59 pm

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

Re: Killer and move encoding

Post by bob » Sat Aug 16, 2014 10:15 pm

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

Re: Killer and move encoding

Post by bob » Sat Aug 16, 2014 10:17 pm

Sven Schüle wrote:
hgm wrote: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.

User avatar
Fabio Gobbato
Posts: 123
Joined: Fri Apr 11, 2014 8:45 am
Contact:

Re: Killer and move encoding

Post by Fabio Gobbato » Sun Aug 17, 2014 7:11 am

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
Posts: 15
Joined: Fri Aug 15, 2014 1:24 am

Re: Killer and move encoding

Post by DavidEather » Sun Aug 17, 2014 11:32 am

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?

Post Reply