25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Fill by Subtraction''' Performing the Subtracting a Rook from a blocking Piec..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Fill by Subtraction'''
Performing the [[Subtracting a Rook from a blocking Piece|o^(o-2r) - trick ]] in a [[SIMD and SWAR Techniques|SWAR-wise]] fashion with bytes (ranks), saves some instructions compared to [[Kogge-Stone Algorithm|Kogge-Stone]].
[[include page="MappingHint"]]
Unfortunately it only works in positive horizontal direction, so the possible savings are marginal, despite even less generalization of handling one out of eight cases with a different code pattern.
=Source Code=
<pre>
U64 eastAttacks(U64 rooks, U64 empty) {
const U64 H = 0x8080808080808080;
U64 occInclRook = rooks | ~empty | H;
U64 occExclRook = (rooks &= ~H) ^ occInclRook;
U64 rookAttacks = (occExclRook - rooks) ^ occInclRook;
return rookAttacks;
}
</pre>
Even more with vectors of two bitboards and [[SSE2#EastAttacks|SSE2-instructions]].
=Comparison with Kogge-Stone=
For comparison the [[Kogge-Stone Algorithm|Kogge-Stone]] attack-getter. It gives an idea how to implement a [[Parallel Prefix Algorithms#KoggeStoneAdder|Kogge-Stone Adder]] with bitwise operations only.
<pre>
U64 eastAttacks(U64 rooks, U64 empty) {
empty &= notAFile;
rooks |= empty & (rooks << 1);
empty &= (empty << 1);
rooks |= empty & (rooks << 2);
empty &= (empty << 2);
rooks |= empty & (rooks << 4);
return notAFile& (rooks << 1);
}
</pre>
=See also=
* [[Parallel Prefix Algorithms#KoggeStoneAdder|Add/Sub versus Attacks]] from [[Parallel Prefix Algorithms]]
* [[Fill Algorithms]]
* [[SSE2#EastAttacks|Fill by Subtraction]] with [[SSE2|SSE2-instructions]]
* [[Kogge-Stone Algorithm]]
* [[Pieces versus Directions]]
* [[SIMD and SWAR Techniques]]
* [[Subtracting a Rook from a blocking Piece]]
'''[[Sliding Piece Attacks|Up one Level]]'''
Performing the [[Subtracting a Rook from a blocking Piece|o^(o-2r) - trick ]] in a [[SIMD and SWAR Techniques|SWAR-wise]] fashion with bytes (ranks), saves some instructions compared to [[Kogge-Stone Algorithm|Kogge-Stone]].
[[include page="MappingHint"]]
Unfortunately it only works in positive horizontal direction, so the possible savings are marginal, despite even less generalization of handling one out of eight cases with a different code pattern.
=Source Code=
<pre>
U64 eastAttacks(U64 rooks, U64 empty) {
const U64 H = 0x8080808080808080;
U64 occInclRook = rooks | ~empty | H;
U64 occExclRook = (rooks &= ~H) ^ occInclRook;
U64 rookAttacks = (occExclRook - rooks) ^ occInclRook;
return rookAttacks;
}
</pre>
Even more with vectors of two bitboards and [[SSE2#EastAttacks|SSE2-instructions]].
=Comparison with Kogge-Stone=
For comparison the [[Kogge-Stone Algorithm|Kogge-Stone]] attack-getter. It gives an idea how to implement a [[Parallel Prefix Algorithms#KoggeStoneAdder|Kogge-Stone Adder]] with bitwise operations only.
<pre>
U64 eastAttacks(U64 rooks, U64 empty) {
empty &= notAFile;
rooks |= empty & (rooks << 1);
empty &= (empty << 1);
rooks |= empty & (rooks << 2);
empty &= (empty << 2);
rooks |= empty & (rooks << 4);
return notAFile& (rooks << 1);
}
</pre>
=See also=
* [[Parallel Prefix Algorithms#KoggeStoneAdder|Add/Sub versus Attacks]] from [[Parallel Prefix Algorithms]]
* [[Fill Algorithms]]
* [[SSE2#EastAttacks|Fill by Subtraction]] with [[SSE2|SSE2-instructions]]
* [[Kogge-Stone Algorithm]]
* [[Pieces versus Directions]]
* [[SIMD and SWAR Techniques]]
* [[Subtracting a Rook from a blocking Piece]]
'''[[Sliding Piece Attacks|Up one Level]]'''
