Bitboard of Pinned Pieces

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
grant
Posts: 67
Joined: Mon Aug 06, 2007 2:42 pm
Location: London, England

Bitboard of Pinned Pieces

Post by grant » Thu Jul 24, 2008 12:41 pm

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
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: Bitboard of Pinned Pieces

Post by jwes » Thu Jul 24, 2008 3:18 pm

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).

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Bitboard of Pinned Pieces

Post by Zach Wegner » Thu Jul 24, 2008 4:16 pm

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
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Bitboard of Pinned Pieces

Post by Gerd Isenberg » Thu Jul 24, 2008 5:06 pm

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

Gerd

Gerd Isenberg
Posts: 2125
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Bitboard of Pinned Pieces

Post by Gerd Isenberg » Thu Jul 24, 2008 5:14 pm

jwes wrote: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
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Bitboard of Pinned Pieces

Post by bob » Thu Jul 24, 2008 8:22 pm

grant wrote: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...

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Bitboard of Pinned Pieces

Post by sje » Thu Jul 24, 2008 10:10 pm

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
Posts: 761
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Bitboard of Pinned Pieces

Post by Edsel Apostol » Fri Jul 25, 2008 12:14 am

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
Posts: 20406
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Bitboard of Pinned Pieces

Post by bob » Fri Jul 25, 2008 5:18 am

Edsel Apostol wrote: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
Posts: 761
Joined: Mon Jul 17, 2006 3:53 am
Full name: Edsel Apostol
Contact:

Re: Bitboard of Pinned Pieces

Post by Edsel Apostol » Fri Jul 25, 2008 7:59 am

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.

Post Reply