To ponder on this a bit more: 8-bit encoding would work by encoding piece number and move number for that piece type. Pawns would need 16 codes each (3 moves times 4 promotion choices). For 8 Pawns that consumes 96 codes. Rook and Bishop have 14 moves, for another 56 codes, the Queen gets 28 codes, King and Knights each 8. That brings us up to 204 codes. Plus 2 for castlings. Downside is that the meaning depends on the side to move (but this is usually known), that for Pawns it depends on their location (promotion to Queen (say) being used for normal moves of non-promoting Pawns, and to Knight for e.p. or double-push). And that it cannot handle positions with super-numerary pieces, although there is room to accomodate 2 Queens and 3 Knights. And that steps in the negative direction must wrap around the board, like it is toroidal. And that it is not resistant to handling the case where two identical pieces swap location, unless you interpret the piece number as the ordering on the board rather than in the piece list. For a program that has to work on a micro-controller with 512 bytes RAM this is probably what I would do, but otherwise it would be a little extreme.
On average a Knight as 5.25 moves, a Bishop 8.75, a Rook 14. Together that makes on average 28 possible moves from a given square. So the total number of moves is 64*28. With 11 bits you could enumerate these, and have 256 codes over for specifying promotions (22 x 4 = 88 combinations of step and promotion choice for each color), 2 x 8 = 16 double-pushes, 2 x 14 = 28 e.p. captures and 4 castlings. So you could use these 11 bits as index to a table that provides from-square, to-square, e.p.-square (after double-push). That groups Pawn double-pushes with the normal moves, and makes the branck you need to catch the special moves very accurately predictable (as promotion, castling and e.p. capture are really rare).
Code: Select all
fromSqr = fromTable[move];
toSqr = toTable[move];
if(move < 64*28+16) { // normal moves and double-pushes
epSqr = epTable[move]; // for normal moves the table holds the INVALID code
} else { // move that needs special board update
epSqr = INVALID;
if(move >= 64*28+16+28+4) { // promotion
promoPiece = epTable[move];
...
} else if(move > 64*28+16+28) { // castling
rookFrom = epTable[move];
rookTo = toSqr + fromSqr >> 1;
...
} else { // e.p. capture
victimSqr = epTable[move];
...
}
}
Disadvantage is that you need 6KB in table space, which causes cache pressure; advantage is that the common case only contains one (correctly predicted) branch.
When the board step is encoded rather than the to-square itself, one can do with 12 bits and small tables. A Queen can have 56 different move steps, the Knight has 8 other. That already requires all 64 codes. But even with contiguous 0-63 square numbering, it is easy to have the purely vertical moves wrap, so that moving up 7 ranks is the same as moving down 1: just AND the calculated to-square with 077. So there is then no need for the negative steps, freeing 8 codes for indicating specials. These could be used to indicate left / right / center promotion, left / right e.p. capture and double-push. In combination with the rank of the from-square this fully specifies the type of special move. If the white and black double-pushes get assigned different codes, they would not even have to be treated as special, when we look up the e.p. square in a 58-byte table (relative to the from-square) for all normal moves; this might be faster than an often-mispredicted branch. Promotion implies the rank, so the rank-number of the from-square can be used to indicate the promotion piece. Castling and e.p. capture also have implied ranks, but there are only 2 castling moves (left or right), while the e.p. capture is fully determined by the from-square and the e.p. square (and thus only needs a single code), so that the rank-field of the from-square is not needed, and can keep its own (redundant) value.
Code: Select all
signed char steps[64] = {
...
+16, -16, +2, -2, 0, +1, -1, 0 // entry 56 and further (W & B double push, L & R castling, e.p., L, R & M promotion)
};
signed char epTable[58] = {
-1, -1, ... // use -1 as code for no e.p. rights
...
0, 0
};
toCode = move & 077;
fromSqr = move >> 6 & 077;
step = steps[toCode];
if(toCode < 58) { // common case: normal move (incl. double push)
skipSqr = (fromSqr ^ 030) | epTable[toCode]; // flips rank
toSqr = victimSqr = fromSqr + step & 077;
} else { // rare: castling, promotion or e.p. capture
static signed char rankCorrect[] = { 0, 060, 020, 040, 040, 020, 060, 0 }; // after XOR produces 0, 070, 0, 070, ...
static signed char promoTable[] = { n, N, b, B, r, R, q, Q };
static signed char rookTable[] = { -4, -1, 0, 0, 0, 3, 1 }; // zero values unused
skipSqr = -1; // doesn't generate e.p. rights
if(toCode == 60) { // e.p. capture
toSqr = epSqr; // the e.p. square is presumably known
victimSqr = toSqr ^ 010; // shift one rank
...
} else {
toSqr = fromSqr + step; // this is only the sideway step of the move (for color-independence)
if(toCode > 60) { // promotion
int rank = fromSqr >> 3;
toSqr ^= rankCorrect[rank]; // 8-byte table, shifts to-square to 1st/8th rank
promoPiece = promoTable[rank]; // 8-byte table, 4 white and 4 black choices
fromSqr = toSqr - step; // reconstruct true rank from-square
victimSqr = toSqr;
...
} else { // castling (a sideway step is just what we needed)
victimSqr = toSqr;
rookTo = fromSqr + rookTable[step + 2];
rookFrom = fromSqr + rookTable[step + 3];
...
}
}
}