25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Bitboard Board-Definition''' To represent the board we typically need one bitboard for each Pieces#PieceT..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Bitboard Board-Definition'''
To represent the board we typically need one bitboard for each [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] - likely encapsulated inside a class or structure, or as an [[Array|array]] of bitboards as part of a [[Chess Position|position]] object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain [[Squares|square]] - one to one associated by the bit-position <ref>[http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond] by [[Glen Pepicelli]], 2005, [https://en.wikipedia.org/wiki/O%27Reilly_Media O'Reilly's] [http://onjava.com/ OnJava.com]</ref>:
<span id="CBoardDef"></span>
=Classical Board=
Those bitboards may part of a central position object which is [[Incremental Updates|incrementally updated]] while [[Make Move|making]] or [[Unmake Move|unmaking]] [[Moves|moves]].
[[FILE:bitboard.gif|none|border|text-bottom|link=http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html?page=2]]
==Structure==
''To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our [[C]]/[[Cpp|C++]] source snippets, the scalar 64-bit long in [[Java]]. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time.''
<pre>
class CBoard
{
U64 whitePawns;
U64 whiteKnights;
U64 whiteBishops;
U64 whiteRooks;
U64 whiteQueens;
U64 whiteKing;
U64 blackPawns;
U64 blackKnights;
U64 blackBishops;
U64 blackRooks;
U64 blackQueens;
U64 blackKing;
...
};
</pre>
==Array==
For better generalization and to [[Avoiding Branches|avoid branches]], one may encapsulate [[Array|arrays]] of bitboards. For instance, inside the [[Beowulf]] sources (sample from moves.c) one finds a lot of branches on [[Side to move|side to move]] to either fetch white or black piece bitboards, as already criticized by [[Vincent Diepeveen]] in 2001 <ref>[https://www.stmintz.com/ccc/index.php?id=173418 On Beowulf - long post] by [[Vincent Diepeveen]], [[CCC]], April 04, 2001</ref> ...
<pre>
switch (side) {
case WHITE: tsq = B->whiteRooks; break;
case BLACK: tsq = B->blackRooks; break;
}
</pre>
.. where an indexed access with appropriate defined {0,1} color range for the side to move would avoid those branches, per piece-kind, ...
<pre>
tsq = B->rooks[side];
</pre>
... or over all piece-kinds, ...
<pre>
tsq = B->pieceBB[nWhiteRook + side];
</pre>
... for instance, on [[x86]] or [[x86-64]], utilizing its [https://en.wikipedia.org/wiki/X86#Addressing_modes addressing modes] with base- and scalable [https://en.wikipedia.org/wiki/Index_register index register], plus displacement:
<pre>
; rsi pointer to structure, rcx side (0 == White, 1 == Black)
mov rax, qword ptr [rsi + rookOffset + 8*rcx]
</pre>
<span id="Occupancy"></span>
Likely one also keeps some often used redundant [[General Setwise Operations#Union|union]] sets like white and black pieces, [[Occupancy|occupancy]] or their complement, the empty squares.
<pre>
class CBoard
{
U64 pieceBB[14];
U64 emptyBB;
U64 occupiedBB;
...
public:
enum enumPiece
{
nWhite, // any white piece
nBlack, // any black piece
nWhitePawn, // white Pawn
nBlackPawn, // white Pawn
...
};
U64 getPieceSet(PieceType pt) const {return pieceBB[pt];}
U64 getWhitePawns() const {return pieceBB[nWhitePawn];}
...
U64 getPawns(ColorType ct) const {return pieceBB[nWhitePawn + ct];}
...
};
</pre>
On initialization and update of the bitboards, see [[General Setwise Operations#UpdateByMove|general setwise operations]].
<span id="SixTwo"></span>
=Denser Board=
A common alternative to reduce the size of the board structure is to keep two color bitboards and six color independent piece bitboards, which are the [[General Setwise Operations#Union|union]] of black and white respective pieces, i.e. all queens. This space saving requires a cheap [[General Setwise Operations#Intersection|intersection]] of a color and a piece bitboard to get the required pieces of that color only.
<pre>
class CBoard
{
U64 pieceBB[8];
public:
enum enumPiece
{
nWhite, // any white piece
nBlack, // any black piece
nPawn,
nKnight,
nBishop,
nRook,
nQueen,
nKing
};
U64 getPieceSet(PieceType pt) const {return pieceBB[pieceCode(pt)] & pieceBB[colorCode(pt)];}
U64 getWhitePawns() const {return pieceBB[nPawn] & pieceBB[nWhite];}
...
U64 getPawns(ColorType ct) const {return pieceBB[nPawn] & pieceBB[ct];}
...
};
</pre>
=See also=
* [[Color Flipping]]
* [[Quad-Bitboards]]
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/834fa3c273fafffe/cab7c12ea99e9a35 Bit Board Bonkers??] by Dave, [[Computer Chess Forums|rec.games.chess.computer]], July 28, 1997
* [https://www.stmintz.com/ccc/index.php?id=405590 Bitboard board representation] by [[Eric Oldre]], [[CCC]], January 13, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=17138 BitBoard representations of the board] by [[Uri Blass]], [[CCC]], October 14, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=47917 Decision concerning board representation] by [[Piotr Lopusiewicz]], [[CCC]], May 05, 2013
=References=
<references />
'''[[Bitboards|Up one Level]]'''
To represent the board we typically need one bitboard for each [[Pieces#PieceTypeCoding|piece-type]] and [[Color|color]] - likely encapsulated inside a class or structure, or as an [[Array|array]] of bitboards as part of a [[Chess Position|position]] object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain [[Squares|square]] - one to one associated by the bit-position <ref>[http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html Bitwise Optimization in Java: Bitfields, Bitboards, and Beyond] by [[Glen Pepicelli]], 2005, [https://en.wikipedia.org/wiki/O%27Reilly_Media O'Reilly's] [http://onjava.com/ OnJava.com]</ref>:
<span id="CBoardDef"></span>
=Classical Board=
Those bitboards may part of a central position object which is [[Incremental Updates|incrementally updated]] while [[Make Move|making]] or [[Unmake Move|unmaking]] [[Moves|moves]].
[[FILE:bitboard.gif|none|border|text-bottom|link=http://www.onjava.com/pub/a/onjava/2005/02/02/bitsets.html?page=2]]
==Structure==
''To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our [[C]]/[[Cpp|C++]] source snippets, the scalar 64-bit long in [[Java]]. Feel free to define a distinct type or wrap U64 into classes for better abstraction and type-safety during compile time.''
<pre>
class CBoard
{
U64 whitePawns;
U64 whiteKnights;
U64 whiteBishops;
U64 whiteRooks;
U64 whiteQueens;
U64 whiteKing;
U64 blackPawns;
U64 blackKnights;
U64 blackBishops;
U64 blackRooks;
U64 blackQueens;
U64 blackKing;
...
};
</pre>
==Array==
For better generalization and to [[Avoiding Branches|avoid branches]], one may encapsulate [[Array|arrays]] of bitboards. For instance, inside the [[Beowulf]] sources (sample from moves.c) one finds a lot of branches on [[Side to move|side to move]] to either fetch white or black piece bitboards, as already criticized by [[Vincent Diepeveen]] in 2001 <ref>[https://www.stmintz.com/ccc/index.php?id=173418 On Beowulf - long post] by [[Vincent Diepeveen]], [[CCC]], April 04, 2001</ref> ...
<pre>
switch (side) {
case WHITE: tsq = B->whiteRooks; break;
case BLACK: tsq = B->blackRooks; break;
}
</pre>
.. where an indexed access with appropriate defined {0,1} color range for the side to move would avoid those branches, per piece-kind, ...
<pre>
tsq = B->rooks[side];
</pre>
... or over all piece-kinds, ...
<pre>
tsq = B->pieceBB[nWhiteRook + side];
</pre>
... for instance, on [[x86]] or [[x86-64]], utilizing its [https://en.wikipedia.org/wiki/X86#Addressing_modes addressing modes] with base- and scalable [https://en.wikipedia.org/wiki/Index_register index register], plus displacement:
<pre>
; rsi pointer to structure, rcx side (0 == White, 1 == Black)
mov rax, qword ptr [rsi + rookOffset + 8*rcx]
</pre>
<span id="Occupancy"></span>
Likely one also keeps some often used redundant [[General Setwise Operations#Union|union]] sets like white and black pieces, [[Occupancy|occupancy]] or their complement, the empty squares.
<pre>
class CBoard
{
U64 pieceBB[14];
U64 emptyBB;
U64 occupiedBB;
...
public:
enum enumPiece
{
nWhite, // any white piece
nBlack, // any black piece
nWhitePawn, // white Pawn
nBlackPawn, // white Pawn
...
};
U64 getPieceSet(PieceType pt) const {return pieceBB[pt];}
U64 getWhitePawns() const {return pieceBB[nWhitePawn];}
...
U64 getPawns(ColorType ct) const {return pieceBB[nWhitePawn + ct];}
...
};
</pre>
On initialization and update of the bitboards, see [[General Setwise Operations#UpdateByMove|general setwise operations]].
<span id="SixTwo"></span>
=Denser Board=
A common alternative to reduce the size of the board structure is to keep two color bitboards and six color independent piece bitboards, which are the [[General Setwise Operations#Union|union]] of black and white respective pieces, i.e. all queens. This space saving requires a cheap [[General Setwise Operations#Intersection|intersection]] of a color and a piece bitboard to get the required pieces of that color only.
<pre>
class CBoard
{
U64 pieceBB[8];
public:
enum enumPiece
{
nWhite, // any white piece
nBlack, // any black piece
nPawn,
nKnight,
nBishop,
nRook,
nQueen,
nKing
};
U64 getPieceSet(PieceType pt) const {return pieceBB[pieceCode(pt)] & pieceBB[colorCode(pt)];}
U64 getWhitePawns() const {return pieceBB[nPawn] & pieceBB[nWhite];}
...
U64 getPawns(ColorType ct) const {return pieceBB[nPawn] & pieceBB[ct];}
...
};
</pre>
=See also=
* [[Color Flipping]]
* [[Quad-Bitboards]]
=Forum Posts=
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/834fa3c273fafffe/cab7c12ea99e9a35 Bit Board Bonkers??] by Dave, [[Computer Chess Forums|rec.games.chess.computer]], July 28, 1997
* [https://www.stmintz.com/ccc/index.php?id=405590 Bitboard board representation] by [[Eric Oldre]], [[CCC]], January 13, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=17138 BitBoard representations of the board] by [[Uri Blass]], [[CCC]], October 14, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=47917 Decision concerning board representation] by [[Piotr Lopusiewicz]], [[CCC]], May 05, 2013
=References=
<references />
'''[[Bitboards|Up one Level]]'''
