25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * King Pattern''' FILE:Moore_d.gif|border|right|thumb|link=http://en.wikipedia.org/wiki/File:Moore_d.gif|Mo..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * King Pattern'''
[[FILE:Moore_d.gif|border|right|thumb|link=http://en.wikipedia.org/wiki/File:Moore_d.gif|Moore neighborhood <ref>[https://en.wikipedia.org/wiki/Moore_neighborhood Moore neighborhood from Wikipedia]</ref> ]]
'''King pattern''' are about '''king attacks''', some [[King Safety|king safety]] issues and [[Pawn Endgame|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 [[Bitboard Board-Definition|standard bitboard definition]] one may avoid [[BitScan|bitscanning]] whole the time. Even without explicit [[Piece-Lists|piece-lists]] , one may consider to keep the redundant king-squares [[Incremental Updates|incrementally updated]] during [[Make Move|make]]/[[Unmake Move|unmake]].
<span id="KingAttacks"></span>
=King Attacks=
The King attacks all squares in [https://en.wikipedia.org/wiki/Moore_neighborhood Moore neighborhood], that is squares with a [[Distance|Chebyshev distance]] of one.
==by Lookup==
Likely we have a the square-index handy, to access a table of precalculated king-attacks.
<pre>
U64 arrKingAttacks[64];
U64 kingAttacks(enumSquare sq) {return arrKingAttacks[sq];}
</pre>
For instance a king on g2:
<pre>
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . 1 1 1
. . . . . 1 . 1
. . . . . 1 1 1
</pre>
<span id="byCalculation"></span>
==by Calculation==
To calculate all eight [[Direction|directions]], one can actually do some simple [[Parallel Prefix Algorithms|parallel prefix stuff]]. Rather than to do a union of all eight [[General Setwise Operations#OneStepOnly|direction-steps]], one first applies the [[General Setwise Operations#OneStepOnly|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:
<pre>
U64 kingAttacks(U64 kingSet) {
U64 attacks = eastOne(kingSet) | westOne(kingSet);
kingSet |= attacks;
attacks |= nortOne(kingSet) | soutOne(kingSet);
return attacks;
}
</pre>
The routine is handy to initialize the kingAttacks [[Array|arrays]]:
<pre>
U64 sqBB = 1;
for (int sq = 0; sq < 64; sq++, sqBB <<= 1)
arrKingAttacks[sq] = kingAttacks(sqBB);
</pre>
It must not necessarily called with single-populated bitboards, and is base of [[King Pattern#FloodFillAlgorithms|king path fill algorithms]].
<span id="KingSafety"></span>
=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|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:
<pre>
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . 1 1 1
. . . . . 1 1 1
. . . . . . . .
</pre>
<span id="VulnerableOnDistantChecks"></span>
==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.
<pre>
moveTargets = arrKingAttacks[sq] & ~taboo;
</pre>
If moveTargets is empty - the king has no move. The king might be vulnerable on distant checks from any [[Sliding Pieces|sliding piece]] [[Direction|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:
<pre>
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 rank
else if ( pattern & fileBits[sq] == pattern )
dirSet = 2; // vulnerable on file
else if ( pattern & diagBits[sq] == pattern )
dirSet = 4; // vulnerable on diagonal
else if ( pattern & antiBits[sq] == pattern )
dirSet = 8; // vulnerable on antidiagonal
}
</pre>
===Branchless===
Branchless in C - since boolean compare result is treated 0 or 1 arithmetically:
<pre>
pattern = moveTargets | sqBBofKing;
dirSet = ( pattern & rankBits[sq] == pattern ) * 1;
dirSet += ( pattern & fileBits[sq] == pattern ) * 2;
dirSet += ( pattern & diagBits[sq] == pattern ) * 4;
dirSet += ( pattern & antiBits[sq] == pattern ) * 8;
</pre>
to possibly test later
<pre>
if ( dirSet ) evaluate and look for possible distant mates
</pre>
<span id="SSE4"></span>
===SSE4===
Using the [[SSE4#SSE4.1|SSE4.1]] PCMPEQQ [[Quad Word|Quadword]] compare for equality instruction via [http://msdn.microsoft.com/en-us/library/bb513998.aspx _mm_cmpeq_epi64] intrinsic, following otherwise [[SSE2]] approach might be applied:
<pre>
struct SKingBits {
U64 rankBits;
U64 fileBits;
U64 diagBits;
U64 antiBits;
} XMM_ALIGN kingBits[64];
int dirSet(U64 pattern, int sq)
{
static const U64 XMM_ALIGN weights[4] = {
C64(0x0000000000000001),
C64(0x0000000000000002),
C64(0x0000000000000004),
C64(0x0000000000000008)
};
__m128i x0, x1, x2;
const __m128i* pKB = (__m128i*)(kingBits + sq);
const __m128i* pW = (__m128i*) weights;
x2 = _mm_cvtsi64x_si128 (pattern);
x2 = _mm_unpacklo_epi64 (x2, x2);
x0 = _mm_and_si128 (x2, pKB[0]);
x1 = _mm_and_si128 (x2, pKB[1]);
x0 = _mm_cmpeq_epi64 (x0, x2);
x1 = _mm_cmpeq_epi64 (x1, x2);
x0 = _mm_and_si128 (x0, pW[0]);
x1 = _mm_and_si128 (x1, pW[1]);
x0 = _mm_or_si128 (x0, x1);
x1 = _mm_unpackhi_epi64 (x0, x0);
x0 = _mm_or_si128 (x0, x1);
return _mm_cvtsi128_si32(x0);
}
</pre>
<span id="KingAndPawns"></span>
=King and Pawns=
Some [[Pawn Endgame|pawn endgame]] issues. A set-wise [[Rule of the Square|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?
<span id="SetwiseRuleoftheSquare"></span>
==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 [[Passed Pawn|passer]]? Or the inverse, where can passers might be caught, considering the [[Rule of the Square|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 [[Pawn race|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.
<pre>
black king on g5 white passers double pawn push, need
wtm possibly caught to copy 3rd to 2nd rank
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . K . . . . 1 1 1 K 1 . . . 1 1 1 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 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
</pre>
''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|tempo]], if black to move, the area of caught grows accordantly:
<pre>
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
</pre>
We can now pre-initialize an [[Array|array]] of '''caught pawn area''' for each king square, for both black and white king as well as [[side to move]]:
<pre>
U64 arrCaughtableArea[2][2][64]; // [color of king][side to move][square]
unCaughtable = whitePassers & ~arrCaughtableArea[black][white][squareOfBlackKing];
</pre>
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.
<pre>
distance = rank(kingSquare) ^ 7; // 7 - rank
. . . . 3 . . .
. . . . 2 . . .
. . . . 1 . . .
. . . . K . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
</pre>
One solution is first expand the king-set distance (3) times, in east and west direction along the rank:
<pre>
caughtable = kingBB;
for (i = 0; i < distance; i++)
caughtable |= westOne(caughtable) | eastOne(caughtable);
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 1 1 1 . . . . 1 1 1 1 . . . 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
</pre>
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 <ref>Thanks to Thomas Herges for pointing out a bug if kings are on the eighth rank</ref>:
<pre>
for (i = 0; i < rank(kingSquare)-2; i++)
caughtable |= soutOne(westOne(caughtable) | caughtable | eastOne(caughtable) );
caughtable |= soutOne(caughtable) | 0xff;
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . 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 1 1
. . . . . . . . . 1 1 1 1 1 1 1 | . 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . | . 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . v 1 1 1 1 1 1 1 1
</pre>
To initialize black to move and white king arrays should not that difficult either - and is left to the ambitious reader.
<span id="FloodFillAlgorithms"></span>
==Flood Fill Algorithms==
Answering questions like can a king on a1 reach h8 along this path?
<pre>
. . . . . . 1 T
. . 1 1 1 1 . .
. 1 . . . . . .
. . 1 1 1 1 . .
. . . . . . 1 .
. . . . . . . 1
. . . . . . 1 .
F 1 1 1 1 1 . .
</pre>
The '''squaresAreConnected''' flood-fill <ref>[https://en.wikipedia.org/wiki/Flood_fill Flood Fill from Wikipedia]</ref> algorithm was introduced by [[Steffan Westcott]] <ref>[https://www.stmintz.com/ccc/index.php?id=251180. Re: algorithm question] answer by [[Steffan Westcott]] in [[CCC]] September 09, 2002</ref>.
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.
<pre>
/////////////////////////////////////////////////////////////////////////
//
// 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 sq2
bool 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 further
if (!(sq1 &= path) || !(sq2 &= path)) return false;
// Drop bits not in path
// Early exit if sq1 or sq2 not on any path
while(!(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 path
if (sq1 == temp) return false; // Fill has stopped
}
return true; // Found a good path
}
</pre>
=See also=
* [[All Shortest Paths|All shortest Paths]]
* [[Fill Algorithms]]
* [[Mate at a Glance]]
=External Links=
* [https://en.wikipedia.org/wiki/Checkmate_pattern Checkmate pattern from Wikipedia]
* [[Videos#AmonDuul|Amon Düül II]] - Archangel Thunderbird (1971), [https://en.wikipedia.org/wiki/YouTube YouTube] Video <ref>[https://en.wikipedia.org/wiki/Male_and_Female Male and Female - 1919 American silent adventure/drama film - Wikipedia]</ref>
: {{#evu:https://www.youtube.com/watch?v=_pcla5zyZfA|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
[[FILE:Moore_d.gif|border|right|thumb|link=http://en.wikipedia.org/wiki/File:Moore_d.gif|Moore neighborhood <ref>[https://en.wikipedia.org/wiki/Moore_neighborhood Moore neighborhood from Wikipedia]</ref> ]]
'''King pattern''' are about '''king attacks''', some [[King Safety|king safety]] issues and [[Pawn Endgame|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 [[Bitboard Board-Definition|standard bitboard definition]] one may avoid [[BitScan|bitscanning]] whole the time. Even without explicit [[Piece-Lists|piece-lists]] , one may consider to keep the redundant king-squares [[Incremental Updates|incrementally updated]] during [[Make Move|make]]/[[Unmake Move|unmake]].
<span id="KingAttacks"></span>
=King Attacks=
The King attacks all squares in [https://en.wikipedia.org/wiki/Moore_neighborhood Moore neighborhood], that is squares with a [[Distance|Chebyshev distance]] of one.
==by Lookup==
Likely we have a the square-index handy, to access a table of precalculated king-attacks.
<pre>
U64 arrKingAttacks[64];
U64 kingAttacks(enumSquare sq) {return arrKingAttacks[sq];}
</pre>
For instance a king on g2:
<pre>
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . 1 1 1
. . . . . 1 . 1
. . . . . 1 1 1
</pre>
<span id="byCalculation"></span>
==by Calculation==
To calculate all eight [[Direction|directions]], one can actually do some simple [[Parallel Prefix Algorithms|parallel prefix stuff]]. Rather than to do a union of all eight [[General Setwise Operations#OneStepOnly|direction-steps]], one first applies the [[General Setwise Operations#OneStepOnly|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:
<pre>
U64 kingAttacks(U64 kingSet) {
U64 attacks = eastOne(kingSet) | westOne(kingSet);
kingSet |= attacks;
attacks |= nortOne(kingSet) | soutOne(kingSet);
return attacks;
}
</pre>
The routine is handy to initialize the kingAttacks [[Array|arrays]]:
<pre>
U64 sqBB = 1;
for (int sq = 0; sq < 64; sq++, sqBB <<= 1)
arrKingAttacks[sq] = kingAttacks(sqBB);
</pre>
It must not necessarily called with single-populated bitboards, and is base of [[King Pattern#FloodFillAlgorithms|king path fill algorithms]].
<span id="KingSafety"></span>
=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|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:
<pre>
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . 1 1 1
. . . . . 1 1 1
. . . . . . . .
</pre>
<span id="VulnerableOnDistantChecks"></span>
==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.
<pre>
moveTargets = arrKingAttacks[sq] & ~taboo;
</pre>
If moveTargets is empty - the king has no move. The king might be vulnerable on distant checks from any [[Sliding Pieces|sliding piece]] [[Direction|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:
<pre>
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 rank
else if ( pattern & fileBits[sq] == pattern )
dirSet = 2; // vulnerable on file
else if ( pattern & diagBits[sq] == pattern )
dirSet = 4; // vulnerable on diagonal
else if ( pattern & antiBits[sq] == pattern )
dirSet = 8; // vulnerable on antidiagonal
}
</pre>
===Branchless===
Branchless in C - since boolean compare result is treated 0 or 1 arithmetically:
<pre>
pattern = moveTargets | sqBBofKing;
dirSet = ( pattern & rankBits[sq] == pattern ) * 1;
dirSet += ( pattern & fileBits[sq] == pattern ) * 2;
dirSet += ( pattern & diagBits[sq] == pattern ) * 4;
dirSet += ( pattern & antiBits[sq] == pattern ) * 8;
</pre>
to possibly test later
<pre>
if ( dirSet ) evaluate and look for possible distant mates
</pre>
<span id="SSE4"></span>
===SSE4===
Using the [[SSE4#SSE4.1|SSE4.1]] PCMPEQQ [[Quad Word|Quadword]] compare for equality instruction via [http://msdn.microsoft.com/en-us/library/bb513998.aspx _mm_cmpeq_epi64] intrinsic, following otherwise [[SSE2]] approach might be applied:
<pre>
struct SKingBits {
U64 rankBits;
U64 fileBits;
U64 diagBits;
U64 antiBits;
} XMM_ALIGN kingBits[64];
int dirSet(U64 pattern, int sq)
{
static const U64 XMM_ALIGN weights[4] = {
C64(0x0000000000000001),
C64(0x0000000000000002),
C64(0x0000000000000004),
C64(0x0000000000000008)
};
__m128i x0, x1, x2;
const __m128i* pKB = (__m128i*)(kingBits + sq);
const __m128i* pW = (__m128i*) weights;
x2 = _mm_cvtsi64x_si128 (pattern);
x2 = _mm_unpacklo_epi64 (x2, x2);
x0 = _mm_and_si128 (x2, pKB[0]);
x1 = _mm_and_si128 (x2, pKB[1]);
x0 = _mm_cmpeq_epi64 (x0, x2);
x1 = _mm_cmpeq_epi64 (x1, x2);
x0 = _mm_and_si128 (x0, pW[0]);
x1 = _mm_and_si128 (x1, pW[1]);
x0 = _mm_or_si128 (x0, x1);
x1 = _mm_unpackhi_epi64 (x0, x0);
x0 = _mm_or_si128 (x0, x1);
return _mm_cvtsi128_si32(x0);
}
</pre>
<span id="KingAndPawns"></span>
=King and Pawns=
Some [[Pawn Endgame|pawn endgame]] issues. A set-wise [[Rule of the Square|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?
<span id="SetwiseRuleoftheSquare"></span>
==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 [[Passed Pawn|passer]]? Or the inverse, where can passers might be caught, considering the [[Rule of the Square|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 [[Pawn race|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.
<pre>
black king on g5 white passers double pawn push, need
wtm possibly caught to copy 3rd to 2nd rank
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . K . . . . 1 1 1 K 1 . . . 1 1 1 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 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
</pre>
''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|tempo]], if black to move, the area of caught grows accordantly:
<pre>
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
</pre>
We can now pre-initialize an [[Array|array]] of '''caught pawn area''' for each king square, for both black and white king as well as [[side to move]]:
<pre>
U64 arrCaughtableArea[2][2][64]; // [color of king][side to move][square]
unCaughtable = whitePassers & ~arrCaughtableArea[black][white][squareOfBlackKing];
</pre>
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.
<pre>
distance = rank(kingSquare) ^ 7; // 7 - rank
. . . . 3 . . .
. . . . 2 . . .
. . . . 1 . . .
. . . . K . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
</pre>
One solution is first expand the king-set distance (3) times, in east and west direction along the rank:
<pre>
caughtable = kingBB;
for (i = 0; i < distance; i++)
caughtable |= westOne(caughtable) | eastOne(caughtable);
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . 1 1 1 . . . . 1 1 1 1 . . . 1 1 1 1 1
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
</pre>
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 <ref>Thanks to Thomas Herges for pointing out a bug if kings are on the eighth rank</ref>:
<pre>
for (i = 0; i < rank(kingSquare)-2; i++)
caughtable |= soutOne(westOne(caughtable) | caughtable | eastOne(caughtable) );
caughtable |= soutOne(caughtable) | 0xff;
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . 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 1 1
. . . . . . . . . 1 1 1 1 1 1 1 | . 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . | . 1 1 1 1 1 1 1
. . . . . . . . . . . . . . . . v 1 1 1 1 1 1 1 1
</pre>
To initialize black to move and white king arrays should not that difficult either - and is left to the ambitious reader.
<span id="FloodFillAlgorithms"></span>
==Flood Fill Algorithms==
Answering questions like can a king on a1 reach h8 along this path?
<pre>
. . . . . . 1 T
. . 1 1 1 1 . .
. 1 . . . . . .
. . 1 1 1 1 . .
. . . . . . 1 .
. . . . . . . 1
. . . . . . 1 .
F 1 1 1 1 1 . .
</pre>
The '''squaresAreConnected''' flood-fill <ref>[https://en.wikipedia.org/wiki/Flood_fill Flood Fill from Wikipedia]</ref> algorithm was introduced by [[Steffan Westcott]] <ref>[https://www.stmintz.com/ccc/index.php?id=251180. Re: algorithm question] answer by [[Steffan Westcott]] in [[CCC]] September 09, 2002</ref>.
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.
<pre>
/////////////////////////////////////////////////////////////////////////
//
// 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 sq2
bool 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 further
if (!(sq1 &= path) || !(sq2 &= path)) return false;
// Drop bits not in path
// Early exit if sq1 or sq2 not on any path
while(!(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 path
if (sq1 == temp) return false; // Fill has stopped
}
return true; // Found a good path
}
</pre>
=See also=
* [[All Shortest Paths|All shortest Paths]]
* [[Fill Algorithms]]
* [[Mate at a Glance]]
=External Links=
* [https://en.wikipedia.org/wiki/Checkmate_pattern Checkmate pattern from Wikipedia]
* [[Videos#AmonDuul|Amon Düül II]] - Archangel Thunderbird (1971), [https://en.wikipedia.org/wiki/YouTube YouTube] Video <ref>[https://en.wikipedia.org/wiki/Male_and_Female Male and Female - 1919 American silent adventure/drama film - Wikipedia]</ref>
: {{#evu:https://www.youtube.com/watch?v=_pcla5zyZfA|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
