Finding all pins in a position with bitboards

[Pradu]

Say for this position:
[diag]2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6[/diag]
2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6 b - - 0 1

I wanted to find a pinned pieces bitboard:

Code: Select all

00000000
00010000
00000000
00010000
00000100
00010000
00000000
00000000

And I have bitboards of unprotected pieces. What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

[Gerd Isenberg]

What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

That is what I intend with multi-set simd-fills aka quad-bitboard-fills, pairwise (direction and opposite direction) - simultaniously for potential pinners plus king and hanging or enprise pieces for both colors within two 128-bit xmm-registers.

[Onno Garms]

What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

I don't know. Is a loop over all potential pinners so expensive? In most positions, there are not many potential pinners.

Anyway, I would also be interested to hear of a loopless solution (at least for performance comparison). Gerd, do you have one or are you planning to develop one?

[Pradu]

What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

I don't know. Is a loop over all potential pinners so expensive? In most positions, there are not many potential pinners.

Not sure what you mean. I was thinking every slider that attacks an opponent piece with another opponent piece behind it is a potential pinner. You just have to figure out if the piece is pinned to a more valuable/poorly guarded piece.

[Ron Murawski]

Say for this position:
[diag]2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6[/diag]
2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6 b - - 0 1

I wanted to find a pinned pieces bitboard:

Code: Select all

00000000
00010000
00000000
00010000
00000100
00010000
00000000
00000000

And I have bitboards of unprotected pieces. What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

Hi Pradu,

I'm looking at your diagram and I'm looking at your bitboard and I realized that you are combining three distict situations into the same bitboard. You don't want to do this because the logic for each is quite different.

Case #1: king-pinned pieces. In your diagram that's the knight on f4. King-pinned pieces *always* matter and can never attack or defend.

Case #2: piece-pinned pieces. (where a lesser piece blocks a more valuable piece from being captured). In your diagram the White knight on c7 is piece-pinned. The Black rook on c5 is also piece-pinned. Piece-pinned pieces don't matter if you are giving check because the opponent doesn't have time to make threats against these pieces or time to capture them. In your bitboard diagram, since Black is in check, the White knight on c7 should be removed from your bitboard of pins.

Case #3: pieces that are attacked by less valuable pieces. In your diagram that would be the White rook on c3. In the general case for lesser attacks using a quick-and-dirty method it's the maximum piece value that "wins". For instance if your rook is attacked by an opponent and you are attacking the opponent's queen, then your attack on the opponent's queen "wins" and the attack on the rook does not matter. The reason for this is that the opponent does not have the time to capture your rook, he must first move his queen to safety. The eval scoring for your "win" is the value of a tempo, usually 0.25 - 0.30. If you can understand that the opponent has no tempos avalable to attack your rook, then you can understand that pieces that are attacked by less valuable pieces do not matter if you are giving check because the opponent must deal with the check and has no time to capture (unless it is the piece that gives check). So in your diagram the White rook on c3 should also be removed.

The only pinned White piece in your diagram should be the king-pinned knight on f4. The Black rook on d5 is the other pinned piece -- it is piece-pinned.

In my engine I found that it took too long to find genuine piece-pinned pieces. Often there were other tactics that were more important than the piece-pin. For instance if a rook is piece-pinned because it is protecting its queen, but in the next move the queen can give check, then the rook that was briefly piece-pinned can suddenly become a big threat. Using the information from piece-pinning is really difficult to do right. I've never been able to do it in a way that was safe.

There is another case and it is:
Case #4 an attacked undefended piece. Ignore it if your are giving check. As long as it's not the piece that gives check the opponent has no time to capture it. It gets treated exactly like Case #3 and it is probably better to combine case #3 and #4 together in calculating the highest value piece that is attacked to determione who "wins".

Ron

[Gerd Isenberg]

I don't know. Is a loop over all potential pinners so expensive? In most positions, there are not many potential pinners.

Anyway, I would also be interested to hear of a loopless solution (at least for performance comparison). Gerd, do you have one or are you planning to develop one?

In my running old 32-bit program I use floodfill with mmx (dumb7fill+koggeStone) for all sliding attacks, absolute pins and pieces that may discovered check. The new approach, still in design phase, will have quad-bitboard fills with 128-bit xmm-registers to get sets of commited pieces...

[Tony van Roon-Werten]

Say for this position:
[diag]2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6[/diag]
2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6 b - - 0 1

I wanted to find a pinned pieces bitboard:

Code: Select all

00000000
00010000
00000000
00010000
00000100
00010000
00000000
00000000

And I have bitboards of unprotected pieces. What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

Hi Pradu,

