25,161
edits
Changes
Created page with "'''Home * Board Representation * Piece-Sets''' FILE:IrvingAmenChessboard.jpg|border|right|thumb|link=http://www.irvingamen.com/works/Chessboard.htm|[[Arts..."
'''[[Main Page|Home]] * [[Board Representation]] * Piece-Sets'''
[[FILE:IrvingAmenChessboard.jpg|border|right|thumb|link=http://www.irvingamen.com/works/Chessboard.htm|[[Arts#Amen|Irving Amen]], Chess Board <ref>[http://www.irvingamen.com/woodcutChess.htm Woodcuts with a Chess Theme] by [[Arts#Amen|Irving Amen]]</ref> ]]
'''Piece-Sets''',<br/>
a set-wise representation with one bit for each [[Pieces|piece]] inside a [[Double Word|32-bit word]]. Piece-sets have some similarities with [[Bitboards|bitboards]], but each set bit does not directly associate a [[Squares|square]], but an index inside a [[Piece-Lists|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|static exchange evaluation]], if one maintains an [[Attack and Defend Maps|attack-set]] as [[Incremental Updates|incremental updated]] [[Array|array]] or 64 piece-sets for each square.
=Serialization=
Techniques to traverse piece-sets are similar to [[Bitboard Serialization|bitboard serialization]], but of course more 32-bit friendly. Same applies for [[General Setwise Operations|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:
<pre>
/* 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);
}
}
}
</pre>
=See also=
* [[Kim Walisch#Bitscan|32-bit BitScan]] by [[Kim Walisch]]
* [[Attack and Defend Maps]]
* [[Chest]]
* [[IsiChess]]
* [[KnightCap]]
* [[Piece-Lists]]
=Forum Posts=
* [https://groups.google.com/group/rec.games.chess.computer/msg/4d6c328e8e8e0cd4 Re: Bit Board Bonkers?? - other alternatives] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 9, 1997
* [http://www.talkchess.com/forum/viewtopic.php?t=54810 Nomenclature suggestion: Bit target programs] by [[Steven Edwards]], [[CCC]], December 31, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=63126 PieceLists ?] by [[Mahmoud Uthman]], [[CCC]], February 10, 2017
=References=
<references />
'''[[Board Representation|Up one Level]]'''
[[FILE:IrvingAmenChessboard.jpg|border|right|thumb|link=http://www.irvingamen.com/works/Chessboard.htm|[[Arts#Amen|Irving Amen]], Chess Board <ref>[http://www.irvingamen.com/woodcutChess.htm Woodcuts with a Chess Theme] by [[Arts#Amen|Irving Amen]]</ref> ]]
'''Piece-Sets''',<br/>
a set-wise representation with one bit for each [[Pieces|piece]] inside a [[Double Word|32-bit word]]. Piece-sets have some similarities with [[Bitboards|bitboards]], but each set bit does not directly associate a [[Squares|square]], but an index inside a [[Piece-Lists|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|static exchange evaluation]], if one maintains an [[Attack and Defend Maps|attack-set]] as [[Incremental Updates|incremental updated]] [[Array|array]] or 64 piece-sets for each square.
=Serialization=
Techniques to traverse piece-sets are similar to [[Bitboard Serialization|bitboard serialization]], but of course more 32-bit friendly. Same applies for [[General Setwise Operations|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:
<pre>
/* 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);
}
}
}
</pre>
=See also=
* [[Kim Walisch#Bitscan|32-bit BitScan]] by [[Kim Walisch]]
* [[Attack and Defend Maps]]
* [[Chest]]
* [[IsiChess]]
* [[KnightCap]]
* [[Piece-Lists]]
=Forum Posts=
* [https://groups.google.com/group/rec.games.chess.computer/msg/4d6c328e8e8e0cd4 Re: Bit Board Bonkers?? - other alternatives] by [[Andrew Tridgell]], [[Computer Chess Forums|rgcc]], August 9, 1997
* [http://www.talkchess.com/forum/viewtopic.php?t=54810 Nomenclature suggestion: Bit target programs] by [[Steven Edwards]], [[CCC]], December 31, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=63126 PieceLists ?] by [[Mahmoud Uthman]], [[CCC]], February 10, 2017
=References=
<references />
'''[[Board Representation|Up one Level]]'''
