Bitboard of Pinned Pieces

[grant]

Hi

Again I find myself coming up with an idea and not being at my computer to test it out, so apologies for this.

I was reading through some posts about generating a bitboard of pinned pieces and found this post by Gerd

Code: Select all

rookWise  = rookAttacks(occ, kiSq); 
potPinned = rookWise & ownPieces; 
xrays     = rookWise ^ rookAttacks(occ ^ potPinned, kiSq); 
pinners   = xrays    & oppoRookOrQueen; 

pinned    = 0; 
while ( pinners ) 
{ 
    pinnerSq = bitScanForward(pinners); 
    pinned  |= potPinned & obstructed[pinnerSq][kiSq]); 
    pinners &= pinners - 1; 
} 
... same for bishops/queens 

After finding the pinners and potentially pinned pieces, we could OR these together as board occupation since pinners are always further from the king than potentially pinned, and use "magic" to lookup the pre-calculated pinned pieces bitboard.

Code: Select all

rookWise  = rookAttacks(occ, kiSq); 
potPinned = rookWise & ownPieces; 
xrays     = rookWise ^ rookAttacks(occ ^ potPinned, kiSq); 
pinners   = xrays    & oppoRookOrQueen; 
pinned    = pinnedByRook(pinners | (potPinned & pinMask), kiSq);



U64 pinnedByRook(U64 occ, int square)
{
	index = (int)((occ * rookPinMagic[square]) >> rookPinShift[square]);
	return *(pinIndecies[square] + index);
}

... same for bishops/queens

Not having tested this, I am assuming that magic numbers exist. My first guess at the table size would be around 600K which is a bit of a downer but may be less depending on the magics. At least it saves looping through all the pinners.

Grant

[jwes]

What I am trying is:

Code: Select all

   pinned[wtm] = (attks[1-wtm][0] & kattks[wtm][0]) |
	   (attks[1-wtm][1] & kattks[wtm][1]) |
	   (attks[1-wtm][2] & kattks[wtm][2]) |
	   (attks[1-wtm][3] & kattks[wtm][3]);

where attks is an array of bitboards of all squares attacked by sliders for each direction, and kattks is an array of bitboards of all squares that would be attacked by the king if it were a queen for each direction (0, 45, 90, 135).

[Zach Wegner]

My first impression is that it's a waste. The vast majority of the time there are no pinned pieces, so you do a big magic lookup for nothing. Usually the loop over pinners is 0 or 1 cycles, which can be predicted pretty easily. I doubt you could improve on that.

[Gerd Isenberg]

I agree with Zach, "all the pinners" are most often empty, rarely single populated, or very rarely more than single populated.

Gerd

[Gerd Isenberg]

What I am trying is:

Code: Select all

   pinned[wtm] = (attks[1-wtm][0] & kattks[wtm][0]) |
	   (attks[1-wtm][1] & kattks[wtm][1]) |
	   (attks[1-wtm][2] & kattks[wtm][2]) |
	   (attks[1-wtm][3] & kattks[wtm][3]);

where attks is an array of bitboards of all squares attacked by sliders for each direction, and kattks is an array of bitboards of all squares that would be attacked by the king if it were a queen for each direction (0, 45, 90, 135).

I use similar as well. For pinned pieces you need to intersect with all pieces of the king color, otherwise you'll also collect potential discovered checkers. In distant check (or even double check), the set may even contain some empty squares though.

[bob]

Hi

Again I find myself coming up with an idea and not being at my computer to test it out, so apologies for this.

I was reading through some posts about generating a bitboard of pinned pieces and found this post by Gerd

Code: Select all

rookWise  = rookAttacks(occ, kiSq); 
potPinned = rookWise & ownPieces; 
xrays     = rookWise ^ rookAttacks(occ ^ potPinned, kiSq); 
pinners   = xrays    & oppoRookOrQueen; 

pinned    = 0; 
while ( pinners ) 
{ 
    pinnerSq = bitScanForward(pinners); 
    pinned  |= potPinned & obstructed[pinnerSq][kiSq]); 
    pinners &= pinners - 1; 
} 
... same for bishops/queens 

After finding the pinners and potentially pinned pieces, we could OR these together as board occupation since pinners are always further from the king than potentially pinned, and use "magic" to lookup the pre-calculated pinned pieces bitboard.

Code: Select all

rookWise  = rookAttacks(occ, kiSq); 
potPinned = rookWise & ownPieces; 
xrays     = rookWise ^ rookAttacks(occ ^ potPinned, kiSq); 
pinners   = xrays    & oppoRookOrQueen; 
pinned    = pinnedByRook(pinners | (potPinned & pinMask), kiSq);



U64 pinnedByRook(U64 occ, int square)
{
	index = (int)((occ * rookPinMagic[square]) >> rookPinShift[square]);
	return *(pinIndecies[square] + index);
}

... same for bishops/queens

Not having tested this, I am assuming that magic numbers exist. My first guess at the table size would be around 600K which is a bit of a downer but may be less depending on the magics. At least it saves looping through all the pinners.

Grant