I'm looking at your diagram and I'm looking at your bitboard and I realized that you are combining three distict situations into the same bitboard. You don't want to do this because the logic for each is quite different.

Case #1: king-pinned pieces. In your diagram that's the knight on f4. King-pinned pieces *always* matter and can never attack or defend.

Case #2: piece-pinned pieces. (where a lesser piece blocks a more valuable piece from being captured). In your diagram the White knight on c7 is piece-pinned. The Black rook on c5 is also piece-pinned. Piece-pinned pieces don't matter if you are giving check because the opponent doesn't have time to make threats against these pieces or time to capture them. In your bitboard diagram, since Black is in check, the White knight on c7 should be removed from your bitboard of pins.

Case #3: pieces that are attacked by less valuable pieces. In your diagram that would be the White rook on c3. In the general case for lesser attacks using a quick-and-dirty method it's the maximum piece value that "wins". For instance if your rook is attacked by an opponent and you are attacking the opponent's queen, then your attack on the opponent's queen "wins" and the attack on the rook does not matter. The reason for this is that the opponent does not have the time to capture your rook, he must first move his queen to safety. The eval scoring for your "win" is the value of a tempo, usually 0.25 - 0.30. If you can understand that the opponent has no tempos avalable to attack your rook, then you can understand that pieces that are attacked by less valuable pieces do not matter if you are giving check because the opponent must deal with the check and has no time to capture (unless it is the piece that gives check). So in your diagram the White rook on c3 should also be removed.

The only pinned White piece in your diagram should be the king-pinned knight on f4. The Black rook on d5 is the other pinned piece -- it is piece-pinned.

In my engine I found that it took too long to find genuine piece-pinned pieces. Often there were other tactics that were more important than the piece-pin. For instance if a rook is piece-pinned because it is protecting its queen, but in the next move the queen can give check, then the rook that was briefly piece-pinned can suddenly become a big threat. Using the information from piece-pinning is really difficult to do right. I've never been able to do it in a way that was safe.

There is another case and it is:
Case #4 an attacked undefended piece. Ignore it if your are giving check. As long as it's not the piece that gives check the opponent has no time to capture it. It gets treated exactly like Case #3 and it is probably better to combine case #3 and #4 together in calculating the highest value piece that is attacked to determione who "wins".

Ron

It might actually be 5 because #2 should be split up imo. The rook on d5 can capture (without loss) the pinning piece while the knight on d7 cannot. (In my engine this is considered a "serious" difference)

Cheers,

Tony

[H.G.Muller]

For instance if a rook is piece-pinned because it is protecting its queen, but in the next move the queen can give check, then the rook that was briefly piece-pinned can suddenly become a big threat.

Indeed, I see Joker make this mistake quite often: it voluntarily moves its pieces to squares where they are attacked by pinned pieces.

This is a motif that is as dangerous as (and logically equivalent to) a discovered threat: the opponent can reactivate the threat by moving the pinned piece, possibly also making a new threat with that one, confronting you with an insolvable dual threat.

This is not so bad if the piece is pinned on the King, as usually a King somewhere in the rear guard is not able to make any new threats. But for other pieces that you can easily pin something on (Queens and Rooks) it is totally fatal.

[Onno Garms]

Not sure what you mean. I was thinking every slider that attacks an opponent piece with another opponent piece behind it is a potential pinner.

I see. I only though of sliders that attack an opponent piece with the openent king behind it. So in your example, only Nf4 is pinned.

How do you intend to use your definition of pinned pieces?

[Pradu]

Not sure what you mean. I was thinking every slider that attacks an opponent piece with another opponent piece behind it is a potential pinner.

I see. I only though of sliders that attack an opponent piece with the openent king behind it. So in your example, only Nf4 is pinned.

How do you intend to use your definition of pinned pieces?

Use it somehow in eval, eg detract some score for pins for your side and no mobility bonus for pinned pieces.

[Ron Murawski]

Say for this position:
[diag]2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6[/diag]
2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6 b - - 0 1

I wanted to find a pinned pieces bitboard:

Code: Select all

00000000
00010000
00000000
00010000
00000100
00010000
00000000
00000000

And I have bitboards of unprotected pieces. What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

Hi Pradu,

I'm looking at your diagram and I'm looking at your bitboard and I realized that you are combining three distict situations into the same bitboard. You don't want to do this because the logic for each is quite different.

Case #1: king-pinned pieces. In your diagram that's the knight on f4. King-pinned pieces *always* matter and can never attack or defend.

