Jump to: navigation, search

Shifted Bitboards

415 bytes added, 18:45, 9 June 2021
no edit summary
'''Shifted Bitboards''',<br/>
an method to determine sliding piece attacks introduced by [[Neels Groenewald]] as implemented in his engine [[NagaSkaki]] <ref>[ How NagaSkaki plays chess - The thinking process] ([ Wayback MachineMove generation])</ref>.
The idea is original and does not need huge memory tables. However, with the proposed 56 64-bit operations for either rook and bishop attacks its [[Space-Time Tradeoff|space-time tradeoff]] seems not that advantageous with respect to time, which looks more in the range of set-wise [[Fill Algorithms|fill algorithms]] for multiple sliders, like [[Dumb7Fill|dumb7fill]] or its parallel prefix [[Kogge-Stone Algorithm|Kogge-Stone]] pendant.
quite similar to the [[Classical Approach|Classical Approach]]. While the Classical Approach performs a [[BitScan|bitscan]], either [[BitScan#Bitscanforward|forward]] or [[BitScan#Bitscanreverse|reverse]] to determine the first blocker (if any) for the covered ray-attack [[General Setwise Operations#ExclusiveOr|exclusion]] by a ray-square lookup,
Shifted Bitboards performs a [[Fill Algorithms|fill-like]] [[General Setwise Operations#Union|union]] of all six [[General Setwise Operations#ShiftingBitboards|direction shifts]] of the blocker(s) from one to six (the maximum amount of covered squares behind a blocker), which were then [[General Setwise Operations#XorWithout|excluded]] from the initial [[On an empty Board#RayAttacks|empty board ray-wise attack set]].
U64 rayAttacks[8][64]; // requires initialization
U64 getRightRayAttacks(U64 occupied, enumSquare square) {
U64 attacks = rayAttacks[right][square];
U64 blocker = attacks & occupied;
if ( blocker ) {
blocker = (blocker << 1) | (blocker << 2)
| (blocker << 3) | (blocker << 4)
| (blocker << 5) | (blocker << 6);
attacks ^= (blocker & attacks);
return attacks;
=See also=
=External Links=
* [ How NagaSkaki plays chess - Move generation]* [ How NagaSkaki plays chess - The thinking processMove generation] ([ Wayback Machine], January 04, 2012)* [ How NagaSkaki: A Free plays chess program for Windows] (20032002, NagaSkaki 2.0)
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''

Navigation menu