Winboard Forum

Hi all,

I am once again experimenting with bitboards. I have made numerous private rotated bitboard versions of Glaurung over the last year, but they were always slower and less compact than my mailbox versions (even on the 64-bit G5 CPU). The reason is almost certainly that I haven't learnt all the tricks yet. As others have demonstrated, it is definitely possible to write blazingly fast bitboard programs.

Right now, I am thinking about the following problem: What is the best way to obtain a bitboard of all passed pawns for one side? The obvious way is to loop through all pawns and check each pawn individually, but this is very slow. It seems that the key to making bitboards fast is to avoid having too many loops through the nonzero bits of a bitboard.

I am not interested in solutions involving assembly language. If possible, I would prefer to use code which works for both colours, rather than separate code for black and white pawns.

Tord

What did you convince that bitboard programs would be the fastest ?

Reinhard.

Tord Romstad wrote:Right now, I am thinking about the following problem: What is the best way to obtain a bitboard of all passed pawns for one side? The obvious way is to loop through all pawns and check each pawn individually, but this is very slow. It seems that the key to making bitboards fast is to avoid having too many loops through the nonzero bits of a bitboard.

I still loop thru all the pawns, but if needed this part can be moved into the pawn structure hash table so later you only have to scan the list of passed pawns, which is much shorter.

Tord Romstad wrote:I am not interested in solutions involving assembly language. If possible, I would prefer to use code which works for both colours, rather than separate code for black and white pawns.

No assembly needed... I think Gerd's routines are more than fast enough!

Reinhard Scharnagl wrote:What did you convince that bitboard programs would be the fastest ?

I am not convinced about anything. I constantly experiment with new tricks and techniques, mixing ideas of my own with those of others. Usually I end up not using most of the stuff I try, but this doesn't mean that it is a waste of time. My goal is to learn more, and sometimes I can learn as much from unsuccessful experiments as from successful.

At the moment, I want to improve my understanding of bitboards. I am not claiming that they are better or worse than any alternative data structures.

Tord

Alessandro Scotti wrote:

Tord Romstad wrote:Right now, I am thinking about the following problem: What is the best way to obtain a bitboard of all passed pawns for one side? The obvious way is to loop through all pawns and check each pawn individually, but this is very slow. It seems that the key to making bitboards fast is to avoid having too many loops through the nonzero bits of a bitboard.

I still loop thru all the pawns, but if needed this part can be moved into the pawn structure hash table so later you only have to scan the list of passed pawns, which is much shorter.

That would work, but I am considering to drop the pawn hash table altogether. Some of the bitboard experts claim that bitboards make pawn structure evaluation so fast that there is no need for a pawn hash table.

Tord Romstad wrote:I am not interested in solutions involving assembly language. If possible, I would prefer to use code which works for both colours, rather than separate code for black and white pawns.

No assembly needed... I think Gerd's routines are more than fast enough!

Where do I find Gerd's routines for this?

Tord

Hi Tord,

You can itarate trought each pawn of the side to move and to check if it is passed you AND the opponent pawns bitboard with a special bitboard (pre calculated once for each(64) squares) with bits setted on every squares in front of the pawn on the same column and the columns on its left and right.

As an example for d5 this bitboard would look like this :

Code: Select all

0 0 1 1 1 0 0 0
0 0 1 1 1 0 0 0
0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

In reality what you test is : "Is there an opponent paws in front of my pawn or an opponent pawn that could take my pawn."

This is done in only one AND, but you still have to iterate trough the pawns of the side to move.

mathmoi wrote:This is done in only one AND, but you still have to iterate trough the pawns of the side to move.

Yes, and that is precisely what I want to avoid. It goes against the central philosophy of bitboards: Operating with sets of squares rather than with individual squares. Looping through the nonzero bits of a bitboard is much slower than looping through a piece list. Eliminating bitscans whenever possible seems to be the way to go to make bitboards fast.

Tord

My engine (and I think most of bitboard programs) don't use only bitboards but hybrid solutions. Beside bitboards I have also lists of pieces. So I don't have to scan trough entire bitboard to find pawns. Using the list of pawns and bitboards you can check for free pawns pretty fast.

Tord Romstad wrote:Right now, I am thinking about the following problem: What is the best way to obtain a bitboard of all passed pawns for one side? The obvious way is to loop through all pawns and check each pawn individually, but this is very slow. It seems that the key to making bitboards fast is to avoid having too many loops through the nonzero bits of a bitboard.

I don't think it's such a bad thing to do the loop because you can evaluate other things at the same time. But if I really had to avoid the loop I guess I'd do something like this:

Code: Select all

/*
 * This code computes a bitmask of passed white pawns
 */

U64 mask, passedPawns;

/* generate black's one square pawn moves */
mask = genPawnMoves(BLACK);

