Move encoding

[hgm]

I agree that the having to consult the board to decode the move (e.g. whether a7a8 is a promotion or a Rook move, e1a1 is a castling or a Queen move, e5d6 is an e.p. or a regular capture by a Pawn) is a bad idea. Also because it is totally unnecessary and inadequate to reach the goal of non-redundant encoding. Using 6 bits for from- and to-square plus a field to indicate promotion piece (at least 2 x 6 + 2 bits in orthodox Chess) still can specify a redundant promotion piece on non-Pawn and non-last-rank moves.

With an extra single-bit flag for indicating all special moves (or, equivalently, reserving 7 bits for the to-square, so that it can run from 0-127, the numbers 64-127 being unique encodings for all special moves (i.e. moves that require more than simply moving the piece as per (from, to) specs). All additional information needed to describe the special move then can be taken from a table indexed by the to-square. This saves a lot of space in the move encoding. Which might not be very important for orthodox Chess, but can make a real difference in variants with larger boards.

[Stan Arts]

Three bytes for me.
From, to and promotion. While I can fit that into two bytes I like to separate them as turning a given number of bits out of a word into a number takes operations. A bitshift and/or a bitwise And and ofcourse adds complexity.
Type of move (castling, en passant) is not so important to me as I like to keep rights as separate flags to the position but piece type is. When I'm moving a knight I don't have to check if I'm doing a castlemove and I don't want to have touch the information in any way. Now for example when I'm not promoting my promotionbyte can contain any rubble and it's fine. While I can easily encode piecetype into the promotionbyte or even add another byte that will add more complexity than just to look at the board. The extra operations required to deal with that information also very probably offsets the speedup of not always having to look at the board and even worse, it's also storing the same information twice which I really do not like.

No doubt storing extra information such as movetype could make sorting and pruning decisions a bit easier (though higher up the tree speed doesn't matter anyway) but most of the time it just seems a bunch of clutter.

[Gerd Isenberg]

There are 22678 (+1 for null move) distinct, full qualified moves per side (15 bit, take a word), including from, to, piece, captured piece (if any) and all special moves and promotions. During generation with mailbox-less bitboards, one may traverse distinct from-and to piece sets anyway so that piece codes are implicit, so why not use those enumeration to encode moves? During make move, a small table indexed by this move-number has all the information needed, including combined zobrist delta, and f.i. performing xor on the central quadbitboard representation, and to and/add values to the remaining position object on a ply stack, including piece nibble counters, material difference (index), castling rights, Halfmove clock, and ep-square.

[Rein Halbersma]

There are 22678 (+1 for null move) distinct, full qualified moves per side (15 bit, take a word), including from, to, piece, captured piece (if any) and all special moves and promotions. During generation with mailbox-less bitboards, one may traverse distinct from-and to piece sets anyway so that piece codes are implicit, so why not use those enumeration to encode moves? During make move, a small table indexed by this move-number has all the information needed, including combined zobrist delta, and f.i. performing xor on the central quadbitboard representation, and to and/add values to the remaining position object on a ply stack, including piece nibble counters, material difference (index), castling rights, Halfmove clock, and ep-square.

What is a small table? 22K of zobrist deltas eats into your L1/L2 caches, wouldn't it? Perhaps recomputign them on the fly takes less cycles? Just asking, perhaps you have measured this already?)

[Gerd Isenberg]

There are 22678 (+1 for null move) distinct, full qualified moves per side (15 bit, take a word), including from, to, piece, captured piece (if any) and all special moves and promotions. During generation with mailbox-less bitboards, one may traverse distinct from-and to piece sets anyway so that piece codes are implicit, so why not use those enumeration to encode moves? During make move, a small table indexed by this move-number has all the information needed, including combined zobrist delta, and f.i. performing xor on the central quadbitboard representation, and to and/add values to the remaining position object on a ply stack, including piece nibble counters, material difference (index), castling rights, Halfmove clock, and ep-square.

What is a small table? 22K of zobrist deltas eats into your L1/L2 caches, wouldn't it? Perhaps recomputign them on the fly takes less cycles? Just asking, perhaps you have measured this already?)

Small compared to other tables
I didn't try that exactly - still I'll expect a lot of L1/L2 hits, since moves didn't change that much randomly between plies and frontier siblings. To balance it, may be without magic tables but pure register computation for sliding attacks?

[rreagan]

During generation with mailbox-less bitboards, one may traverse distinct from-and to piece sets anyway so that piece codes are implicit, so why not use those enumeration to encode moves?

Hi Gerd, do you mean you have a list of bitboards that serve as your move list?

[Gerd Isenberg]

During generation with mailbox-less bitboards, one may traverse distinct from-and to piece sets anyway so that piece codes are implicit, so why not use those enumeration to encode moves?

Hi Gerd, do you mean you have a list of bitboards that serve as your move list?

Hi Russel,

no, I mean short or int-moves, but classical 6+2 bitboard representation. During move generation, a more or less unrolled loop over six source bitboards (own pawns, ...queen, king), serializing each (bitscan loop) for the from-squares, and getting its piece attacks. The next inner loop over six target sets (opp queens, rooks, ... empty), (pawns are handled differently anyway), each time intersected with the attacks to serialize the result, the to-squares, combined with the from-square, and possibly piece-codes and scaled material-gain score, as 32-bit int move-object into the move-list. So disjoint nested bb-traversal in LVA-MVV order, makes the redundant 8x8 boards unnecessary.

[Aleks Peshkov]

My representation of a move needs only From and To squares. If I need to convert internal move to algebraic notation without position additional 1-bit flag to mark any special move is needed.

Castling encoded as Rook captures King. It allows to skip explicit test for rare case of pinned rook in Chess960 castling. I store castling right together with its rook, so it simplifies other code too.

En passant capture encoded as Pawn captures Pawn. That also simplifies things in move generation.

Promotion piece type encoded in place of Rank of destination square. I store all moves of a single piece in the bitboard, so it is beneficial to fit all distinct promotion moves here.

[Rebel]

Still using the 8-bit 6502 approach, 2 bytes. Don't like the use of 16-bit words because it's still penalized (extra cycle).

byte-1 : from square
byte-2 : to square

In case of promotion in move_gen the to-square is coded as follows:

Code: Select all

bit-7       : on (as a token of promotion)
bit-6|5|4|3 : Q|R|B|N
bit-2|1|0   : direction (capture left, forward, capture right)

Then via a simple table look-up (using the bits) I get the offset to the to-square and the promotion type.

[asanjuan]

this is the move type definition and macros that I'm using in Rhetoric.

Code: Select all

#define NULL_MOVE 0x00000000
#define ERROR_MOVE 0xFFFFFFFF

#define maskFrom 0x003F
#define maskTo 0x3F00

#define maskPromotion 0xC000
#define maskEspecial 0x0080 //bit for promotions
#define maskCheck 0x0040

#define maskPromotionN 0x0000
#define maskPromotionB 0x4000
#define maskPromotionR 0x8000
#define maskPromotionQ 0xC000

#define From(x) (x & maskFrom)
#define To(x) ((x & maskTo) >>8)

#define setFrom(mv, x) mv |= (MoveType)x
#define setTo&#40;mv,x&#41; mv |= ((&#40;MoveType&#41;x << 8&#41; & maskTo&#41;
#define setEspecial&#40;mv&#41; mv |= maskEspecial //is a promotion
#define setCheck&#40;mv&#41; mv |= maskCheck
#define setPromotion&#40;mv, mc&#41; mv |= mc


#define getEspecial&#40;mv&#41; (&#40;mv & maskEspecial&#41;!=0&#41; //means is a promotion
#define getPromotion&#40;mv&#41; &#40;mv & maskPromotion ) //gets the piece for promotion
#define isCheck&#40;mv&#41; (&#40;mv & maskCheck )!=0&#41;

//the move will include the sorting value in the upper 16 bits
//&#40;sort value must be always positive. On pst sort, use only for forward moves&#41; &#40;Robert Hyatt's idea of not using history&#41;
#define setSortValue&#40;move,value&#41; move |= &#40;value&#41;<<16
#define getSortValue&#40;move&#41; (&#40;signed short&#41;&#40;move >> 16&#41;)
#define onlyMove&#40;move&#41; &#40;move & 0x0000FFFF&#41;  //removing only the sort value

typedef signed int MoveType; //longer data type, older was 16 bit

this approach has the advantage that to sort the moves in the search based on history, pst, or whatelse, is equivalent to sort the moves directly as any other integer, just because the upper 8 bits are used to sort the moves.
To detect enpassant and castling moves I have to check at the board, but nothing more.

Hope it helps.

Alberto.