Home * Board Representation * Piece-Sets

		Piece-Sets, a set-wise representation with one bit for each piece inside a 32-bit word. 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.
Irving Amen, Chess Board [1]

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

• 32-bit BitScan by Kim Walisch
• Attack and Defend Maps
• Chest
• IsiChess
• KnightCap
• Piece-Lists

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

References

1. ^ Woodcuts with a Chess Theme by Irving Amen

What links here?

Up one Level