/* Duplicate the mask and move it down. This is done three times
    to make sure the mask reaches the bottom of the board */
mask |= mask << 8;
mask |= mask << 16;
mask |= mask << 32;

/* get white's passed pawn mask */
passedPawns = ~mask & whitePawns;


It's just a quick idea and I haven't really thought it through nor have I tested it in practise, but I think it will save some time especially when there are many pawns on the board. There are no loops in this code so the execution time should be constant. It's also pretty easy to avoid color-dependent code but I didn't feel like going through that extra trouble here.

EDIT: to clarify how the genPawnMoves function works: it computes a mask of pawn captures and one-square pawn moves, ignoring the fact that there may not be anything to capture or that the pawn may be blocked/pinned. Here's how I do it: http://www.ics.uci.edu/~eppstein/180a/970408.html (see Representation 4: bitboards).

toma wrote:My engine (and I think most of bitboard programs) don't use only bitboards but hybrid solutions.

That's not an option for me, I'm afraid. Even without bitboards, my current source code is too big and complicated. I can't add bitboards on top of it all; I have to rip out my current data structures and replace everything with bitboards.

Beside bitboards I have also lists of pieces. So I don't have to scan trough entire bitboard to find pawns. Using the list of pawns and bitboards you can check for free pawns pretty fast.

This is possible, but then there is little point in using bitboards. Unless I can use setwise operations, bitboards will only make my program bigger, slower and uglier.

Tord

Tord Romstad wrote:That would work, but I am considering to drop the pawn hash table altogether. Some of the bitboard experts claim that bitboards make pawn structure evaluation so fast that there is no need for a pawn hash table.

Hey no objection to this... except for passed pawns I'm considering to drop pawn evaluation altogether!

Tord Romstad wrote:Where do I find Gerd's routines for this?

This is from Kiwi sources... I think you will find many in this forum and also in the CCC archives...
BTW Gerd told me he's not the original author once, but I got this code from his postings and wouldn't know who else to credit.

Code: Select all

const unsigned int lsz64_tbl[64] =
{
    63, 30,  3, 32, 59, 14, 11, 33,
    60, 24, 50,  9, 55, 19, 21, 34,
    61, 29,  2, 53, 51, 23, 41, 18,
    56, 28,  1, 43, 46, 27,  0, 35,
    62, 31, 58,  4,  5, 49, 54,  6,
    15, 52, 12, 40,  7, 42, 45, 16,
    25, 57, 48, 13, 10, 39,  8, 44,
    20, 47, 38, 22, 17, 37, 36, 26,
};

/*
    Bit count function by Gerd Isenberg.
*/
inline int bitCount( Uint64 bb )
{
   unsigned w = (unsigned) (bb >> 32);
   unsigned v = (unsigned) bb;

   v = v - ((v >> 1) & 0x55555555);
   w = w - ((w >> 1) & 0x55555555);
   v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
   w = (w & 0x33333333) + ((w >> 2) & 0x33333333);
   v = (v + (v >> 4)) & 0x0F0F0F0F;
   w = (w + (w >> 4)) & 0x0F0F0F0F;
   v = ((v+w) * 0x01010101) >> 24;

   return v;
}

/*
    Bit search functions by Gerd Isenberg.
*/
inline unsigned int bitSearch( BitBoard bb )
{
   Uint64 b = bb.data ^ (bb.data - 1);
   unsigned int fold = ((unsigned)b) ^ ((unsigned)(b>>32));
   return lsz64_tbl[(fold * 0x78291ACF) >> (32-6)];
}

inline unsigned int bitSearchAndReset( BitBoard & bb )
{
    Uint64 b = bb.data ^ (bb.data - 1);
    bb.data = bb.data & (bb.data - 1);
    unsigned int fold = ((unsigned)b) ^ ((unsigned)(b>>32));
    return lsz64_tbl[(fold * 0x78291ACF) >> (32-6)];
}

inline int bitScanForward( BitBoard bb )
{
    return bb.data != 0 ? (int) bitSearch(bb) : -1;
}

inline int bitScanAndResetForward( BitBoard & bb )
{
    return bb.data != 0 ? (int) bitSearchAndReset(bb) : -1;
}

inline int bitCount( const BitBoard & b )
{
    return bitCount( b.data );
}

inline int BitBoard::bitScanForward() const {
    return ::bitScanForward( data );
}



[/quote]

mathmoi wrote:In reality what you test is : "Is there an opponent paws in front of my pawn or an opponent pawn that could take my pawn."

This is done in only one AND, but you still have to iterate trough the pawns of the side to move.

Hi Mathieu,
I also check for own pawns in the advance path, i.e. when passed are doubled or tripled I only consider the most advanced as passed.

Alessandro Scotti wrote:Hi Mathieu,
I also check for own pawns in the advance path, i.e. when passed are doubled or tripled I only consider the most advanced as passed.

