Thought bitboards was faster :-)

[JohnWoe]

Perft is totally useless for chess engines.
1. Just play 1M games against SF.
2. grep for illegal moves.
3. If there's none then your movegen is good. Also makes your UCI code battle proof.

BitBoards not only speedup movegen. They also speedup everything else. Evaluation. Checks...

[hgm]

BitBoards not only speedup movegen. They also speedup everything else. Evaluation. Checks...

That is perhaps true when you use the most simplistic mailbox implementation as reference. But of course more advanced algorithms can enormously speed up mailbox too, and then it is not so clear at all.

[JohnWoe]

BitBoards not only speedup movegen. They also speedup everything else. Evaluation. Checks...

That is perhaps true when you use the most simplistic mailbox implementation as reference. But of course more advanced algorithms can enormously speed up mailbox too, and then it is not so clear at all.

That's true.
Mailbox algorithms can be very fast too.
I never really used mailbox. I jumped directly to bitboards. I have only used the 0x88 trick in Eucalyptus KPK generator. That's about it.

In Havoc I found piece lists slower than no piece lists. Removing and adding stuff to piece lists cost so much time. I might need to revisit them.

[hgm]

I suppose it depends on how you handle the capture of pieces. During search I usually do that through an invalid square number in their location field. That is fast, but the downside is that you have to test whether a piece is present before using it for whatever you want to do. And then I compactify the list in the root before every search. An alternative would be to make it a doubly-linked list, so that you can easily unlink a piece on capture, an re-insert it during UnMake. For games with piece drops like Crazyhouse I don't bother with a piece list at all, as you would have to make the list long enough to also contain all material captured from the opponent, so that a large fraction would typically be empty. Then you might as well scan the board for pieces, which is always quite crowded in such games. Of course you can use bit-extraction tricks on piece lists too, by setting a bit for each piece that is present in a separate word.

But I am not only thinking of a piece list, but also of techniques like a 'neighbor table', where you can look up at a glance which are the closest occupied squares in each of the 8 directions. It is not very expensive or complex to incrementally update that. And it is a great help for generating slider captures, as you don't have to do board scans anymore, but can directly look at the targets they attack.

Keeping track of all captures in an incrementally updated attack map (i.e. sorted by to-square) reduces the move-generation work to only doing it for the moved (and possibly captured) piece, and this only doesn't make capture generation very cheap, but also makes it trivial to generate the captures in MVV order, so that you get rid of a lot of sorting effort as well. And it is a great help in its own incremental updating, as it tells you directly which sliders attack a square that gets evacuated, and thus get their moves extended to a target downstream (as given by the neighbor table). And of course mobility comes out as a nearly free side effect of updating the attack map.

[Karlo Bala]

Bitboards are not automagically faster, but most often open up some possiblities for further optimizations.

For example, your function

Code: Select all

void set_bit(U64 *pbitboard, int y, int type)  
{
	U64 x = pbitboard[type];
		
	x = (BIT[y] | x);
	
	pbitboard[type] = x;	
}

could be simplified into

Code: Select all

   pbitboard[type] |= (U64)1 << y;

which would then benefit *hughley* from being inlined.

Also, in one place you have noticed that a queen has things in common with rooks and bishops:

Code: Select all

//fou
U64 mask_bishop[64];
U64 mask_b_no[64];
U64 mask_b_ne[64];
U64 mask_b_so[64];
U64 mask_b_se[64];
//tour
U64 mask_rook[64];
U64 mask_r_n[64];
U64 mask_r_s[64];
U64 mask_r_e[64];
U64 mask_r_o[64];
//dame = tour + fou

There are many other symmetries that can be used to reduce the number of bitbords stored. For example, if you have black pieces and white pieces stored, it is very easy to compute occupied or empty squares on demand.

By pushing this, I have reduced your 17 bitmaps into just 7:

