## Killer and move encoding

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Fabio Gobbato
Posts: 146
Joined: Fri Apr 11, 2014 8:45 am
Full name: Fabio Gobbato
Contact:

### Killer and move encoding

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

### Re: Killer and move encoding

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.

Fabio Gobbato
Posts: 146
Joined: Fri Apr 11, 2014 8:45 am
Full name: Fabio Gobbato
Contact:

### Re: Killer and move encoding

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: 830
Joined: Sun May 23, 2010 11:32 am
Contact:

### Re: Killer and move encoding

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?

Fabio Gobbato
Posts: 146
Joined: Fri Apr 11, 2014 8:45 am
Full name: Fabio Gobbato
Contact:

### Re: Killer and move encoding

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

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: 830
Joined: Sun May 23, 2010 11:32 am
Contact:

### Re: Killer and move encoding

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

### Re: Killer and move encoding

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

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

### Re: Killer and move encoding

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.