You are right, I forgot to mention that.

Tord Romstad wrote:I am not interested in solutions involving assembly language. If possible, I would prefer to use code which works for both colours, rather than separate code for black and white pawns.

No assembly needed... I think Gerd's routines are more than fast enough!

Where do I find Gerd's routines for this?

Tord[/quote]

I do not know if this is what you are interested in but
I use bitboards in movei only for pawns and I use Gerd's code that he posted in CCC

I have the following code of Gerd that was posted in CCC inside movei(if I remember correctly Gerd did not use the first line and used simply unsigned __int64 instead of BitBoard but it does not change the fact that the code is Gerd's code)

The code is both for passed pawns and for isolated pawns.
Gerd also posted code for backward pawns and maybe for candidate pawns(I am not sure exactly) but Movei is not using it(I remember that I tried backward pawns and it was not productive).

typedef unsigned __int64 BitBoard;

BitBoard FillDownBoard(BitBoard bb)
{
bb|=(bb>>8);
bb|=(bb>>16);
bb|=(bb>>32);
return bb;
}
BitBoard FillUpBoard(BitBoard bb)
{
bb|=(bb<<8);
bb|=(bb<<16);
bb|=(bb<<32);
return bb;
}

pawnattacksAH[LIGHT]=(pawnBB[LIGHT]<<9)&NOTFILEABB;
pawnattacksHA[LIGHT]=(pawnBB[LIGHT]<<7)&NOTFILEHBB;
pawnattacks[LIGHT]=(pawnattacksAH[LIGHT]|pawnattacksHA[LIGHT]);
isolatedpawns[LIGHT]=(pawnBB[LIGHT]&~FillDownBoard(FillUpBoard(pawnattacks[LIGHT])));

pawnattacksAH[DARK]=(pawnBB[DARK]>>7)&NOTFILEABB;
pawnattacksHA[DARK]=(pawnBB[DARK]>>9)&NOTFILEHBB;
pawnattacks[DARK]=(pawnattacksAH[DARK]|pawnattacksHA[DARK]);
isolatedpawns[DARK]=(pawnBB[DARK]&~FillDownBoard(FillUpBoard(pawnattacks[DARK])));

openpawns[LIGHT]=pawnBB[LIGHT]&~FillDownBoard(allpawns>>8);
openpawns[DARK]=pawnBB[DARK]&~FillUpBoard(allpawns<<8);
passedpawns[LIGHT]=openpawns[LIGHT]&~FillDownBoard(pawnattacks[DARK]);
passedpawns[DARK]=openpawns[DARK]&~FillUpBoard(pawnattacks[LIGHT]);

Uri

Tord Romstad wrote:Hi all,

I am once again experimenting with bitboards. I have made numerous private rotated bitboard versions of Glaurung over the last year, but they were always slower and less compact than my mailbox versions (even on the 64-bit G5 CPU). The reason is almost certainly that I haven't learnt all the tricks yet. As others have demonstrated, it is definitely possible to write blazingly fast bitboard programs.

Right now, I am thinking about the following problem: What is the best way to obtain a bitboard of all passed pawns for one side? The obvious way is to loop through all pawns and check each pawn individually, but this is very slow. It seems that the key to making bitboards fast is to avoid having too many loops through the nonzero bits of a bitboard.

I am not interested in solutions involving assembly language. If possible, I would prefer to use code which works for both colours, rather than separate code for black and white pawns.

Tord

Is 5 operations (max) too many?

You can move an entire side worth of pawns forward with one shift.
I think that the implication is obvious.

With a little bit more work you can also find out if they are clear of pawns on either edge (shoving forward until they ram opposite pawns only shows slots forward, but if you need to know clearance, you can also figure the attacks for the entire bank of opponent pawns with 2 shifts per advance. Don't forget that the edge bits should be clear for the direction of the shift.)

Reinhard Scharnagl wrote:What did you convince that bitboard programs would be the fastest ?

Reinhard.

As far as I know the best chess program in the world(Rybka) is a bitboard program.

Of course it is not a proof that bitboard is faster but it supports that theory.


Uri

I would be very astonished if the kind of its move generator would be the key to its success ;-)

Reinhard.

Uri Blass wrote:I do not know if this is what you are interested in but
I use bitboards in movei only for pawns and I use Gerd's code that he posted in CCC

Hi Uri,

Thanks for the code! This looks usable - I'll give it a try.

Gerd also posted code for backward pawns and maybe for candidate pawns(I am not sure exactly) but Movei is not using it(I remember that I tried backward pawns and it was not productive).

This is very surprising. In my experience, backward pawns are at least as important as isolated pawns.

Tord

I can say that last time that I tried to evaluate backward pawns was some years ago and it is possible that today it is productive.

It is also possible that I simply did not try the right weights to make it productive or that I did not play enough games.

I found the relevant discussion in old CCC

Here is one of the post of Gerd from that discussion

http://chessprogramming.org/cccsearch/c ... _id=271287

He later gave correction for not defendable

from that thread:

notDefendable[WHITE] = pawnBB[WHITE] & ~fillup(pawnAttacks[WHITE]);
Backward pawns:

First we need all squares dominated by sides pawn attacks:

pawnDomination[side] = (pawnDblAttacks[side] & ~pawnDblAttacks[other(side)])
| (pawnAttacks[side] & ~pawnAttacks[other(side)]);

backWard1[WHITE] = notDefendable[WHITE] & (pawnDomination[BLACK] >> 8);
backWard2[WHITE] = backWard1[WHITE] & openPawns[WHITE];

Uri

Tord Romstad wrote:Hi all,

I am once again experimenting with bitboards. I have made numerous private rotated bitboard versions of Glaurung over the last year, but they were always slower and less compact than my mailbox versions (even on the 64-bit G5 CPU). The reason is almost certainly that I haven't learnt all the tricks yet. As others have demonstrated, it is definitely possible to write blazingly fast bitboard programs.

Right now, I am thinking about the following problem: What is the best way to obtain a bitboard of all passed pawns for one side? The obvious way is to loop through all pawns and check each pawn individually, but this is very slow. It seems that the key to making bitboards fast is to avoid having too many loops through the nonzero bits of a bitboard.

I am not interested in solutions involving assembly language. If possible, I would prefer to use code which works for both colours, rather than separate code for black and white pawns.

Tord

Bitboards are slow for me too, I'm not sure exactly why either, but I do have a really fast passed pawn detection code. It avoids a lot of uncessary looping in bitboards that we are all afraid of.

Code: Select all

/*passedPawnEval()
 *passed pawn evaluvation
 *it is based on the passed pawn PST
 *
 *the basic idea behind optimization of this is that
 *when you find that a pawn is not passed, the opponent
 *pawns are not passed either, so you skip doing tests
 *for them. This improves performance 2-3x.  For the initial
 *position, only 4 tests are needed to test if any of the pawns
 *are passed isntead of 16 tests.
 *
 *@param pos - the board position to be evaluvated
 */
int passedPawnEval(const board* pos)
{
   int sq, score=0;
   U64 BlackPawns, WhitePawns; //static pawn bitboards
   U64 BPawns, WPawns; //changing pawn bitboards

   BlackPawns=BPawns=pos->Pieces[P]&pos->PiecesSide[BLACK];
   WhitePawns=WPawns=pos->Pieces[P]&pos->PiecesSide[WHITE];

   while(WPawns)
   {
      sq=LastOne(WPawns);
      WPawns^=toBit[sq];
      if(BlackPawns&detectPasserWHITE[sq])
         BPawns&=~detectPasserWHITE[sq];
      else
      {
         score+=passedPawnPST[sq];
         continue;
      }

BPasser:
      if(BPawns)
      {
         sq=LastOne(BPawns);
         BPawns^=toBit[sq];
         if(WhitePawns&detectPasserBLACK[sq])
            WPawns&=~detectPasserBLACK[sq];
         else
         {
            score-=passedPawnPST[flip[sq]];
            goto BPasser;
         }
      }
      else
         goto WLeft;
   }


   while(BPawns)
   {
      sq=LastOne(BPawns);
      BPawns^=toBit[sq];
      if(!(WhitePawns&detectPasserBLACK[sq]))
         score-=passedPawnPST[flip[sq]];
   }
   return signSide[pos->side]*score;

WLeft:
   while(WPawns)
   {
      sq=LastOne(WPawns);
      WPawns^=toBit[sq];
      if(!(BlackPawns&detectPasserWHITE[sq]))
         score+=passedPawnPST[flip[sq]];
   }
   return signSide[pos->side]*score;
}

I haven't really tried all the tricks possible to avoid looping, but I'm sure there are many, like for generating a bitboard of all pawn captures.

Code: Select all

U64 pieceboard, pawnAttacks[2];
...
//Pawn Attacks
pieceboard=piecesBLACK(*pos,P);
pawnAttacks[BLACK]=((pieceboard&0x7F7F7F7F7F7F7F7FULL)>>7)|((pieceboard&0xFEFEFEFEFEFEFEFEULL)>>9);

pieceboard=piecesWHITE(*pos,P);
pawnAttacks[WHITE]=((pieceboard&0x7F7F7F7F7F7F7F7FULL)<<9)|((pieceboard&0xFEFEFEFEFEFEFEFEULL)<<7);


Similarly pawn doubble attacks can be done with an & instead of an | in the above code.

I think if we could reduce unnecessary looping as much as possible we can also achieve blazing fast programs. Anyways, the CCC post with using fillUp, fillDown is pretty interesting.