25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * On an empty Board''' '''Single sliding piece attacks''' on the '''otherwise emp..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * On an empty Board'''
'''Single sliding piece attacks''' on the '''otherwise empty board''' or their disjoint subsets on lines or [[Rays|rays]] are that simple than none sliding pieces. We simply use pre-calculated tables for each [[Pieces|piece-type]], line or ray, indexed by square-index. To initialize those tables, one may use a [[Kogge-Stone Algorithm#Fillonanemptyboard|fill approach]] with single populated from-sets, if availably anyway since used elsewhere. While the proposed line-routines here are quite small and cheap, incremental update during an initialization loop has some merits.
The various ray-,line- and piece sets are foundation of further attack calculation considering blocking pieces, for instance to mask the [[Occupancy|occupancy]] of relevant rays. Of course the piece attacks are union-sets of the disjoint line attacks, while the line attacks are unions of the disjoint ray attacks.
<span id="RayAttacks"></span>
=Ray Attacks=
<pre>
northwest north northeast
noWe nort noEa
+7 +8 +9
\ | /
west -1 <- 0 -> +1 east
/ | \
-9 -8 -7
soWe sout soEa
southwest south southeast
</pre>
<span id="SplitRaysFromLine"></span>
==Rays by Line==
Ray-Attacks may be conducted from Line-Attacks by intersection with "positive" and "negative" squares:
<pre>
positiveRay[sq] = lineAttacks[sq] & (0 - 2*singleBit[sq]);
negativeRay[sq] = lineAttacks[sq] & (singleBit[sq] - 1);
</pre>
or with shifts instead of lookups
<pre>
positiveRay[sq] = lineAttacks[sq] & (C64(-2) << sq);
negativeRay[sq] = lineAttacks[sq] & ((C64(1) << sq) - 1);
</pre>
<span id="PositiveRays"></span>
==Positive Rays==
''Remember [[Square Mapping Considerations]].''
===By Lookup===
<pre>
East (+1) Nort (+8) NoEa (+9) NoWe (+7)
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .
. . . R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
</pre>
===Initialization===
North attacks are simple to initialize inside a loop, starting from a1, shifting left:
<pre>
U64 nort = C64(0x0101010101010100);
for (int sq=0; sq < 64; sq++, nort <<= 1)
rayAttacks[sq][Nort] = nort;
</pre>
Similar, but tad trickier for [[ranks]] and [[diagonals]], due to the wraps. For instance the north-east [[Direction|direction]]:
<pre>
U64 noea = C64(0x8040201008040200);
for (int f=0; f < 8; f++, noea = eastOne(noea) {
U64 ne = noea;
for (int r8 = 0; r8 < 8*8; r8 += 8, ne <<= 8)
rayAttacks[r8+f][NoEa] = ne;
}
</pre>
===By Calculation===
Orthogonal positive rays are quite cheap to calculate on the fly. For diagonal rays split the lines as [[On an empty Board#SplitRaysFromLine|mentioned]].
<pre>
U64 eastMaskEx(int sq) {
const U64 one = 1;
return 2*( (one << (sq|7)) - (one << sq) );
}
U64 nortMaskEx(int sq) {
return C64(0x0101010101010100) << sq;
}
</pre>
<span id="NegativeRays"></span>
==Negative Rays==
Remember [[Square Mapping Considerations]].
===By Lookup===
<pre>
West (-1) Sout (-8) SoWe (-9) SoEa (-7)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 1 R . . . . . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .
</pre>
===Initialization===
South attacks are simple to initialize inside a loop, starting from h8, shifting right:
<pre>
U64 sout = C64(0x0080808080808080);
for (int sq=63; sq >= 0; sq--, sout >>= 1)
rayAttacks[sq][Sout] = sout;
</pre>
Similar, but tad trickier for [[ranks]] and [[diagonals]], due to the wraps.
===By Calculation===
Orthogonal negative rays are quite cheap to calculate on the fly. For diagonal rays split the lines as [[On an empty Board#SplitRaysFromLine|mentioned]].
<pre>
U64 westMaskEx(int sq) {
const U64 one = 1;
return (one << sq) - (one << (sq&56));
}
U64 soutMaskEx(int sq) {
return C64(0x0080808080808080) >> (sq ^ 63);
}
</pre>
<span id="LineAttacks"></span>
=Line Attacks=
<pre>
RankAttacks[sq] = EastAttacks[sq] | WestAttacks[sq];
FileAttacks[sq] = NortAttacks[sq] | SoutAttacks[sq];
DiagonalAttacks[sq] = NoEaAttacks[sq] | SoWeAttacks[sq];
AntiDiagonalAttacks[sq] = NoWeAttacks[sq] | SoEaAttacks[sq];
</pre>
===By Lookup===
<pre>
Rank File Diagonal Anti-Diagonal
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .
1 1 1 R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .
</pre>
===By Calculation===
To calculate them on the fly, including...
<pre>
U64 rankMask(int sq) {return C64(0xff) << (sq & 56);}
U64 fileMask(int sq) {return C64(0x0101010101010101) << (sq & 7);}
U64 diagonalMask(int sq) {
const U64 maindia = C64(0x8040201008040201);
int diag =8*(sq & 7) - (sq & 56);
int nort = -diag & ( diag >> 31);
int sout = diag & (-diag >> 31);
return (maindia >> sout) << nort;
}
U64 antiDiagMask(int sq) {
const U64 maindia = C64(0x0102040810204080);
int diag =56- 8*(sq&7) - (sq&56);
int nort = -diag & ( diag >> 31);
int sout = diag & (-diag >> 31);
return (maindia >> sout) << nort;
}
</pre>
... or excluding the square bit:
<pre>
U64 rankMaskEx (int sq) {return (C64(1) << sq) ^ rankMask(sq);}
U64 fileMaskEx (int sq) {return (C64(1) << sq) ^ fileMask(sq);}
U64 diagonalMaskEx(int sq) {return (C64(1) << sq) ^ diagonalMask(sq);}
U64 antiDiagMaskEx(int sq) {return (C64(1) << sq) ^ antiDiagMask(sq);}
</pre>
<span id="PieceAttacks"></span>
=Piece Attacks=
<pre>
RookAttacks[sq] = RankAttacks[sq] | FileAttacks[sq];
BishopAttacks[sq] = DiagonalAttacks[sq] | AntiDiagonalAttacks[sq];
QueenAttacks[sq] = RookAttacks[sq] | BishopAttacks[sq];
</pre>
===By Lookup===
<pre>
Queen
. . . 1 . . . 1
1 . . 1 . . 1 .
. 1 . 1 . 1 . .
Rook . . 1 1 1 . . . Bishop
. . . 1 . . . . 1 1 1 Q 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 R 1 1 1 1 . . . B . . . .
. . . 1 . . . . . . 1 . 1 . . .
. . . 1 . . . . . 1 . . . 1 . .
. . . 1 . . . . 1 . . . . . 1 .
</pre>
===By Calculation===
<pre>
U64 rookMask (int sq) {return rankMask(sq) | fileMask(sq);}
U64 bishopMask (int sq) {return diagonalMask(sq) | antiDiagMask(sq);}
U64 rookMaskEx (int sq) {return rankMask(sq) ^ fileMask(sq);}
U64 bishopMaskEx(int sq) {return diagonalMask(sq) ^ antiDiagMask(sq);}
U64 queenMask (int sq) {return rookMask(sq) | bishopMask(sq);}
U64 queenMaskEx (int sq) {return rookMask(sq) ^ bishopMask(sq);}
</pre>
=See also=
* [[Blockers and Beyond]]
* [[Kogge-Stone Algorithm#Fillonanemptyboard|Fill on an empty Board]] with [[Kogge-Stone Algorithm]]
'''[[Sliding Piece Attacks|Up one Level]]'''
'''Single sliding piece attacks''' on the '''otherwise empty board''' or their disjoint subsets on lines or [[Rays|rays]] are that simple than none sliding pieces. We simply use pre-calculated tables for each [[Pieces|piece-type]], line or ray, indexed by square-index. To initialize those tables, one may use a [[Kogge-Stone Algorithm#Fillonanemptyboard|fill approach]] with single populated from-sets, if availably anyway since used elsewhere. While the proposed line-routines here are quite small and cheap, incremental update during an initialization loop has some merits.
The various ray-,line- and piece sets are foundation of further attack calculation considering blocking pieces, for instance to mask the [[Occupancy|occupancy]] of relevant rays. Of course the piece attacks are union-sets of the disjoint line attacks, while the line attacks are unions of the disjoint ray attacks.
<span id="RayAttacks"></span>
=Ray Attacks=
<pre>
northwest north northeast
noWe nort noEa
+7 +8 +9
\ | /
west -1 <- 0 -> +1 east
/ | \
-9 -8 -7
soWe sout soEa
southwest south southeast
</pre>
<span id="SplitRaysFromLine"></span>
==Rays by Line==
Ray-Attacks may be conducted from Line-Attacks by intersection with "positive" and "negative" squares:
<pre>
positiveRay[sq] = lineAttacks[sq] & (0 - 2*singleBit[sq]);
negativeRay[sq] = lineAttacks[sq] & (singleBit[sq] - 1);
</pre>
or with shifts instead of lookups
<pre>
positiveRay[sq] = lineAttacks[sq] & (C64(-2) << sq);
negativeRay[sq] = lineAttacks[sq] & ((C64(1) << sq) - 1);
</pre>
<span id="PositiveRays"></span>
==Positive Rays==
''Remember [[Square Mapping Considerations]].''
===By Lookup===
<pre>
East (+1) Nort (+8) NoEa (+9) NoWe (+7)
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .
. . . R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
</pre>
===Initialization===
North attacks are simple to initialize inside a loop, starting from a1, shifting left:
<pre>
U64 nort = C64(0x0101010101010100);
for (int sq=0; sq < 64; sq++, nort <<= 1)
rayAttacks[sq][Nort] = nort;
</pre>
Similar, but tad trickier for [[ranks]] and [[diagonals]], due to the wraps. For instance the north-east [[Direction|direction]]:
<pre>
U64 noea = C64(0x8040201008040200);
for (int f=0; f < 8; f++, noea = eastOne(noea) {
U64 ne = noea;
for (int r8 = 0; r8 < 8*8; r8 += 8, ne <<= 8)
rayAttacks[r8+f][NoEa] = ne;
}
</pre>
===By Calculation===
Orthogonal positive rays are quite cheap to calculate on the fly. For diagonal rays split the lines as [[On an empty Board#SplitRaysFromLine|mentioned]].
<pre>
U64 eastMaskEx(int sq) {
const U64 one = 1;
return 2*( (one << (sq|7)) - (one << sq) );
}
U64 nortMaskEx(int sq) {
return C64(0x0101010101010100) << sq;
}
</pre>
<span id="NegativeRays"></span>
==Negative Rays==
Remember [[Square Mapping Considerations]].
===By Lookup===
<pre>
West (-1) Sout (-8) SoWe (-9) SoEa (-7)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 1 1 R . . . . . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .
</pre>
===Initialization===
South attacks are simple to initialize inside a loop, starting from h8, shifting right:
<pre>
U64 sout = C64(0x0080808080808080);
for (int sq=63; sq >= 0; sq--, sout >>= 1)
rayAttacks[sq][Sout] = sout;
</pre>
Similar, but tad trickier for [[ranks]] and [[diagonals]], due to the wraps.
===By Calculation===
Orthogonal negative rays are quite cheap to calculate on the fly. For diagonal rays split the lines as [[On an empty Board#SplitRaysFromLine|mentioned]].
<pre>
U64 westMaskEx(int sq) {
const U64 one = 1;
return (one << sq) - (one << (sq&56));
}
U64 soutMaskEx(int sq) {
return C64(0x0080808080808080) >> (sq ^ 63);
}
</pre>
<span id="LineAttacks"></span>
=Line Attacks=
<pre>
RankAttacks[sq] = EastAttacks[sq] | WestAttacks[sq];
FileAttacks[sq] = NortAttacks[sq] | SoutAttacks[sq];
DiagonalAttacks[sq] = NoEaAttacks[sq] | SoWeAttacks[sq];
AntiDiagonalAttacks[sq] = NoWeAttacks[sq] | SoEaAttacks[sq];
</pre>
===By Lookup===
<pre>
Rank File Diagonal Anti-Diagonal
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .
1 1 1 R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .
</pre>
===By Calculation===
To calculate them on the fly, including...
<pre>
U64 rankMask(int sq) {return C64(0xff) << (sq & 56);}
U64 fileMask(int sq) {return C64(0x0101010101010101) << (sq & 7);}
U64 diagonalMask(int sq) {
const U64 maindia = C64(0x8040201008040201);
int diag =8*(sq & 7) - (sq & 56);
int nort = -diag & ( diag >> 31);
int sout = diag & (-diag >> 31);
return (maindia >> sout) << nort;
}
U64 antiDiagMask(int sq) {
const U64 maindia = C64(0x0102040810204080);
int diag =56- 8*(sq&7) - (sq&56);
int nort = -diag & ( diag >> 31);
int sout = diag & (-diag >> 31);
return (maindia >> sout) << nort;
}
</pre>
... or excluding the square bit:
<pre>
U64 rankMaskEx (int sq) {return (C64(1) << sq) ^ rankMask(sq);}
U64 fileMaskEx (int sq) {return (C64(1) << sq) ^ fileMask(sq);}
U64 diagonalMaskEx(int sq) {return (C64(1) << sq) ^ diagonalMask(sq);}
U64 antiDiagMaskEx(int sq) {return (C64(1) << sq) ^ antiDiagMask(sq);}
</pre>
<span id="PieceAttacks"></span>
=Piece Attacks=
<pre>
RookAttacks[sq] = RankAttacks[sq] | FileAttacks[sq];
BishopAttacks[sq] = DiagonalAttacks[sq] | AntiDiagonalAttacks[sq];
QueenAttacks[sq] = RookAttacks[sq] | BishopAttacks[sq];
</pre>
===By Lookup===
<pre>
Queen
. . . 1 . . . 1
1 . . 1 . . 1 .
. 1 . 1 . 1 . .
Rook . . 1 1 1 . . . Bishop
. . . 1 . . . . 1 1 1 Q 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 R 1 1 1 1 . . . B . . . .
. . . 1 . . . . . . 1 . 1 . . .
. . . 1 . . . . . 1 . . . 1 . .
. . . 1 . . . . 1 . . . . . 1 .
</pre>
===By Calculation===
<pre>
U64 rookMask (int sq) {return rankMask(sq) | fileMask(sq);}
U64 bishopMask (int sq) {return diagonalMask(sq) | antiDiagMask(sq);}
U64 rookMaskEx (int sq) {return rankMask(sq) ^ fileMask(sq);}
U64 bishopMaskEx(int sq) {return diagonalMask(sq) ^ antiDiagMask(sq);}
U64 queenMask (int sq) {return rookMask(sq) | bishopMask(sq);}
U64 queenMaskEx (int sq) {return rookMask(sq) ^ bishopMask(sq);}
</pre>
=See also=
* [[Blockers and Beyond]]
* [[Kogge-Stone Algorithm#Fillonanemptyboard|Fill on an empty Board]] with [[Kogge-Stone Algorithm]]
'''[[Sliding Piece Attacks|Up one Level]]'''
