Are Bitboards More Intoxicating Than They Are Good?

[JeremiahK]

In some of your code snippets I've looked at I remember seeing lots of "if" statements. In my code there are very few if statements. For example in my make and unmake move routines there is not a single "if" statement and only one switch statement each. In all my pawn move generation and make/unmake there is not a single "if" statement.

...

If statements are the bane of high performance. Mispredictions are expensive. The more "if" statements there are the easier it is to overflow the branch prediction tables. And the constantly changing state of a chess engine makes for a high prediction fail rate.

...

With regard to if-statements... if you think my code has a lot of then, you should look at some other engines. My engine uses if and switch statements sparingly, compared to what I normally see.

There is something like branchless programming. One day I'll have to look into this to see if there are places in my engine where I can use that.

This is my first post on these forums. I recently started working on my first engine in C++, which can currently only hold and print out the board state, nothing else. I am slowly adding one thing at a time, being careful to really think each step through. I decided to go with bitboards, since I have experience working with 6502 assembly (which is entirely different, but requires a LOT of bit wrangling and unconventional "tricks"). I am keeping some redundant mailboxes as well, since it doesn't add much overhead and might save time making certain calculations, and I can easily remove them if I want.

I have a get_mail() function which updates the mailboxes (white/black) to line up with the bitboards, and my first rough implementation used a simple algorithm with many IF statements:

Code: Select all

void position::get_mail ()
{
	uint64_t mask = force64(1);

	for (int i = 0; i < 64; ++i, mask = mask << 1)
	{
		// check for case of no piece at mask position
		if (((white | black) & mask) == 0)
		{
			whitemail[i] = blackmail[i] = EMPTY;
			continue;
		}

		// mail = pointer to blackmail or whitemail, depending on piece color
		PIECE* mail = whitemail;
		if (black & mask) mail = blackmail;

		if	(king & mask)	*(mail + i) = KING;
		else if	(queen & mask)	*(mail + i) = QUEEN;
		else if	(rook & mask)	*(mail + i) = ROOK;
		else if	(bishop & mask)	*(mail + i) = BISHOP;
		else if	(knight & mask)	*(mail + i) = KNIGHT;
		else			*(mail + i) = PAWN;
	}

	return;
}

After reading this thread, I realized there was a better method using my newly added reverse bitscan and clear function, bitpullr():

Code: Select all

void position::get_mail ()
{
	// first clear both mailboxes, setting to EMPTY
	for (int i = 0; i < 64; ++i) whitemail[i] = blackmail[i] = EMPTY;

	// then loop through and set each type of piece + color seperately
	bitboard piecemask;

	piecemask.bb = white & pawn.bb;
	while (piecemask.bb) whitemail[piecemask.bitpullr()] = PAWN;
	piecemask.bb = black & pawn.bb;
	while (piecemask.bb) blackmail[piecemask.bitpullr()] = PAWN;

	piecemask.bb = white & knight.bb;
	while (piecemask.bb) whitemail[piecemask.bitpullr()] = KNIGHT;
	piecemask.bb = black & knight.bb;
	while (piecemask.bb) blackmail[piecemask.bitpullr()] = KNIGHT;

	piecemask.bb = white & bishop.bb;
	while (piecemask.bb) whitemail[piecemask.bitpullr()] = BISHOP;
	piecemask.bb = black & bishop.bb;
	while (piecemask.bb) blackmail[piecemask.bitpullr()] = BISHOP;

	piecemask.bb = white & rook.bb;
	while (piecemask.bb) whitemail[piecemask.bitpullr()] = ROOK;
	piecemask.bb = black & rook.bb;
	while (piecemask.bb) blackmail[piecemask.bitpullr()] = ROOK;

	piecemask.bb = white & queen.bb;
	while (piecemask.bb) whitemail[piecemask.bitpullr()] = QUEEN;
	piecemask.bb = black & queen.bb;
	while (piecemask.bb) blackmail[piecemask.bitpullr()] = QUEEN;

	piecemask.bb = white & king.bb;
	while (piecemask.bb) whitemail[piecemask.bitpullr()] = KING;
	piecemask.bb = black & king.bb;
	while (piecemask.bb) blackmail[piecemask.bitpullr()] = KING;

	return;
}

This version may look "ugly" compared to the first, but it is twice as fast. Of course, updating the mailboxes will only use a very small percentage of computing time, so the actual savings is minimal, but it should help me going forward with more critical parts of the code, and I thought it was a good example of how re-thinking your approach can make a huge difference.

[hgm]

Indeed, bitscan methods can be much faster than loops over all bits. What I don't understand is why you would want to do this with any significant frequency. (I can imagine you would do it in the FEN reader for setting up a new position.) Even the twice faster codes loops over 2 x 64 squares to set them to empty (although a smart compiler could reduce this to 2 x 8 64-bit stores if the mailbox elements are bytes), and eventually has to extract 32 pieces, in a fully populated position. So it seems to me that saving a factor 2 is is no reason for celebration, and a factor 20-30 would be about right.

When bitboard engines keep a redundant mailbox board, they usually update it incrementally, together with the bitboard. Just do

