King Pattern
Home * Board Representation * Bitboards * King Pattern
Moore neighborhood [1] King pattern are about king attacks, some king safety issues and pawn endgame related stuff. There is exactly one king per side - the whole game. Not a big issue, but even if white and black kings are member of the standard bitboard definition one may avoid bitscanning whole the time. Even without explicit piece-lists , one may consider to keep the redundant king-squares incrementally updated during make/ unmake.
by Lookup
Likely we have a the square-index handy, to access a table of precalculated king-attacks.
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
- Checkmate pattern from Wikipedia
- Amon Düül II - Archangel Thunderbird (1971), YouTube Video
References
- ↑ Moore neighborhood from Wikipedia
- ↑ Thanks to Thomas Herges for pointing out a bug if kings are on the eighth rank
- ↑ Flood Fill from Wikipedia
- ↑ Re: algorithm question answer by Steffan Westcott in CCC September 09, 2002