Difference between revisions of "Shifted Bitboards"

From Chessprogramming wiki
Jump to: navigation, search
 
(One intermediate revision by the same user not shown)
Line 2: Line 2:
  
 
'''Shifted Bitboards''',<br/>
 
'''Shifted Bitboards''',<br/>
an  method to determine sliding piece attacks introduced by [[Neels Groenewald]] as implemented in his engine [[NagaSkaki]] <ref>[https://web.archive.org/web/20120104163142/http://www.mayothi.com/nagaskakichess6.html How NagaSkaki plays chess - Move generation] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], January 04, 2012)</ref>.
+
an  method to determine sliding piece attacks introduced by [[Neels Groenewald]] as implemented in his engine [[NagaSkaki]] <ref>[https://mayothi.com/nagaskakichess6.html How NagaSkaki plays chess - Move 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.
 
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.
  
Line 10: Line 10:
 
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,  
 
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]].  
 
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]].  
 +
 +
<pre>
 +
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;
 +
}
 +
</pre>
  
 
=See also=
 
=See also=
Line 18: Line 34:
  
 
=External Links=
 
=External Links=
 +
* [https://mayothi.com/nagaskakichess6.html How NagaSkaki plays chess - Move generation]
 
* [https://web.archive.org/web/20120104163142/http://www.mayothi.com/nagaskakichess6.html How NagaSkaki plays chess - Move generation] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], January 04, 2012)
 
* [https://web.archive.org/web/20120104163142/http://www.mayothi.com/nagaskakichess6.html How NagaSkaki plays chess - Move generation] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine], January 04, 2012)
 
* [http://mysite.mweb.co.za/residents/lollapot/nagaskaki_chess.html How NagaSkaki plays chess] (2002, NagaSkaki 2.0)
 
* [http://mysite.mweb.co.za/residents/lollapot/nagaskaki_chess.html How NagaSkaki plays chess] (2002, NagaSkaki 2.0)

Latest revision as of 18:45, 9 June 2021

Home * Board Representation * Bitboards * Sliding Piece Attacks * Shifted Bitboards

Shifted Bitboards,
an method to determine sliding piece attacks introduced by Neels Groenewald as implemented in his engine NagaSkaki [1]. 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 seems not that advantageous with respect to time, which looks more in the range of set-wise fill algorithms for multiple sliders, like dumb7fill or its parallel prefix Kogge-Stone pendant.

Description

Shifted Bitboards work ray-wise and uses pre-calculated ray-attacks on the otherwise empty board for each of the eight ray-directions for all origin squares, and intersects one of them with the occupancy to determine the blockers on the attacking ray in question, quite similar to the Classical Approach. While the Classical Approach performs a bitscan, either forward or reverse to determine the first blocker (if any) for the covered ray-attack exclusion by a ray-square lookup, Shifted Bitboards performs a fill-like union of all six direction shifts of the blocker(s) from one to six (the maximum amount of covered squares behind a blocker), which were then excluded from the initial 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

References

Up one Level