Case #2: piece-pinned pieces. (where a lesser piece blocks a more valuable piece from being captured). In your diagram the White knight on c7 is piece-pinned. The Black rook on c5 is also piece-pinned. Piece-pinned pieces don't matter if you are giving check because the opponent doesn't have time to make threats against these pieces or time to capture them. In your bitboard diagram, since Black is in check, the White knight on c7 should be removed from your bitboard of pins.

Case #3: pieces that are attacked by less valuable pieces. In your diagram that would be the White rook on c3. In the general case for lesser attacks using a quick-and-dirty method it's the maximum piece value that "wins". For instance if your rook is attacked by an opponent and you are attacking the opponent's queen, then your attack on the opponent's queen "wins" and the attack on the rook does not matter. The reason for this is that the opponent does not have the time to capture your rook, he must first move his queen to safety. The eval scoring for your "win" is the value of a tempo, usually 0.25 - 0.30. If you can understand that the opponent has no tempos avalable to attack your rook, then you can understand that pieces that are attacked by less valuable pieces do not matter if you are giving check because the opponent must deal with the check and has no time to capture (unless it is the piece that gives check). So in your diagram the White rook on c3 should also be removed.

The only pinned White piece in your diagram should be the king-pinned knight on f4. The Black rook on d5 is the other pinned piece -- it is piece-pinned.

In my engine I found that it took too long to find genuine piece-pinned pieces. Often there were other tactics that were more important than the piece-pin. For instance if a rook is piece-pinned because it is protecting its queen, but in the next move the queen can give check, then the rook that was briefly piece-pinned can suddenly become a big threat. Using the information from piece-pinning is really difficult to do right. I've never been able to do it in a way that was safe.

There is another case and it is:
Case #4 an attacked undefended piece. Ignore it if your are giving check. As long as it's not the piece that gives check the opponent has no time to capture it. It gets treated exactly like Case #3 and it is probably better to combine case #3 and #4 together in calculating the highest value piece that is attacked to determione who "wins".

Ron

It might actually be 5 because #2 should be split up imo. The rook on d5 can capture (without loss) the pinning piece while the knight on d7 cannot. (In my engine this is considered a "serious" difference)

Cheers,

Tony

Hi Tony,

I spent several months experimenting with pinned pieces that "fight back" along the rank/file/diagonal from which they were attacked and I could not find a way to use the information in improving playing strength. Based on my experimentation I believe that the most important consideration is that Black has no time to make any captures or threats if he is in check. In the general case: if White gives check, then *all* White pieces are perfectly safe with the possible exception of:
* Black capturing the piece that gives check
* Black capturing a piece with his king
IMO all other Black "threats" are mirages.

Ron

[Dann Corbit]

Say for this position:
[diag]2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6[/diag]
2Q4k/3N4/3q4/3r1b2/5N2/3R1RK1/8/1B6 b - - 0 1

I wanted to find a pinned pieces bitboard:

Code: Select all

00000000
00010000
00000000
00010000
00000100
00010000
00000000
00000000

And I have bitboards of unprotected pieces. What is the fastest way to calculate the bitboard of all pinned pieces? Is there a loopless bit-paralell way to do this? Perhaps with floodfills?

Precompute and store in a table of bitmaps.
For any slider at position p on a board, there are at most 127 possible states on any of his rays. You can simply index the 7 bit number to find out the attacks, pins, etc.

In addition, the maximum of 2 direct attacks/defends for opponentcolor/mycolor have only a few states as well.
Half-pins are also useful for battery calculation. You can use quarter pins if you want to get esoteric.

[Pradu]

Precompute and store in a table of bitmaps.
For any slider at position p on a board, there are at most 127 possible states on any of his rays. You can simply index the 7 bit number to find out the attacks, pins, etc.

That's true but that's computing each pinned piece separately instead of computing them all in parallel.

In addition, the maximum of 2 direct attacks/defends for opponentcolor/mycolor have only a few states as well.
Half-pins are also useful for battery calculation. You can use quarter pins if you want to get esoteric.

I don't quite understand this can you elaborate on what you mean by a "direct attack/defend for opponentcolor/mycolor". I probably should by now but embarresingly, I do not know the concept of half-pins and quarter-pins. Can you elaborate on this as well?

[Dann Corbit]

Precompute and store in a table of bitmaps.
For any slider at position p on a board, there are at most 127 possible states on any of his rays. You can simply index the 7 bit number to find out the attacks, pins, etc.

That's true but that's computing each pinned piece separately instead of computing them all in parallel.

You precompute the answers and store them. There is no computation at runtime. You can do the simple way and just store the table of precomputed bitmaps, or you can go past that and encode all of the actions for the bitmaps in separate functions.

In addition, the maximum of 2 direct attacks/defends for opponentcolor/mycolor have only a few states as well.
Half-pins are also useful for battery calculation. You can use quarter pins if you want to get esoteric.

