Piece-Sets
Home * Board Representation * Piece-Sets
Piece-Sets,
a set-wise representation with one bit for each piece inside one 32-bit word or two 16-bit words for each side. Piece-sets have some similarities with bitboards, but each set bit does not directly associate a square, but an index inside a piece-list. Thus to get the square, one additional indirection is necessary. Often the bit-position of a piece-set directly implies the information, what type and color the piece is - while bitboards usually maintains distinct sets for different pieces. That has advantages for instance in static exchange evaluation, if one maintains an attack-set as incremental updated array or 64 piece-sets for each square.
Serialization
Techniques to traverse piece-sets are similar to bitboard serialization, but of course more 32-bit friendly. Same applies for general set-wise operations.
Move Generation
As proposed by Andrew Tridgell and used in KnightCap, piece-sets can be used to generate moves, as seen in the move generation code of Dorpsgek by Matthew R. Brades, with some code omitted:
/* Iterate over all squares */
for (dest = 0; dest < 64; dest++) {
/* Do we have any pieces attacking this square? */
if ((index = (b->bitlist[dest] & b->sidemask[b->side]))) {
/* Yes, we do, iterate over them. */
while (index) {
bit = BitScanForward(index); /* Retrieve index of lowest attacker. */
from = b->piecelist[bit]; /* Retrieve the square it is on. */
type = (b->board[dest] == INVALID) ? MoveTypeNormal : MoveTypeCapture; /* Check if capture */
index &= index - 1; /* Reset LSB */
/* Don't allow own-piece captures. */
if (type == MoveTypeCapture && ((1 << b->index[dest]) & b->sidemask[b->side])) {
continue;
}
/* Pawn related code */
if ((1 << bit) & b->piecemask[PAWN]) {
/* En-passant captures can move to nothing, so we avoid skipping them */
if (b->ep != INVALID && dest == b->ep) {
if ((b->side == WHITE && ROW(from) == 4) ||
(b->side == BLACK && ROW(from) == 3)) {
type = MoveTypeEnPassant;
}
}
/* Don't allow pawns to capture diagonally when there is nothing to capture. */
if (type == MoveTypeNormal) {
continue;
}
/* Captures with promotion */
if ((b->side == WHITE && ROW(from) == 6) ||
(b->side == BLACK && ROW(from) == 1)) {
AddMove(m, &movecount, from, dest, MoveTypePromotionKnight);
AddMove(m, &movecount, from, dest, MoveTypePromotionBishop);
AddMove(m, &movecount, from, dest, MoveTypePromotionRook);
AddMove(m, &movecount, from, dest, MoveTypePromotionQueen);
continue;
}
}
/* Add this move to the list and increment the pointer. */
AddMove(m, &movecount, from, dest, type);
}
}
}
See also
Forum Posts
- Re: Bit Board Bonkers?? - other alternatives by Andrew Tridgell, rgcc, August 9, 1997
- Nomenclature suggestion: Bit target programs by Steven Edwards, CCC, December 31, 2014
- PieceLists ? by Mahmoud Uthman, CCC, February 10, 2017
