Bitboard Board-Definition

From Chessprogramming wiki
Jump to: navigation, search

Home * Board Representation * Bitboards * Bitboard Board-Definition

To represent the board we typically need one bitboard for each piece-type and color - likely encapsulated inside a class or structure, or as an array of bitboards as part of a position object. A one-bit inside a bitboard implies the existence of a piece of this piece-type on a certain square - one to one associated by the bit-position [1]:

Classical Board

Those bitboards may part of a central position object which is incrementally updated while making or unmaking moves.

Bitboard.gif

Structure

To be aware of their scalar 64-bit origin, we use so far a type defined unsigned integer U64 in our C/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.

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;
   ...
};

Array

For better generalization and to avoid branches, one may encapsulate arrays of bitboards. For instance, inside the Beowulf sources (sample from moves.c) one finds a lot of branches on side to move to either fetch white or black piece bitboards, as already criticized by Vincent Diepeveen in 2001 [2] ...

  switch (side) {
   case WHITE: tsq = B->whiteRooks; break;
   case BLACK: tsq = B->blackRooks; break;
  }

.. where an indexed access with appropriate defined {0,1} color range for the side to move would avoid those branches, per piece-kind, ...

  tsq = B->rooks[side];

... or over all piece-kinds, ...

  tsq = B->pieceBB[nWhiteRook + side];

... for instance, on x86 or x86-64, utilizing its addressing modes with base- and scalable index register, plus displacement:

   ; rsi pointer to structure, rcx side (0 == White, 1 == Black)
   mov  rax, qword ptr [rsi + rookOffset + 8*rcx] 

Likely one also keeps some often used redundant union sets like white and black pieces, occupancy or their complement, the empty squares.

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];}
   ...
};

On initialization and update of the bitboards, see general setwise operations.

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 union of black and white respective pieces, i.e. all queens. This space saving requires a cheap intersection of a color and a piece bitboard to get the required pieces of that color only.

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];}
   ...
};

See also

Forum Posts

External Links

lineup: Charlie Mariano, Jack Bruce, Jan Hammer, John Marshall, Nippy Noya, Zbigniew Seifert

References

Up one Level