25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Shifted Bitboards''' '''Shifted Bitboards''',<br/> an method to determine slid..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Shifted Bitboards'''
'''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/20111012021024/http://mayothi.com/nagaskakichess5.html How NagaSkaki plays chess - The thinking process] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])</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.
=Description=
Shifted Bitboards work ray-wise and uses pre-calculated [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board for each of the eight [[Rays#RayDirections|ray-directions]] for all [[Origin Square|origin squares]],
and [[General Setwise Operations#Intersection|intersects]] one of them with the [[Occupancy|occupancy]] to determine the blockers on the attacking [[Rays|ray]] in question,
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]].
=See also=
* [[Classical Approach]]
* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]
* [[Blockers and Beyond]]
* [[Obstruction Difference]]
=External Links=
* [https://web.archive.org/web/20111012021024/http://mayothi.com/nagaskakichess5.html How NagaSkaki plays chess - The thinking process] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
'''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/20111012021024/http://mayothi.com/nagaskakichess5.html How NagaSkaki plays chess - The thinking process] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])</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.
=Description=
Shifted Bitboards work ray-wise and uses pre-calculated [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board for each of the eight [[Rays#RayDirections|ray-directions]] for all [[Origin Square|origin squares]],
and [[General Setwise Operations#Intersection|intersects]] one of them with the [[Occupancy|occupancy]] to determine the blockers on the attacking [[Rays|ray]] in question,
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]].
=See also=
* [[Classical Approach]]
* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]
* [[Blockers and Beyond]]
* [[Obstruction Difference]]
=External Links=
* [https://web.archive.org/web/20111012021024/http://mayothi.com/nagaskakichess5.html How NagaSkaki plays chess - The thinking process] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
=References=
<references />
'''[[Sliding Piece Attacks|Up one Level]]'''
