To calculate all eight directions, one can actually do some simple parallel prefix stuff. Rather than to do a union of all eight direction-steps, one first applies the horizontal attacks considering file-wraps. Those up to two bits are then shifted up and down, together with the king-bitboard itself, to get all the other direction bits:
It must not necessarily called with single-populated bitboards, and is base of king path fill algorithms.
King Safety
King Safety is an important evaluation topic. Some bitboard pattern are about to recognize king safety related features. To evaluate those features is a complete other story.
Pawn-Shield Pattern
During the middlegame, the king is encouraged to hide behind own pawn shields. Beside Considering open and half-open files on king's and adjacent files, one idea is to mask potential pawn shield pattern per wing of the king file - and to hash it to an appropriate index range to access tables with precalculated stuff. This mask might be used for kings on f1-h1 or f1-h2:
Assuming we are aware of all taboo squares of the king. That is the union of own pieces with all opposite attacks, then we can simply calculate a move target set by relative complement of the king attacks.
moveTargets = arrKingAttacks[sq] & ~taboo;
If moveTargets is empty - the king has no move. The king might be vulnerable on distant checks from any sliding piecedirection, due to lack of any escape. Otherwise, the king might be vulnerable on distant checks, if escape squares are on one line only - either rank, file, diagonal or anti-diagonal:
if( moveTargets ==0){
dirSet =15;// vulnerable on all lines}else{
dirSet =0;
pattern = moveTargets | sqBBofKing;if( pattern & rankBits[sq]== pattern )
dirSet =1;// vulnerable on rank, e.g. base rankelseif( pattern & fileBits[sq]== pattern )
dirSet =2;// vulnerable on fileelseif( pattern & diagBits[sq]== pattern )
dirSet =4;// vulnerable on diagonalelseif( pattern & antiBits[sq]== pattern )
dirSet =8;// vulnerable on antidiagonal}
Branchless
Branchless in C - since boolean compare result is treated 0 or 1 arithmetically:
Some pawn endgame issues. A set-wise rule of the square from king's point of view. Or does a king have a connected path along safe and empty squares to a certain square?
Set-wise Rule of the Square
Assuming a black-king on g5 - white to move. What is the set of squares, where a king can never catch a white passer? Or the inverse, where can passers might be caught, considering the rule of the square? In this inverse case, where passers may be close enough, there are other aspects to consider like two distant passers, or passer supported by own king - here it is only about races between passers and opponent king. It is about a set-wise view, where the distance to promotion is greater or equal than the distance of the king. We need to consider double pushes from the initial rank though.
Of course we may even mask off the base ranks since pawns can not exist there - but since we intersect with passers anyway, it don't cares.
We need to consider tempo, if black to move, the area of caught grows accordantly:
black king on g5 white passers
btm possibly caught
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . K K K . . . 1 1 1 1 1
. . . . . K K K . . 1 1 1 1 K 1
. . . . . K K K . 1 1 1 1 1 1 1
. . . . . . . . 1 1 1 1 1 1 1 1
. . . . . . . . 1 1 1 1 1 1 1 1
. . . . . . . . 1 1 1 1 1 1 1 1
We can now pre-initialize an array of caught pawn area for each king square, for both black and white king as well as side to move:
U64 arrCaughtableArea[2][2][64]; // [color of king][side to move][square]
unCaughtable = whitePassers & ~arrCaughtableArea[black][white][squareOfBlackKing];
How can the array be initialized, how can we calculate it? That is already some special fill approach. For the mentioned black king, wtm case, we use the rank-distance of the black king to the 8th rank.
Now it is about filling south-west and south-east rank(kingSquare) times, which finally results in the desired set of catchable passers. Special handling is required for the doubles pushes [2]:
A flood fill algorithm, like the one below, starting at the "from" square and stopping if the fill hits the to" square or the fill can't make any more progress. The fill progresses in all directions at once, so should return an answer within a few iterations. Each iteration is pretty fast too, as it just a bunch of shifting and logic operations. And no lookup tables either.
///////////////////////////////////////////////////////////////////////////// Returns true if a path of set bits in 'path' exists that 8-way connect// any set bit in sq1 to any set bit of sq2bool squaresAreConnected(U64 sq1, U64 sq2, U64 path){// With bitboard sq1, do an 8-way flood fill, masking off bits not in// path at every step. Stop when fill reaches any set bit in sq2, or// fill cannot progress any furtherif(!(sq1 &= path)||!(sq2 &= path))returnfalse;// Drop bits not in path// Early exit if sq1 or sq2 not on any pathwhile(!(sq1 & sq2)){
U64 temp = sq1;
sq1 |= eastOne(sq1)| westOne(sq1);// Set all 8 neighbours
sq1 |= soutOne(sq1)| nortOne(sq1);
sq1 &= path;// Drop bits not in pathif(sq1 == temp)returnfalse;// Fill has stopped}returntrue;// Found a good path}
Table of Contents
King Attacks
The King attacks all squares in Moore neighborhood, that is squares with a Chebyshev distance of one.by Lookup
Likely we have a the square-index handy, to access a table of precalculated king-attacks.U64 arrKingAttacks[64]; U64 kingAttacks(enumSquare sq) {return arrKingAttacks[sq];}For instance a king on g2:by Calculation
To calculate all eight directions, one can actually do some simple parallel prefix stuff. Rather than to do a union of all eight direction-steps, one first applies the horizontal attacks considering file-wraps. Those up to two bits are then shifted up and down, together with the king-bitboard itself, to get all the other direction bits:The routine is handy to initialize the kingAttacks arrays:
It must not necessarily called with single-populated bitboards, and is base of king path fill algorithms.
King Safety
King Safety is an important evaluation topic. Some bitboard pattern are about to recognize king safety related features. To evaluate those features is a complete other story.Pawn-Shield Pattern
During the middlegame, the king is encouraged to hide behind own pawn shields. Beside Considering open and half-open files on king's and adjacent files, one idea is to mask potential pawn shield pattern per wing of the king file - and to hash it to an appropriate index range to access tables with precalculated stuff. This mask might be used for kings on f1-h1 or f1-h2:Vulnerable on distant Checks
Assuming we are aware of all taboo squares of the king. That is the union of own pieces with all opposite attacks, then we can simply calculate a move target set by relative complement of the king attacks.If moveTargets is empty - the king has no move. The king might be vulnerable on distant checks from any sliding piece direction, due to lack of any escape. Otherwise, the king might be vulnerable on distant checks, if escape squares are on one line only - either rank, file, diagonal or anti-diagonal:
Branchless
Branchless in C - since boolean compare result is treated 0 or 1 arithmetically:to possibly test later
SSE4
Using the SSE4.1 PCMPEQQ Quadword compare for equality instruction via _mm_cmpeq_epi64 intrinsic, following otherwise SSE2 approach might be applied:King and Pawns
Some pawn endgame issues. A set-wise rule of the square from king's point of view. Or does a king have a connected path along safe and empty squares to a certain square?Set-wise Rule of the Square
Assuming a black-king on g5 - white to move. What is the set of squares, where a king can never catch a white passer? Or the inverse, where can passers might be caught, considering the rule of the square? In this inverse case, where passers may be close enough, there are other aspects to consider like two distant passers, or passer supported by own king - here it is only about races between passers and opponent king. It is about a set-wise view, where the distance to promotion is greater or equal than the distance of the king. We need to consider double pushes from the initial rank though.Of course we may even mask off the base ranks since pawns can not exist there - but since we intersect with passers anyway, it don't cares.
We need to consider tempo, if black to move, the area of caught grows accordantly:
We can now pre-initialize an array of caught pawn area for each king square, for both black and white king as well as side to move:
How can the array be initialized, how can we calculate it? That is already some special fill approach. For the mentioned black king, wtm case, we use the rank-distance of the black king to the 8th rank.
One solution is first expand the king-set distance (3) times, in east and west direction along the rank:
Now it is about filling south-west and south-east rank(kingSquare) times, which finally results in the desired set of catchable passers. Special handling is required for the doubles pushes [2]:
To initialize black to move and white king arrays should not that difficult either - and is left to the ambitious reader.
Flood Fill Algorithms
Answering questions like can a king on a1 reach h8 along this path?The squaresAreConnected flood-fill [3] algorithm was introduced by Steffan Westcott [4].
A flood fill algorithm, like the one below, starting at the "from" square and stopping if the fill hits the to" square or the fill can't make any more progress. The fill progresses in all directions at once, so should return an answer within a few iterations. Each iteration is pretty fast too, as it just a bunch of shifting and logic operations. And no lookup tables either.
See also
External Links
References
What links here?
Up one Level