25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * First Rank Attacks''' The technique of occupancy lookups is base..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * First Rank Attacks'''
The technique of [[Occupancy|occupancy]] lookups is base for [[Rotated Bitboards|Rotated bitboards]], [[Kindergarten Bitboards|Kindergarten bitboards]] and [[Magic Bitboards|Magic bitboards]]. The first [[Ranks|rank]] with an occupancy in the [[Byte|byte]] range serves as teaser to introduce occupancy lookups.
=Introduction to Occupancy Lookup=
==One Byte Only==
Assume we (temporary) reduce the chess-board to one [[Ranks|rank]]. Occupancy bitboard is one [[Byte|byte]] with up to 256 states. A [[Rook|rook]] attack-set from one of the eight [[Squares|squares]] ([[Files|file]]) on this single rank is also only one byte. Thus we can construct an [[Array|array]] of bytes[256][8], indexed by all 256 occupancies and 8 files, to lookup the pre-calculated rank-attack bytes.
<fentt border="a1" style="font-size:36pt">.[N..](R)[.K].</fentt>
Occupancy of the first rank = 01001010B, <span style="color: #ff0000;">Rank-attacks</span> ::= f (e-file, Occupancy) = 01110110B
<pre>
BYTE arrFirstRankAttacks256x8[256][8]; // 2048 Bytes = 2KByte
firstRankAttack = arrFirstRankAttacks256x8[rankOccupancy][squareOnRank];
</pre>
==Overdetermined?==
In fact both indices seem somehow overdetermined, since the rook is already member of occupancy. But rather than to make the redundant rook-bit disappear to use only the remaining seven occupancy bits, with half table size - which is not that cheap and simple either - we better decide to uncouple this items to eventually pass (virtual) rook squares, not actually member of occupancy. We better rely on another property to reduce the table fourfold.
<span id="TheOuterSquares"></span>
==The Outer Squares==
If we think about to the occupancy lookup, we may recognize that the outer squares don't matter. There are no more squares behind. The outer squares are either attacked or not - independent from their occupancy state. We can use the '''six inner bits''' only as lookup-index with two additional cheap instructions.
<pre>
BYTE arrFirstRankAttacks64x8[64][8]; // 512 Bytes = 1/2KByte
firstRankAttack = arrFirstRankAttacks64x8[(rankOccupancy >> 1) & 63][squareOnRank];
</pre>
<span id="AttacksOnAllRanks"></span>
=Attacks on all Ranks=
Since it is simple to shift ranks up and down, the general rank attack getter is already handy.
<pre>
BYTE arrFirstRankAttacks64x8[64*8]; // 512 Bytes = 1/2KByte
U64 rankAttacks(U64 occ, enumSquare sq) {
unsigned int file = sq & 7;
unsigned int rkx8 = sq & 56; // rank * 8
occ = (occ >> rkx8) & 2*63;
U64 attacks = arrFirstRankAttacks64x8[4*occ + file];
return attacks << rkx8;
}
</pre>
The [[Array|array]] is defined one-dimensional, and has to indexed by 8*occ + file. The reason was playing the optimization game and to safe the right shift one, but to scale by 4 instead of 8, which is done by the address calculation unit anyway. This routine may complete the [[Hyperbola Quintessence]].
=See also=
* [[Rotated Bitboards]]
* [[Kindergarten Bitboards]]
* [[Magic Bitboards]]
'''[[Sliding Piece Attacks|Up one Level]]'''
The technique of [[Occupancy|occupancy]] lookups is base for [[Rotated Bitboards|Rotated bitboards]], [[Kindergarten Bitboards|Kindergarten bitboards]] and [[Magic Bitboards|Magic bitboards]]. The first [[Ranks|rank]] with an occupancy in the [[Byte|byte]] range serves as teaser to introduce occupancy lookups.
=Introduction to Occupancy Lookup=
==One Byte Only==
Assume we (temporary) reduce the chess-board to one [[Ranks|rank]]. Occupancy bitboard is one [[Byte|byte]] with up to 256 states. A [[Rook|rook]] attack-set from one of the eight [[Squares|squares]] ([[Files|file]]) on this single rank is also only one byte. Thus we can construct an [[Array|array]] of bytes[256][8], indexed by all 256 occupancies and 8 files, to lookup the pre-calculated rank-attack bytes.
<fentt border="a1" style="font-size:36pt">.[N..](R)[.K].</fentt>
Occupancy of the first rank = 01001010B, <span style="color: #ff0000;">Rank-attacks</span> ::= f (e-file, Occupancy) = 01110110B
<pre>
BYTE arrFirstRankAttacks256x8[256][8]; // 2048 Bytes = 2KByte
firstRankAttack = arrFirstRankAttacks256x8[rankOccupancy][squareOnRank];
</pre>
==Overdetermined?==
In fact both indices seem somehow overdetermined, since the rook is already member of occupancy. But rather than to make the redundant rook-bit disappear to use only the remaining seven occupancy bits, with half table size - which is not that cheap and simple either - we better decide to uncouple this items to eventually pass (virtual) rook squares, not actually member of occupancy. We better rely on another property to reduce the table fourfold.
<span id="TheOuterSquares"></span>
==The Outer Squares==
If we think about to the occupancy lookup, we may recognize that the outer squares don't matter. There are no more squares behind. The outer squares are either attacked or not - independent from their occupancy state. We can use the '''six inner bits''' only as lookup-index with two additional cheap instructions.
<pre>
BYTE arrFirstRankAttacks64x8[64][8]; // 512 Bytes = 1/2KByte
firstRankAttack = arrFirstRankAttacks64x8[(rankOccupancy >> 1) & 63][squareOnRank];
</pre>
<span id="AttacksOnAllRanks"></span>
=Attacks on all Ranks=
Since it is simple to shift ranks up and down, the general rank attack getter is already handy.
<pre>
BYTE arrFirstRankAttacks64x8[64*8]; // 512 Bytes = 1/2KByte
U64 rankAttacks(U64 occ, enumSquare sq) {
unsigned int file = sq & 7;
unsigned int rkx8 = sq & 56; // rank * 8
occ = (occ >> rkx8) & 2*63;
U64 attacks = arrFirstRankAttacks64x8[4*occ + file];
return attacks << rkx8;
}
</pre>
The [[Array|array]] is defined one-dimensional, and has to indexed by 8*occ + file. The reason was playing the optimization game and to safe the right shift one, but to scale by 4 instead of 8, which is done by the address calculation unit anyway. This routine may complete the [[Hyperbola Quintessence]].
=See also=
* [[Rotated Bitboards]]
* [[Kindergarten Bitboards]]
* [[Magic Bitboards]]
'''[[Sliding Piece Attacks|Up one Level]]'''
