Difference between revisions of "Checks and Pinned Pieces (Bitboards)"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Board Representation * Bitboards * Checks and Pinned Pieces''' This is about whether the king is in check. If so, one likel...")
 
 
Line 38: Line 38:
 
<span id="AbsolutePins"></span>
 
<span id="AbsolutePins"></span>
 
=Absolute Pins=  
 
=Absolute Pins=  
To detect [[Pin#AbsolutePin|absolute pins]] is necessary for [[Legal Move|legal]] [[Move Generation|move generation]] and may be considered in [[Evaluation|evaluation]]. While there are different approaches, the most common for programs based on single sliding piece attacks rather than direction wise set-wise attack getter, relies on the [[X-ray Attacks (Bitboards)#ModifyingOccupancy|xrayRookAttacks]] or [[X-ray Attacks (Bitboards)#ModifyingOccupancy|xrayBishopAttacks]] routines - called with square of own king and own pieces as blockers. An [[Square Attacked By#Obstructed|in-between lookup]] determines the set of pinned pieces while [[Bitboard Serialization|traversing]] the pinning pieces.
+
To detect [[Pin#AbsolutePin|absolute pins]] is necessary for [[Legal Move|legal]] [[Move Generation|move generation]] and may be considered in [[Evaluation|evaluation]]. While there are different approaches, the most common for programs based on single sliding piece attacks rather than direction wise set-wise attack getter, relies on the [[X-ray Attacks (Bitboards)#ModifyingOccupancy|xrayRookAttacks]] or [[X-ray Attacks (Bitboards)#ModifyingOccupancy|xrayBishopAttacks]] routines - called with square of own king and own pieces as blockers. An [[Square Attacked By#Obstructed|in-between lookup]] (Obstructed) determines the set of pinned pieces while [[Bitboard Serialization|traversing]] the pinning pieces <ref>[https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79617&start=2 Re: Pinned Pieces With Bitboards] by tcusr, [[CCC]], April 01, 2022</ref>.
 
<pre>
 
<pre>
 
pinned = 0;
 
pinned = 0;
Line 56: Line 56:
 
<span id="OppositeRay"></span>
 
<span id="OppositeRay"></span>
 
=Opposite Ray-Directions=
 
=Opposite Ray-Directions=
Another idea to determine absolute pins as well as distant check block-targets, or possible discovered check origins, is to apply disjoint direction-wise attacks, as demonstrated in the [[DirGolem]] proposal, where this technique is used for all eight ray-dirctions. The intersection of direction attacks of potential pinning sliding pieces with the opposite ray-direction attacks of the king treated as sliding super piece, gains enough information if further intersected by empty squares, own, or opponent pieces. For instance as illustrated with a black rook and white king on the same rank, with no, one and two pieces inbetween:
+
Another idea to determine absolute pins as well as distant check block-targets, or possible discovered check origins, is to apply disjoint direction-wise attacks, as demonstrated in the [[DirGolem]] proposal, where this technique is used for all eight ray-directions. The intersection of direction attacks of potential pinning sliding pieces with the opposite ray-direction attacks of the king treated as sliding super piece, gains enough information if further intersected by empty squares, own, or opponent pieces. For instance as illustrated with a black rook and white king on the same rank, with no, one and two pieces inbetween:
  
 
No obstruction, king in check. In-between intersection consists of empty squares as target set to block the distant check:
 
No obstruction, king in check. In-between intersection consists of empty squares as target set to block the distant check:
Line 92: Line 92:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=22550 Bitboard of Pinned Pieces] by [[Grant Osborne]], [[CCC]], July 24, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=22550 Bitboard of Pinned Pieces] by [[Grant Osborne]], [[CCC]], July 24, 2008
 
* [http://www.talkchess.com/forum/viewtopic.php?t=41351 Check detection and move generation using bitboards] by [[Lasse Hansen]], [[CCC]], December 06, 2011
 
* [http://www.talkchess.com/forum/viewtopic.php?t=41351 Check detection and move generation using bitboards] by [[Lasse Hansen]], [[CCC]], December 06, 2011
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79617 Pinned Pieces With Bitboards] by Andrew Zhuo, [[CCC]], April 01, 2022
  
 +
=References=
 +
<references />
 
[[Bitboards|Up one Level]]
 
[[Bitboards|Up one Level]]

Latest revision as of 11:13, 4 April 2022

Home * Board Representation * Bitboards * Checks and Pinned Pieces

This is about whether the king is in check. If so, one likely uses a specialized check evasion move generator. One may also trigger search extensions - based on the king is in check - or based on the check evasion move generator only reports one valid move. Related to determining discovered check is to look for absolute pins.

Checks

Whether the king is in check may be determined on the fly by looking up attacks to the king square - or based on the last move made by the other, probably checking side. Another option is to determine check giving moves already at generation time, and to flag moves accordantly.

On the Fly

Whether a king is in check can be determined by the attacked-routine mentioned in Square Attacked By. We pass the square of the king and opposite color for the potential attackers.

If one needs the set of attackers, either empty, single or double populated - one likely better relies on a specialized attacksTo-routine for each side, e.g. as member of the standard bitboard board-definition:

U64 CBoard::attacksToKing(enumSquare squareOfKing, enumColor colorOfKing) {
   U64 opPawns, opKnights, opRQ, opBQ;
   opPawns     = pieceBB[nBlackPawn   - colorOfKing];
   opKnights   = pieceBB[nBlackKnight - colorOfKing];
   opRQ = opBQ = pieceBB[nBlackQueen  - colorOfKing];
   opRQ       |= pieceBB[nBlackRook   - colorOfKing];
   opBQ       |= pieceBB[nBlackBishop - colorOfKing];
   return (arrPawnAttacks[colorOfKing][squareOfKing] & opPawns)
        | (arrKnightAttacks[squareOfKing]            & opKnights)
        | (bishopAttacks (occupiedBB, squareOfKing)  & opBQ)
        | (rookAttacks   (occupiedBB, squareOfKing)  & opRQ)
        ;
}

By Move

Another idea is to determine the check inside the search-routine by the last move done by the opponent. It might be a direct or discovered check - or in case of double check, both. With bitboards the possible savings to determine checks by last move seems negligible - and one probably better relies on the branch-less on the fly solution, since we may reuse the rook-wise and bishop-wise attacks for other purposes - like determining absolute pinned pieces, kingsafety-evaluation, and/or whether the opponent side threatens checks or discovered checks.

Direct Check

For the direct check we may use the routine mentioned in Square Attacked By:

if ( isAttacked(squareOfKing, move.to, move.piece(), occupiedBB) ) -> direct check

Discovered Check

One solution is to determine the direction between the from-square and the king square (e.g. by 0x88 difference). If both squares share a common line, one calls an appropriate sliding ray- or line-attack getter with king square and occupancy, to look whether this set intersects the possible opponing sliders of that ray. One also has to prove, whether a possible true result was not caused by a direct check of a sliding capture.

Absolute Pins

To detect absolute pins is necessary for legal move generation and may be considered in evaluation. While there are different approaches, the most common for programs based on single sliding piece attacks rather than direction wise set-wise attack getter, relies on the xrayRookAttacks or xrayBishopAttacks routines - called with square of own king and own pieces as blockers. An in-between lookup (Obstructed) determines the set of pinned pieces while traversing the pinning pieces [1].

pinned = 0;
pinner = xrayRookAttacks(occupiedBB, ownPieces, squareOfKing) & opRQ;
while ( pinner ) {
   int sq  = bitScanForward(pinner);
   pinned |= obstructed(sq, squareOfKing) & ownPieces;
   pinner &= pinner - 1;
}
pinner = xrayBishopAttacks(occupiedBB, ownPieces, squareOfKing) & opBQ;
while ( pinner ) {
   int sq  = bitScanForward(pinner);
   pinned |= obstructed(sq, squareOfKing) & ownPieces;
   pinner &= pinner - 1;
}

Opposite Ray-Directions

Another idea to determine absolute pins as well as distant check block-targets, or possible discovered check origins, is to apply disjoint direction-wise attacks, as demonstrated in the DirGolem proposal, where this technique is used for all eight ray-directions. The intersection of direction attacks of potential pinning sliding pieces with the opposite ray-direction attacks of the king treated as sliding super piece, gains enough information if further intersected by empty squares, own, or opponent pieces. For instance as illustrated with a black rook and white king on the same rank, with no, one and two pieces inbetween:

No obstruction, king in check. In-between intersection consists of empty squares as target set to block the distant check:

     . r . . . . K .     
r->  . . 1 1 1 1 1 .      
<-K  . 1 1 1 1 1 . .
&    . . 1 1 1 1 . .  

One piece in-between. Intersection leaves a pinned piece if of king color, otherwise a possible discovered checker:

     . r . . x . K .  
r->  . . 1 1 1 . . .             
<-K  . . . . 1 1 . .
&    . . . . 1 . . .

Two (or more) pieces in-between. Intersection is null:

      . r . x x . K .  
r->   . . 1 1 . . . .
<-K   . . . . 1 1 . .
&     . . . . . . . .   

See also

Forum Posts

References

  1. Re: Pinned Pieces With Bitboards by tcusr, CCC, April 01, 2022

Up one Level