Code: Select all

      // By piece-type

      BitBoard   Pieces[5];

      static constexpr auto Pawns = 0;
      static constexpr auto Kings = 1;
      static constexpr auto Knights = 2;
      static constexpr auto DiagSweepers = 3;
      static constexpr auto AngularSweepers = 4;

      // By color

      BitBoard   AllPieces[2];

      static constexpr auto Dark = 0;
      static constexpr auto Lite = 1;

and then use little helper functions like

Code: Select all

      // Positional board info

      inline BitBoard LitePieces() 
      { return AllPieces[Lite]; }

      inline BitBoard DarkPieces() 
      { return AllPieces[Dark]; }

      inline BitBoard Occupied() 
      { return LitePieces() | DarkPieces(); }

      inline BitBoard EmptySquares() 
      { return ~Occupied(); }

      // Pawns

      inline BitBoard LitePawns() 
      { return Pieces[Pawns] & LitePieces(); }

      inline BitBoard DarkPawns() 
      { return Pieces[Pawns] & DarkPieces(); }

Just curious,
how do you update those bitboards in make / unmake?
Do you have a large IF like in Crafty or do you use some extra piece_type to index the bitboards?

[emadsen]

Perft is totally useless for chess engines.
1. Just play 1M games against SF.
2. grep for illegal moves.
3. If there's none then your movegen is good. Also makes your UCI code battle proof.

This technique doesn't find the absence of a legal move. That's where perft is valuable.

I'm just arguing the movegen within perft should be the same movegen when playing games, to give confidence correct perft results indicate the search examines all moves. Well, excepting pruning. But with identical movegen we know all moves are generated and run through the pruning logic.

[Daniel Anulliero]

Bitboards are not automagically faster, but most often open up some possiblities for further optimizations.

For example, your function

Code: Select all

void set_bit(U64 *pbitboard, int y, int type)  
{
	U64 x = pbitboard[type];
		
	x = (BIT[y] | x);
	
	pbitboard[type] = x;	
}

could be simplified into

Code: Select all

   pbitboard[type] |= (U64)1 << y;

which would then benefit *hughley* from being inlined.

Also, in one place you have noticed that a queen has things in common with rooks and bishops:

Code: Select all

//fou
U64 mask_bishop[64];
U64 mask_b_no[64];
U64 mask_b_ne[64];
U64 mask_b_so[64];
U64 mask_b_se[64];
//tour
U64 mask_rook[64];
U64 mask_r_n[64];
U64 mask_r_s[64];
U64 mask_r_e[64];
U64 mask_r_o[64];
//dame = tour + fou

There are many other symmetries that can be used to reduce the number of bitbords stored. For example, if you have black pieces and white pieces stored, it is very easy to compute occupied or empty squares on demand.

By pushing this, I have reduced your 17 bitmaps into just 7:

Code: Select all

      // By piece-type

      BitBoard   Pieces[5];

      static constexpr auto Pawns = 0;
      static constexpr auto Kings = 1;
      static constexpr auto Knights = 2;
      static constexpr auto DiagSweepers = 3;
      static constexpr auto AngularSweepers = 4;

      // By color

      BitBoard   AllPieces[2];

      static constexpr auto Dark = 0;
      static constexpr auto Lite = 1;

and then use little helper functions like

Code: Select all

      // Positional board info

      inline BitBoard LitePieces() 
      { return AllPieces[Lite]; }

      inline BitBoard DarkPieces() 
      { return AllPieces[Dark]; }

      inline BitBoard Occupied() 
      { return LitePieces() | DarkPieces(); }

      inline BitBoard EmptySquares() 
      { return ~Occupied(); }

      // Pawns

      inline BitBoard LitePawns() 
      { return Pieces[Pawns] & LitePieces(); }

      inline BitBoard DarkPawns() 
      { return Pieces[Pawns] & DarkPieces(); }

Just curious,
how do you update those bitboards in make / unmake?
Do you have a large IF like in Crafty or do you use some extra piece_type to index the bitboards?

In the two functions in move.c