This is one of those cases where intuition should be ignored and testing should be done. It is like the comments I get about "jeez, a bubble sort in your q-search or to SEE sort captures? Why use something so slow? Because often I am sorting 1-2-3 moves and bubble sort is as fast as anything and faster than most.

In this case, if you think about playing actual games of chess, pins are pretty rare if you are only talking about 'absolute pins" (which is a piece pinned to the king so that it can't move at all, rook/knight pinned by a bishop, rook pinned by a bishop, queen pinned by a bishop/rook. Those are _very_ rare and having more than one absolute pin in a position is beyond rare. More normal pins, such as knight pinned on a rook by a bishop might be more interesting in this light, but I doubt anyone tries to evaluate those except as part of piece scoring anyway where this "set" would not make much sense.

So, the bottom line is that you are trying to do something efficient for what is void operation for the most part, or a set of one at best...

Testing will show that the magic computation will _way_ outweigh the speed gained in those rare positions where there are multiple pins...

[sje]

Symbolic keeps track of pinned pieces against the kings. Each color has a bitboard of frozen pieces (no moves) and of restricted pieces (e.g., a bishop pinning a queen). These are used to good effect in move generation where only legal moves are output by the routines. They are also used in positional scoring.

During move execution, the old pin bitboards are saved for a later restoration and new values are computed from scratch.

[Edsel Apostol]

In my case, I'm calling pinned pieces before I start looping through the move loop as I used it for move legality detection. So its like I'm calling it as much as I'm generating moves. Making it faster for me results to noticeable increase in speed.

By the way, here is my code:

Code: Select all

u64 pinnedPieces(const position_t *pos, u32 c) {
    u64 b, pin, pinners; int t, ksq;
	pin = 0ULL;
	ksq = pos->kpos[c];
	pinners = pos->color[c^1] & (pos->queens|pos->rooks);
	if(pinners){
    	b = rookAttacksBBX(ksq, pos->occupied) & pinners;
    	while (b) {
    		t = popFirstBit(&b);
    		pin |= InBetween[t][ksq] & pos->color[c];
    	}
    }
	pinners = pos->color[c^1] & (pos->queens|pos->bishops);
	if(pinners){
    	b = bishopAttacksBBX(ksq, pos->occupied) & pinners;
    	while (b) {
    		t = popFirstBit(&b);
    		pin |= InBetween[t][ksq] & pos->color[c];
    	}
    }
	return pin;
}

rookAttacksBBX and bishopAttacksBBX are xray attacks and InBetween is the bitboard occupancy between two squares.

I'm using a large array of bitboard attacks for the look-up (512Kb). That already includes the normal non-xray attacks.

This is the fastest one I could think of. Though it would be much faster if there is no call to popFirstBit. Is there anything faster than this?

[bob]

In my case, I'm calling pinned pieces before I start looping through the move loop as I used it for move legality detection. So its like I'm calling it as much as I'm generating moves. Making it faster for me results to noticeable increase in speed.

In the case being discussed, it really doesn't matter how many times you call it, what matters is how often is more than one piece pinned on the king. If it is, as most of us believe, usually zero, then the magic multiplication is going to hurt performance. If it could reach 3-4-5 then yes it would be a good approach. But to detect zero pins most of the time, and one on very infrequent occasions, I don't think the extra work of reading from a really big table is necessary.

And there are easier ways to either (a) check for legality or (b) just generate legal moves. I do both in Crafty in fact, depending on whether I start off at a given node in check or not...

By the way, here is my code:

Code: Select all

u64 pinnedPieces(const position_t *pos, u32 c) {
    u64 b, pin, pinners; int t, ksq;
	pin = 0ULL;
	ksq = pos->kpos[c];
	pinners = pos->color[c^1] & (pos->queens|pos->rooks);
	if(pinners){
    	b = rookAttacksBBX(ksq, pos->occupied) & pinners;
    	while (b) {
    		t = popFirstBit(&b);
    		pin |= InBetween[t][ksq] & pos->color[c];
    	}
    }
	pinners = pos->color[c^1] & (pos->queens|pos->bishops);
	if(pinners){
    	b = bishopAttacksBBX(ksq, pos->occupied) & pinners;
    	while (b) {
    		t = popFirstBit(&b);
    		pin |= InBetween[t][ksq] & pos->color[c];
    	}
    }
	return pin;
}

rookAttacksBBX and bishopAttacksBBX are xray attacks and InBetween is the bitboard occupancy between two squares.

I'm using a large array of bitboard attacks for the look-up (512Kb). That already includes the normal non-xray attacks.

This is the fastest one I could think of. Though it would be much faster if there is no call to popFirstBit. Is there anything faster than this?

are you using BSF/BSR depending on the end you want to search from? they are blazing fast on core2 type processors.

[Edsel Apostol]

Well I think you are right. The infrequent occasion is not worth the extra work and big table.

By the way, I'm using Matt Taylor's folded bitscan approach.

Can you elaborate further on this?

And there are easier ways to either (a) check for legality or (b) just generate legal moves. I do both in Crafty in fact, depending on whether I start off at a given node in check or not...

In my engine I used the return value from the pinnedPieces in determining move legality. I passed it to my sorting routine that does a lazy move generation in the move loop.