I don't quite understand this can you elaborate on what you mean by a "direct attack/defend for opponentcolor/mycolor". I probably should by now but embarresingly, I do not know the concept of half-pins and quarter-pins. Can you elaborate on this as well?

[diag]
1k1n3q/1n4b1/1R6/1Q6/1R6/2P5/1n6/K7 w - -
[/diag]
Some of the terms I don't really know too well, so I just make up my own.
In the above diagram, white's rook on B6 directly attacks the knight, and has a full pin on the same knight. In a similar manner, the rook on B6 also directly defends the queen. One piece removed, the rook has a shadow attack on the king and a shadow defend on the other white rook.
The white rook on B4 directly attack the black knight on B2 and direcrtly defends the white queen on B5. The white rook on B4 has a shadow defend of the white rook on B6 and a half shadow on the black knight on B7 and a quarter shadow on the black king on b8.

I calculate it like this:
All non sliders have only direct attacks (pawn, King, knight).
All other pieces attack directly the empty squares between themselves and any first piece standing on one of their rays.
So the direct attack bitmap for the rook on B4 is the squares B1, B2, B5.
The shadow attack bitmap for the rook on B4 is the squares B1 and B6.
The half-shadow attack bitmap for the rook on B4 is the square B7.
The quarter-shadow attack bitmap for the rook on B4 is B8.

For the whole board, you can mark each square as safe for a given piece type, depending on what attacks it, and if lowest attackers are equal, by the MVV/LVA against it (which can be fully precomputed and incrementally updated as each piece moves).

The bitmaps calculated do not even have to be stored. You can instead use the bits to create board increment functions that increment the attackers for the squares by piece type.

I am sure that there are many other approaches that are as good or better than this one, but it seems obvious and intuitive for me.

[Dann Corbit]

Precompute and store in a table of bitmaps.
For any slider at position p on a board, there are at most 127 possible states on any of his rays. You can simply index the 7 bit number to find out the attacks, pins, etc.

That's true but that's computing each pinned piece separately instead of computing them all in parallel.

You precompute the answers and store them. There is no computation at runtime. You can do the simple way and just store the table of precomputed bitmaps, or you can go past that and encode all of the actions for the bitmaps in separate functions.

In addition, the maximum of 2 direct attacks/defends for opponentcolor/mycolor have only a few states as well.
Half-pins are also useful for battery calculation. You can use quarter pins if you want to get esoteric.

I don't quite understand this can you elaborate on what you mean by a "direct attack/defend for opponentcolor/mycolor". I probably should by now but embarresingly, I do not know the concept of half-pins and quarter-pins. Can you elaborate on this as well?

[diag]
1k1n3q/1n4b1/1R6/1Q6/1R6/2P5/1n6/K7 w - -
[/diag]
Some of the terms I don't really know too well, so I just make up my own.
In the above diagram, white's rook on B6 directly attacks the knight, and has a full pin on the same knight. In a similar manner, the rook on B6 also directly defends the queen. One piece removed, the rook has a shadow attack on the king and a shadow defend on the other white rook.
The white rook on B4 directly attack the black knight on B2 and direcrtly defends the white queen on B5. The white rook on B4 has a shadow defend of the white rook on B6 and a half shadow on the black knight on B7 and a quarter shadow on the black king on b8.

I calculate it like this:
All non sliders have only direct attacks (pawn, King, knight).
All other pieces attack directly the empty squares between themselves and any first piece standing on one of their rays.
So the direct attack bitmap for the rook on B4 is the squares B1, B2, B5.
The shadow attack bitmap for the rook on B4 is the squares B1 and B6.
The half-shadow attack bitmap for the rook on B4 is the square B7.
The quarter-shadow attack bitmap for the rook on B4 is B8.

For the whole board, you can mark each square as safe for a given piece type, depending on what attacks it, and if lowest attackers are equal, by the MVV/LVA against it (which can be fully precomputed and incrementally updated as each piece moves).

The bitmaps calculated do not even have to be stored. You can instead use the bits to create board increment functions that increment the attackers for the squares by piece type.

I am sure that there are many other approaches that are as good or better than this one, but it seems obvious and intuitive for me.

This is the diagram. I do not know how to show it properly here:
[D]1k1n3q/1n4b1/1R6/1Q6/1R6/2P5/1n6/K7 w - -

[Peter Fendrich]

[This is the diagram. I do not know how to show it properly here:

1k1n3q/1n4b1/1R6/1Q6/1R6/2P5/1n6/K7 w - -
[diag]1k1n3q/1n4b1/1R6/1Q6/1R6/2P5/1n6/K7 w - - [/diag]