Code: Select all

//fill a square 'sq' whith a piece 'p' of color 'c'
void fill_sq(int c, int sq, int p)
{
	//update hash code
	hash_position ^= hash_table[p][sq];

	//update position
	echiquier[sq] = p;

	//bitboardS
	set_bit(bb, sq, ALP);
	clear_bit(bb, sq, NOP);
	if(c == BLANC)
	{
		set_bit(bb, sq, WPC);
		set_bit(bb, sq, p);
	}
	else
	{
		set_bit(bb, sq, BPC);
		set_bit(bb, sq, p);
	}
}

//remove a piece 'p' of color 'c' from square 'sq'
void clear_sq(int c, int sq, int p)
{
	//update hash code
	hash_position ^= hash_table[p][sq];

	//update position
	echiquier[sq] = VIDE;

	//bitboards
	clear_bit(bb, sq, ALP);
	set_bit(bb, sq, NOP);

	if(c == BLANC)
	{
		clear_bit(bb, sq, WPC);
		clear_bit(bb, sq, p);
	}
	else
	{
		clear_bit(bb, sq, BPC);
		clear_bit(bb, sq, p);
	}
}

with these two functions in bitboard.c

Code: Select all

//put a bit to '1' in a bitboard
//*pbitboard  bb[] array
//y = the square
//type = bitboard to modify (bb[] array
void set_bit(U64 *pbitboard, int y, int type)  
{
	U64 x = pbitboard[type];
		
	x = (BIT[y] | x);
	
	pbitboard[type] = x;	
}

//put a bit to '0' in a bitboard 
void clear_bit(U64 *pbitboard, int y, int type)
{
	U64 x = pbitboard[type];
	
	x = (x ^ BIT[y]);
	
	pbitboard[type] = x;	
}

[Karlo Bala]

In the two functions in move.c

Code: Select all

//fill a square 'sq' whith a piece 'p' of color 'c'
void fill_sq(int c, int sq, int p)
{
	//update hash code
	hash_position ^= hash_table[p][sq];

	//update position
	echiquier[sq] = p;

	//bitboardS
	set_bit(bb, sq, ALP);
	clear_bit(bb, sq, NOP);
	if(c == BLANC)
	{
		set_bit(bb, sq, WPC);
		set_bit(bb, sq, p);
	}
	else
	{
		set_bit(bb, sq, BPC);
		set_bit(bb, sq, p);
	}
}

//remove a piece 'p' of color 'c' from square 'sq'
void clear_sq(int c, int sq, int p)
{
	//update hash code
	hash_position ^= hash_table[p][sq];

	//update position
	echiquier[sq] = VIDE;

	//bitboards
	clear_bit(bb, sq, ALP);
	set_bit(bb, sq, NOP);

	if(c == BLANC)
	{
		clear_bit(bb, sq, WPC);
		clear_bit(bb, sq, p);
	}
	else
	{
		clear_bit(bb, sq, BPC);
		clear_bit(bb, sq, p);
	}
}

with these two functions in bitboard.c

Code: Select all

//put a bit to '1' in a bitboard
//*pbitboard  bb[] array
//y = the square
//type = bitboard to modify (bb[] array
void set_bit(U64 *pbitboard, int y, int type)  
{
	U64 x = pbitboard[type];
		
	x = (BIT[y] | x);
	
	pbitboard[type] = x;	
}

//put a bit to '0' in a bitboard 
void clear_bit(U64 *pbitboard, int y, int type)
{
	U64 x = pbitboard[type];
	
	x = (x ^ BIT[y]);
	
	pbitboard[type] = x;	
}

Thanks Daniel,
the question was mostly for Bo Persson since he combines queens/rooks and queens/bishops into the same bitboard.
I do what I suppose is the standard way. "m_piececode" is a hash for all pieces including pawns, "m_pawncode" is a hash only for pawns, and "m_matcode" is a material key.

Code: Select all

