25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Checks and Pinned Pieces''' This is about whether the king is in check. If so, one likel..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Checks and Pinned Pieces'''
This is about whether the [[King|king]] is in [[Check|check]]. If so, one likely uses a specialized check evasion [[Move Generation|move generator]]. One may also trigger search [[Extensions|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|discovered check]] is to look for [[Pin#AbsolutePin|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.
<span id="ChecksOnTheFly"></span>
==On the Fly==
Whether a king is in check can be determined by the attacked-routine mentioned in [[Square Attacked By#AnyAttackBySide|Square Attacked By]]. We pass the square of the king and opposite [[Color|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 [[Square Attacked By#ByAllPieces|attacksTo-routine]] for each side, e.g. as member of the [[Bitboard Board-Definition|standard bitboard board-definition]]:
<pre>
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)
;
}
</pre>
==By Move==
Another idea is to determine the check inside the search-routine by the last [[Moves|move]] done by the opponent. It might be a direct or discovered [[Check|check]] - or in case of [[Double Check|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 [[Checks and Pinned Pieces (Bitboards)#ChecksOnTheFly|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#AttackedByPieceOnSquare|Square Attacked By]]:
<pre>
if ( isAttacked(squareOfKing, move.to, move.piece(), occupiedBB) ) -> direct check
</pre>
===Discovered Check===
One solution is to determine the [[Direction|direction]] between the [[Origin Square|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.
<span id="AbsolutePins"></span>
=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.
<pre>
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;
}
</pre>
<span id="OppositeRay"></span>
=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:
No obstruction, king in check. In-between intersection consists of empty squares as target set to block the distant check:
<pre>
. r . . . . K .
r-> . . 1 1 1 1 1 .
<-K . 1 1 1 1 1 . .
& . . 1 1 1 1 . .
</pre>
One piece in-between. Intersection leaves a pinned piece if of king color, otherwise a possible discovered checker:
<pre>
. r . . x . K .
r-> . . 1 1 1 . . .
<-K . . . . 1 1 . .
& . . . . 1 . . .
</pre>
Two (or more) pieces in-between. Intersection is null:
<pre>
. r . x x . K .
r-> . . 1 1 . . . .
<-K . . . . 1 1 . .
& . . . . . . . .
</pre>
=See also=
* [[Check]]
* [[DirGolem]]
* [[Discovered Check]]
* [[Double Check]]
* [[Pin]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=334869 Fast check detection in bitboard engine] by [[Jean-Francois Romang]], [[CCC]], December 10, 2003
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6064&p=29127 Bitboards and inCheck] by [[Andreas Guettinger]], [[Computer Chess Forums|Winboard Forum]], January 03, 2007
* [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
[[Bitboards|Up one Level]]
This is about whether the [[King|king]] is in [[Check|check]]. If so, one likely uses a specialized check evasion [[Move Generation|move generator]]. One may also trigger search [[Extensions|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|discovered check]] is to look for [[Pin#AbsolutePin|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.
<span id="ChecksOnTheFly"></span>
==On the Fly==
Whether a king is in check can be determined by the attacked-routine mentioned in [[Square Attacked By#AnyAttackBySide|Square Attacked By]]. We pass the square of the king and opposite [[Color|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 [[Square Attacked By#ByAllPieces|attacksTo-routine]] for each side, e.g. as member of the [[Bitboard Board-Definition|standard bitboard board-definition]]:
<pre>
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)
;
}
</pre>
==By Move==
Another idea is to determine the check inside the search-routine by the last [[Moves|move]] done by the opponent. It might be a direct or discovered [[Check|check]] - or in case of [[Double Check|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 [[Checks and Pinned Pieces (Bitboards)#ChecksOnTheFly|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#AttackedByPieceOnSquare|Square Attacked By]]:
<pre>
if ( isAttacked(squareOfKing, move.to, move.piece(), occupiedBB) ) -> direct check
</pre>
===Discovered Check===
One solution is to determine the [[Direction|direction]] between the [[Origin Square|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.
<span id="AbsolutePins"></span>
=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.
<pre>
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;
}
</pre>
<span id="OppositeRay"></span>
=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:
No obstruction, king in check. In-between intersection consists of empty squares as target set to block the distant check:
<pre>
. r . . . . K .
r-> . . 1 1 1 1 1 .
<-K . 1 1 1 1 1 . .
& . . 1 1 1 1 . .
</pre>
One piece in-between. Intersection leaves a pinned piece if of king color, otherwise a possible discovered checker:
<pre>
. r . . x . K .
r-> . . 1 1 1 . . .
<-K . . . . 1 1 . .
& . . . . 1 . . .
</pre>
Two (or more) pieces in-between. Intersection is null:
<pre>
. r . x x . K .
r-> . . 1 1 . . . .
<-K . . . . 1 1 . .
& . . . . . . . .
</pre>
=See also=
* [[Check]]
* [[DirGolem]]
* [[Discovered Check]]
* [[Double Check]]
* [[Pin]]
=Forum Posts=
* [https://www.stmintz.com/ccc/index.php?id=334869 Fast check detection in bitboard engine] by [[Jean-Francois Romang]], [[CCC]], December 10, 2003
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=6064&p=29127 Bitboards and inCheck] by [[Andreas Guettinger]], [[Computer Chess Forums|Winboard Forum]], January 03, 2007
* [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
[[Bitboards|Up one Level]]
