Piece-Sets

From Chessprogramming wiki
Jump to: navigation, search

Home * Board Representation * Piece-Sets

Irving Amen - Chess Board [1]

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

References

Up one Level