whitemail[toSqr] = whitemail[fromSqr];
whitemail[fromSqr] = 0;
blackmail[toSqr] = 0;

They wouldn't recreate the mailbox board from the bitboard game state from scratch. And why would you want to use separate mailbox boards for the white and the black pieces? There will never be two pieces on the same square (in orthodox Chess, at least), so you could have put them on the same board.

[JeremiahK]

I neglected to mention that indeed this function would likely only be run once at the start, with very simple ways to change the board while making / unmaking moves. So yes, in the big picture, it doesn't really matter how long this specific task takes, since it will only run once. As I said, this is my first engine, so I'm not 100% sure which mailboxes would be best to keep track of, if any at all. I know this exact code is maybe not well fitted for use in a full engine, but I don't have that yet, so I can easily change it as I go.

I wasn't trying to make a case for bitboards > mailbox. It was only an example (albeit not a very useful one) of how specific tasks might be simpler in one method, or faster in another. Applied to a more useful task, like finding checks, pinned pieces, etc. such a speedup could be huge, and it applies to both bitboards and mailboxes. The main idea is that many times the problem may not be a bitboard vs mailbox one, but an algorithmic one. Taking a step back and asking yourself, "How can I do this better?" can help you find ideas you never would have otherwise.

[hgm]

That is true, and it is exactly what the thread about the 'mailbox trials' that I started is about: trying to find new algorithms that do equivalent tasks faster. Adapting the data structures to fit the algorithm best.

[JeremiahK]

Excellent, I'll run a search and check that out.

Edit: lol very recent I see, must have missed it somehow.

[mvanthoor]

Indeed, bitscan methods can be much faster than loops over all bits. What I don't understand is why you would want to do this with any significant frequency. (I can imagine you would do it in the FEN reader for setting up a new position.)

Obviously, you shouldn't loop over bitboards, because if you do, you're doing no better than a piece/square-iterator engine. The only time where you have to loop over a bitboard, is when you have to do something with each individual bit, and the thing you have to do can be different each time. One of the cases you mention is setting up pieces. You have to extract each square from the bitboard, one by one so you can handle the specific piece on the specific square.

[Karlo Bala]

Indeed, bitscan methods can be much faster than loops over all bits. What I don't understand is why you would want to do this with any significant frequency. (I can imagine you would do it in the FEN reader for setting up a new position.) Even the twice faster codes loops over 2 x 64 squares to set them to empty (although a smart compiler could reduce this to 2 x 8 64-bit stores if the mailbox elements are bytes), and eventually has to extract 32 pieces, in a fully populated position. So it seems to me that saving a factor 2 is is no reason for celebration, and a factor 20-30 would be about right.

When bitboard engines keep a redundant mailbox board, they usually update it incrementally, together with the bitboard. Just do

whitemail[toSqr] = whitemail[fromSqr];
whitemail[fromSqr] = 0;
blackmail[toSqr] = 0;

They wouldn't recreate the mailbox board from the bitboard game state from scratch. And why would you want to use separate mailbox boards for the white and the black pieces? There will never be two pieces on the same square (in orthodox Chess, at least), so you could have put them on the same board.

Why do you think that mailbox is redundant in a bitboard engine?

[hgm]

Because the game state is already uniquely defined by the bitboard representation. I did nort mean to say that it would be useless to have a mailbox next to the bitboard. The same could be said from a piece list in a mailbox engine; it is redundant as far as defining the game state is concerned, but can give you a nice speedup despite the overhead it takes to maintain it.

[mvanthoor]

Because the game state is already uniquely defined by the bitboard representation. I did nort mean to say that it would be useless to have a mailbox next to the bitboard. The same could be said from a piece list in a mailbox engine; it is redundant as far as defining the game state is concerned, but can give you a nice speedup despite the overhead it takes to maintain it.

As I posted before, having a piece list / board mailbox right next to the bitboards can be very useful. When capturing a piece, I'd previously needed to loop over 6 bitboards, and then see if one of them had the specific to_square set, to find which piece the move actually captured. By using the piece list (which you called a board mailbox, which is probably more accurate; I'll possibly rename it "piece_type", because that is what it holds), this information can be queried by "piece_type[to_square]". Maintaining this piece_type array when moving a piece, is much faster than constantly looping over the 6 bitboards and extracting squares.

[hgm]

Indeed, mailbox boards hold piece types or piece numbers. The reason you want a board that holds types is exactly the same as the reason why a design that uses a piece list wants to keep a mailbox board with piece numbers (rather than types): otherwise, when you see a move captures a piece, you would have to loop over all pieces of that type in the piece list, to know which one you captured (to delete it from the list). Which would not even be so bad if there are only two pieces of that type, but is a bit annoying for Pawns.

In fact the conventional bitboard representation could be described as a piece-type list, as each element indicates the position of all pieces of a given type. So you can combine it with a piece-type (mailbox) board. When you have a true piece list (i.e. indexed by piece number), you need to combine it with mailbox board containing piece numbers. Basically these are all examples of bidirectional linking corresponding elements, so they can be deleted in pairs.

Redundancy can be very useful. The 'occupied', 'white' and 'black' bitboards are also redundant: they could be obtained by ORing all piece-type bitboards together.