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.
User avatar
Fabio Gobbato
Posts: 123
Joined: Fri Apr 11, 2014 8:45 am
Contact:

Killer and move encoding

Post by Fabio Gobbato » Thu Aug 14, 2014 1:26 pm

In my engine a move is encoded in a 32bit integer.
For efficiency I would like to encode it in a 16bit integer.

So, before to make a lot of changes in my engine I have tried what should be done differently with the new encoding.

In particular I have made a test with the killer moves.

With the 32bit encoding the killer move is validated if the type of piece, the origin square and the destination square will match a quiet move.

With the 16bit encoding the killer move is validated if ONLY the origin and the destination square will match a quiet move.

In my tests killer moves with 16bit encoding get worse than with 32bit encoding.

Has anyone tried this before and with what results?

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

Re: Killer and move encoding

Post by bob » Thu Aug 14, 2014 3:13 pm

Fabio Gobbato wrote:In my engine a move is encoded in a 32bit integer.
For efficiency I would like to encode it in a 16bit integer.

So, before to make a lot of changes in my engine I have tried what should be done differently with the new encoding.

In particular I have made a test with the killer moves.

With the 32bit encoding the killer move is validated if the type of piece, the origin square and the destination square will match a quiet move.

With the 16bit encoding the killer move is validated if ONLY the origin and the destination square will match a quiet move.

In my tests killer moves with 16bit encoding get worse than with 32bit encoding.

Has anyone tried this before and with what results?
What is your 16 bit encoding like? If you use 6 bits for from, 6 bits for to, that gives you 4 bits to at least include the moving piece. That ought to be near 100% reliable. This is really about speed (move ordering) rather than accuracy or whatever, so I wouldn't expect a huge penalty if you completely remove killers, assuming you still have the usual TT best move, and good captures first type of ordering.

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

Re: Killer and move encoding

Post by Fabio Gobbato » Thu Aug 14, 2014 4:38 pm

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

elcabesa
Posts: 795
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Killer and move encoding

Post by elcabesa » Thu Aug 14, 2014 4:41 pm

I never tried your scheme. I accept a killer move only it's legal

what do you mean by : get worse?
how many elo point it loose and how much games did you play?

if you try to totally disable killer moves you got better or worst result?

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

Re: Killer and move encoding

Post by Fabio Gobbato » Thu Aug 14, 2014 5:51 pm

Validate a killer if it's legal of course.

For instance if you save a killer with only "from" and "to" you could store a move of a bishop that goes from c1 to f4 and when you have to use this killer it could match with a queen that goes from c1 to f4 because you don't check the piece type but only the origin and the destination square.

And this it seems not good in my tests, about -20ELO after 2000 games

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Killer and move encoding

Post by ZirconiumX » Thu Aug 14, 2014 5:58 pm

Fabio Gobbato wrote:Validate a killer if it's legal of course.

For instance if you save a killer with only "from" and "to" you could store a move of a bishop that goes from c1 to f4 and when you have to use this killer it could match with a queen that goes from c1 to f4 because you don't check the piece type but only the origin and the destination square.

And this it seems not good in my tests, about -20ELO after 2000 games
[D]rnbqkbnr/pppp1ppp/8/4p3/5PP1/8/PPPPP2P/RNBQKBNR w KQkq

Black plays Qh4#.

If we swapped the queen and bishop around:

[D]rnbbkqnr/pppp1ppp/8/4p3/5PP1/8/PPPPP2P/RNBQKBNR w KQkq

does it affect the checkmate?

If it fails low, you simply keep searching.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

elcabesa
Posts: 795
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Killer and move encoding

Post by elcabesa » Thu Aug 14, 2014 6:17 pm

Fabio Gobbato wrote:Validate a killer if it's legal of course.

For instance if you save a killer with only "from" and "to" you could store a move of a bishop that goes from c1 to f4 and when you have to use this killer it could match with a queen that goes from c1 to f4 because you don't check the piece type but only the origin and the destination square.

And this it seems not good in my tests, about -20ELO after 2000 games
it sound very strange that this is causing elo drop. I'll do some test you puzled me :)

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

Re: Killer and move encoding

Post by bob » Thu Aug 14, 2014 9:09 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
from/to is ambiguous. Pe3xd4, Be3d4, Be3xd4, Qe4d4, Qe3xd4, Ke3d4, Ke4xd4, etc...

However, the only bad effect should be move ordering.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Killer and move encoding

Post by ZirconiumX » Thu Aug 14, 2014 9:20 pm

bob wrote:
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
from/to is ambiguous. Pe3xd4, Be3d4, Be3xd4, Qe4d4, Qe3xd4, Ke3d4, Ke4xd4, etc...

However, the only bad effect should be move ordering.
Being ambiguous with regard to piece is much easier to handle than being ambiguous with regard to square. Even in Crafty you had to put in special code to deal with being ambiguous wrt square, which I think you solved by checking the entire move list.

LAN is very ugly, but at least it's simple.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

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

Re: Killer and move encoding

Post by bob » Thu Aug 14, 2014 10:10 pm

ZirconiumX wrote:
bob wrote:
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
from/to is ambiguous. Pe3xd4, Be3d4, Be3xd4, Qe4d4, Qe3xd4, Ke3d4, Ke4xd4, etc...

However, the only bad effect should be move ordering.
Being ambiguous with regard to piece is much easier to handle than being ambiguous with regard to square. Even in Crafty you had to put in special code to deal with being ambiguous wrt square, which I think you solved by checking the entire move list.

LAN is very ugly, but at least it's simple.

Matthew:out
Not sure what you mean. I store a complete move for killers, hash move, etc. from, to, moving piece, captured piece and promotion piece. I don't see where it is worth any execution-time hassle at all just to save 5 bits or so.

Or are we talking apples and oranges? I'm talking about how to store a move using N bits, not how to display a move in SAN, although that code is extremely simple as well.

Post Reply