void PutPiece(PIECECOLOR color, PIECE piece, SQUARE square)
{
	m_pieces[square] = piece;
	m_colorbb[color].Set(square);
	m_piecebb[piece].Set(square);
	m_piececode ^= PieceCode(piece, square);
	if (piece >= WPAWN)
		m_pawncode ^= PieceCode(piece, square);
	m_matcode.AddPiece(piece);
}

void RemovePiece(PIECECOLOR color, PIECE piece, SQUARE square)
{
	m_pieces[square] = NOPIECE;
	m_colorbb[color].Clear(square);
	m_piecebb[piece].Clear(square);
	m_piececode ^= PieceCode(piece, square);
	if (piece >= WPAWN)
		m_pawncode ^= PieceCode(piece, square);
	m_matcode.RemovePiece(piece);
}

void MovePiece(PIECECOLOR color, PIECE	piece, SQUARE	from, SQUARE to)
{
	m_pieces[from] = NOPIECE;
	m_pieces[to] = piece;
	m_colorbb[color].Clear(from);
	m_colorbb[color].Set(to);
	m_piecebb[piece].Clear(from);
	m_piecebb[piece].Set(to);
	m_piececode ^= PieceCode(piece, from);
	m_piececode ^= PieceCode(piece, to);
	if (piece >= WPAWN)
	{
		m_pawncode ^= PieceCode(piece, from);
		m_pawncode ^= PieceCode(piece, to);
	}
}

[Bo Persson]

By pushing this, I have reduced your 17 bitmaps into just 7:

Code: Select all

      // By piece-type

      BitBoard   Pieces[5];

      static constexpr auto Pawns = 0;
      static constexpr auto Kings = 1;
      static constexpr auto Knights = 2;
      static constexpr auto DiagSweepers = 3;
      static constexpr auto AngularSweepers = 4;

      // By color

      BitBoard   AllPieces[2];

      static constexpr auto Dark = 0;
      static constexpr auto Lite = 1;

and then use little helper functions like

Code: Select all

      // Positional board info

      inline BitBoard LitePieces() 
      { return AllPieces[Lite]; }

      inline BitBoard DarkPieces() 
      { return AllPieces[Dark]; }

      inline BitBoard Occupied() 
      { return LitePieces() | DarkPieces(); }

      inline BitBoard EmptySquares() 
      { return ~Occupied(); }

      // Pawns

      inline BitBoard LitePawns() 
      { return Pieces[Pawns] & LitePieces(); }

      inline BitBoard DarkPawns() 
      { return Pieces[Pawns] & DarkPieces(); }

Just curious,
how do you update those bitboards in make / unmake?
Do you have a large IF like in Crafty or do you use some extra piece_type to index the bitboards?

I have chosen the piece values so that they are easily transformed into the proper array index:

Code: Select all

   class Piece
   {
      // Internal types

      using value_type = std::uint8_t;

      // Possible values

   public:
      enum Literal : value_type
      {
         DarkPawn   = 0,  LitePawn   = 1,
         DarkKing   = 2,  LiteKing   = 3,
         DarkKnight = 4,  LiteKnight = 5,
         DarkBishop = 6,  LiteBishop = 7,
         DarkRook   = 8,  LiteRook   = 9,
         DarkQueen  = 10, LiteQueen  = 11,
      };

   //etc
   
   };

The low bit is the piece color, and value >> 1 is the array index.

We then only need one if-statement for queens, which are placed into two bitmaps (being both like a rook and like a bishop).

Code: Select all

   constexpr void BitMappedBoard::PlacePiece(Piece ThePiece, Square TheSquare) noexcept
   {
      if (ThePiece.IsQueen())
      {
         Pieces[DiagSweepers].Include(TheSquare);
         Pieces[AngularSweepers].Include(TheSquare);
      }
      else
      {
         Pieces[ThePiece.Base()].Include(TheSquare);
      }

      AllPieces[ThePiece.IsLite()].Include(TheSquare);
   }