25,161
edits
Changes
Created page with "'''Home * Board Representation * Bitboards * Pieces versus Directions''' Despite the generation of moves to one Target Square|targ..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * Pieces versus Directions'''
Despite the [[Move Generation|generation of moves]] to one [[Target Square|target square]] by [[Pieces|pieces]] from different [[Direction|directions]] as mentioned [[Square Attacked By]], there are two approaches to [[Move Generation|generate]] [[Moves|moves]] in an [[Origin Square|origin centric]] manner to determine a set of distinct target squares. The classical approach, also applied in [[Mailbox]] [[Array|array]] representation, is to generate [[Attacks|attacks]] and moves piece by piece. Alternately there are set-wise approaches, to determine distinct direction attacks for sets of multiple pieces and [[Pawn|pawns]]. [[Sliding Pieces|Sliding pieces]] rely on [[Dumb7Fill|dumb7fill]], [[Kogge-Stone Algorithm|kogge-stone algorithm]] or [[Fill by Subtraction|fill by subtraction]].
<span id="PieceByPiece"></span>
=Piece by Piece=
In general there are lookup techniques to determine attack- or move-target sets for each individual [[Pawn|pawn]] or [[Pieces|piece]], indexed by [[BitScan|bitscanned]] square and for the sliders by occupancy. Each piece-wise attack covers all their inherited [[Direction|ray- or knight directions]]. This classical approach traverses all pieces and generates attack sets and move sets by following techniques:
* [[Pawn Push]]
* [[Pawn Attacks (Bitboards)#AttacksOfaSinglePawn|Attacks of a Single Pawn]]
* [[Knight Pattern#ByLookup|Knight Attacks by Lookup]]
* [[King Pattern#KingAttacks|King Attacks by Lookup]]
* [[Sliding Piece Attacks#SingleSlidingPieceAttacks|Single Sliding Piece Attacks]]
As usual, [[Captures|captures]] are determined by [[General Setwise Operations#Intersection|intersection]] of attacks with opponent pieces or [[En passant|en passant]] target, while all other attacks or push targets of empty squares are [[Quiet Moves|quiet moves]].
<pre>
for all pieces {
generateMovetargets(piece);
for all capture targets
generate captures (move or capture list)
for all empty square targets
generate quite moves (move list)
}
</pre>
<span id="DirectionWise"></span>
=Directions=
The [[Direction|direction-wise]] approach relies on following set-wise techniques to determine move-targets. As usual, [[Captures|captures]] are determined by [[General Setwise Operations#Intersection|intersection]] of attacks with opponent pieces or [[En passant|en passant]] target, while all other attacks or push targets of empty squares are [[Quiet Moves|quiet moves]].
* [[Pawn Pushes (Bitboards)#PawnPushSetwise|Pushes set-wise]]
* [[Pawn Attacks (Bitboards)#PawnAttacks|Pawn Attacks set-wise]]
* [[Knight Pattern#MultipleKnightAttacks|Multiple Knight Attacks]]
* [[King Pattern#byCalculation|King Attacks by Calculation]] with [[General Setwise Operations#OneStepOnly|Direction-Steps]]
* [[Sliding Piece Attacks#Multiple|Multiple Sliding Pieces]]
For [[Move Generation|move generation]] purpose one may store target-sets of different piece types per direction. Thus, 16 bitboards as a kind of unsorted [[Move List|move list]]. Each [[Target Square|target square]] in each ray-direction set has an unique one-to-one relation to it's [[Origin Square|source square]].
<pre>
for all 16 ray- and knight directions {
generateMovetargets(dirtargets[dir], dir);
}
</pre>
Likely this loop is unrolled - at least for the ray-attacks - where pawns, kings, bishops, rooks or queens may involved. See the proposal of [[DirGolem]] for a branch-less direction-wise generation of [[Legal Move|legal moves]].
An incremental [https://en.wikipedia.org/wiki/Finite_state_machine finite state machine] - move-getter may scan and reset the target squares per direction. For distant source squares of [[Sliding Pieces|sliding pieces]], one may [[General Setwise Operations#Intersection|intersect]] the [[On an empty Board#RayAttacks|ray-wise masks]] per direction and [[Target Square|target-square]] with the occupancy - to use either [[BitScan|bitscan]] [[BitScan#Bitscanreverse|reverse]] or [[BitScan#Bitscanforward|forward]] for the [[On an empty Board#PositiveRays|positive]] or [[On an empty Board#NegativeRays|negative]] directions - similar to the [[Classical Approach|classical approach]], except one don't needs the if (blocker) - condition, which is always true. However, one may delay determining the source square and moving piece until [[Make Move|make move]] time, and to [[Encoding Moves|encode moves]] uniquely with target square (six bits) and direction (4 bits).
Alternatively, one may process a ray in one run, to bitscan the most farthest [[Target Square|destination square]] from one distinct direction, i.e. bitscan reverse of positive ray attacks, and to loop over all intermediate targets by adding offsets until the source square is arrived. The below loop considers that move-target bits may already reset due to staged move generation, i.e. [[Hash Move|hash move]] or [[Killer Move|killer moves]] may already tried. Therefor the extra condition with ''testAndResetBit'' <ref>[http://msdn.microsoft.com/en-us/library/hd0hzyf8%28VS.100%29.aspx _bittestandreset, _bittestandreset64]</ref>.
<pre>
while ( northMoveTargets )
{
targetSquare = bitScanReverse( northMoveTargets );
sourceSquare = bitScanReverse( rayAttacks[sout][targetSquare] & occupied);
storeMoveOrCapture( sourceSquare, targetSquare);
resetBit (northMoveTargets, targetSquare);
targetSquare -= 8;
while ( targetSquare > sourceSquare) {
if ( testAndResetBit (northMoveTargets, targetSquare) )
storeMove( sourceSquare, targetSquare);
targetSquare -= 8;
}
}
</pre>
=Hybrid=
One may combine both approaches with usual [[Move List|move lists]]. For instance direction-wise attacks for all pawns, piece-wise attacks for none-pawns. The target set-of pawn-captures should be considered early, since this are winning or at least equal captures.
=See also=
* [[Bitboard Serialization]]
* [[BitScan]]
* [[Classical Approach]] of [[Sliding Piece Attacks]]
* [[DirGolem]]
* [[Move Generation]]
* [[Square Attacked By]]
=External Links=
* [[Videos#MilesDavis|Miles Davis]] - [https://en.wikipedia.org/wiki/A_Different_Kind_of_Blue Call It Anything], [https://en.wikipedia.org/wiki/Isle_of_Wight_Festival_1970 Isle of Wight Festival], August 29, 1970, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#MilesDavis|Miles Davis]], [https://en.wikipedia.org/wiki/Gary_Bartz Gary Bartz], [[Videos#ChickCorea|Chick Corea]], [[Videos#KeithJarrett|Keith Jarrett]], [[Videos#DaveHolland|Dave Holland]], [[Videos#JackDeJohnette|Jack DeJohnette]], [[Videos#AirtoMoreira|Airto Moreira]] <ref>[https://answers.yahoo.com/question/index?qid=20101214072119AASF0pn Does anyone know the name of the instrument Airto Moreira uses during the Isle of Wight Festival (1970)?] | [https://en.wikipedia.org/wiki/Yahoo!_Answers Yahoo! Answers]</ref> <ref>[https://en.wikipedia.org/wiki/Cu%C3%ADca Cuíca from Wikipedia]</ref>
: [https://en.wikipedia.org/wiki/Bitches_Brew_Live#Track_listing Directions] ([[Videos#JoeZawinul|Joe Zawinul]]) 0:00 (7:30), [https://en.wikipedia.org/wiki/Bitches_Brew Bitches Brew] 7:30 (10:09), [https://en.wikipedia.org/wiki/Live_at_the_Fillmore_East,_March_7,_1970:_It%27s_About_that_Time It's About That Time] 17:39 (6:17),
: [https://en.wikipedia.org/wiki/Bitches_Brew#Track_listing Sanctuary] ([[Videos#WayneShorter|Wayne Shorter]]) 23:56 (1:10), [https://en.wikipedia.org/wiki/Bitches_Brew Spanish Key] 25:06 (8:15), [https://en.wikipedia.org/wiki/Bitches_Brew_Live The Theme] 33:21 (2:10)
: {{#evu:https://www.youtube.com/watch?v=qyJooHmRcdc|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
Despite the [[Move Generation|generation of moves]] to one [[Target Square|target square]] by [[Pieces|pieces]] from different [[Direction|directions]] as mentioned [[Square Attacked By]], there are two approaches to [[Move Generation|generate]] [[Moves|moves]] in an [[Origin Square|origin centric]] manner to determine a set of distinct target squares. The classical approach, also applied in [[Mailbox]] [[Array|array]] representation, is to generate [[Attacks|attacks]] and moves piece by piece. Alternately there are set-wise approaches, to determine distinct direction attacks for sets of multiple pieces and [[Pawn|pawns]]. [[Sliding Pieces|Sliding pieces]] rely on [[Dumb7Fill|dumb7fill]], [[Kogge-Stone Algorithm|kogge-stone algorithm]] or [[Fill by Subtraction|fill by subtraction]].
<span id="PieceByPiece"></span>
=Piece by Piece=
In general there are lookup techniques to determine attack- or move-target sets for each individual [[Pawn|pawn]] or [[Pieces|piece]], indexed by [[BitScan|bitscanned]] square and for the sliders by occupancy. Each piece-wise attack covers all their inherited [[Direction|ray- or knight directions]]. This classical approach traverses all pieces and generates attack sets and move sets by following techniques:
* [[Pawn Push]]
* [[Pawn Attacks (Bitboards)#AttacksOfaSinglePawn|Attacks of a Single Pawn]]
* [[Knight Pattern#ByLookup|Knight Attacks by Lookup]]
* [[King Pattern#KingAttacks|King Attacks by Lookup]]
* [[Sliding Piece Attacks#SingleSlidingPieceAttacks|Single Sliding Piece Attacks]]
As usual, [[Captures|captures]] are determined by [[General Setwise Operations#Intersection|intersection]] of attacks with opponent pieces or [[En passant|en passant]] target, while all other attacks or push targets of empty squares are [[Quiet Moves|quiet moves]].
<pre>
for all pieces {
generateMovetargets(piece);
for all capture targets
generate captures (move or capture list)
for all empty square targets
generate quite moves (move list)
}
</pre>
<span id="DirectionWise"></span>
=Directions=
The [[Direction|direction-wise]] approach relies on following set-wise techniques to determine move-targets. As usual, [[Captures|captures]] are determined by [[General Setwise Operations#Intersection|intersection]] of attacks with opponent pieces or [[En passant|en passant]] target, while all other attacks or push targets of empty squares are [[Quiet Moves|quiet moves]].
* [[Pawn Pushes (Bitboards)#PawnPushSetwise|Pushes set-wise]]
* [[Pawn Attacks (Bitboards)#PawnAttacks|Pawn Attacks set-wise]]
* [[Knight Pattern#MultipleKnightAttacks|Multiple Knight Attacks]]
* [[King Pattern#byCalculation|King Attacks by Calculation]] with [[General Setwise Operations#OneStepOnly|Direction-Steps]]
* [[Sliding Piece Attacks#Multiple|Multiple Sliding Pieces]]
For [[Move Generation|move generation]] purpose one may store target-sets of different piece types per direction. Thus, 16 bitboards as a kind of unsorted [[Move List|move list]]. Each [[Target Square|target square]] in each ray-direction set has an unique one-to-one relation to it's [[Origin Square|source square]].
<pre>
for all 16 ray- and knight directions {
generateMovetargets(dirtargets[dir], dir);
}
</pre>
Likely this loop is unrolled - at least for the ray-attacks - where pawns, kings, bishops, rooks or queens may involved. See the proposal of [[DirGolem]] for a branch-less direction-wise generation of [[Legal Move|legal moves]].
An incremental [https://en.wikipedia.org/wiki/Finite_state_machine finite state machine] - move-getter may scan and reset the target squares per direction. For distant source squares of [[Sliding Pieces|sliding pieces]], one may [[General Setwise Operations#Intersection|intersect]] the [[On an empty Board#RayAttacks|ray-wise masks]] per direction and [[Target Square|target-square]] with the occupancy - to use either [[BitScan|bitscan]] [[BitScan#Bitscanreverse|reverse]] or [[BitScan#Bitscanforward|forward]] for the [[On an empty Board#PositiveRays|positive]] or [[On an empty Board#NegativeRays|negative]] directions - similar to the [[Classical Approach|classical approach]], except one don't needs the if (blocker) - condition, which is always true. However, one may delay determining the source square and moving piece until [[Make Move|make move]] time, and to [[Encoding Moves|encode moves]] uniquely with target square (six bits) and direction (4 bits).
Alternatively, one may process a ray in one run, to bitscan the most farthest [[Target Square|destination square]] from one distinct direction, i.e. bitscan reverse of positive ray attacks, and to loop over all intermediate targets by adding offsets until the source square is arrived. The below loop considers that move-target bits may already reset due to staged move generation, i.e. [[Hash Move|hash move]] or [[Killer Move|killer moves]] may already tried. Therefor the extra condition with ''testAndResetBit'' <ref>[http://msdn.microsoft.com/en-us/library/hd0hzyf8%28VS.100%29.aspx _bittestandreset, _bittestandreset64]</ref>.
<pre>
while ( northMoveTargets )
{
targetSquare = bitScanReverse( northMoveTargets );
sourceSquare = bitScanReverse( rayAttacks[sout][targetSquare] & occupied);
storeMoveOrCapture( sourceSquare, targetSquare);
resetBit (northMoveTargets, targetSquare);
targetSquare -= 8;
while ( targetSquare > sourceSquare) {
if ( testAndResetBit (northMoveTargets, targetSquare) )
storeMove( sourceSquare, targetSquare);
targetSquare -= 8;
}
}
</pre>
=Hybrid=
One may combine both approaches with usual [[Move List|move lists]]. For instance direction-wise attacks for all pawns, piece-wise attacks for none-pawns. The target set-of pawn-captures should be considered early, since this are winning or at least equal captures.
=See also=
* [[Bitboard Serialization]]
* [[BitScan]]
* [[Classical Approach]] of [[Sliding Piece Attacks]]
* [[DirGolem]]
* [[Move Generation]]
* [[Square Attacked By]]
=External Links=
* [[Videos#MilesDavis|Miles Davis]] - [https://en.wikipedia.org/wiki/A_Different_Kind_of_Blue Call It Anything], [https://en.wikipedia.org/wiki/Isle_of_Wight_Festival_1970 Isle of Wight Festival], August 29, 1970, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: [[Videos#MilesDavis|Miles Davis]], [https://en.wikipedia.org/wiki/Gary_Bartz Gary Bartz], [[Videos#ChickCorea|Chick Corea]], [[Videos#KeithJarrett|Keith Jarrett]], [[Videos#DaveHolland|Dave Holland]], [[Videos#JackDeJohnette|Jack DeJohnette]], [[Videos#AirtoMoreira|Airto Moreira]] <ref>[https://answers.yahoo.com/question/index?qid=20101214072119AASF0pn Does anyone know the name of the instrument Airto Moreira uses during the Isle of Wight Festival (1970)?] | [https://en.wikipedia.org/wiki/Yahoo!_Answers Yahoo! Answers]</ref> <ref>[https://en.wikipedia.org/wiki/Cu%C3%ADca Cuíca from Wikipedia]</ref>
: [https://en.wikipedia.org/wiki/Bitches_Brew_Live#Track_listing Directions] ([[Videos#JoeZawinul|Joe Zawinul]]) 0:00 (7:30), [https://en.wikipedia.org/wiki/Bitches_Brew Bitches Brew] 7:30 (10:09), [https://en.wikipedia.org/wiki/Live_at_the_Fillmore_East,_March_7,_1970:_It%27s_About_that_Time It's About That Time] 17:39 (6:17),
: [https://en.wikipedia.org/wiki/Bitches_Brew#Track_listing Sanctuary] ([[Videos#WayneShorter|Wayne Shorter]]) 23:56 (1:10), [https://en.wikipedia.org/wiki/Bitches_Brew Spanish Key] 25:06 (8:15), [https://en.wikipedia.org/wiki/Bitches_Brew_Live The Theme] 33:21 (2:10)
: {{#evu:https://www.youtube.com/watch?v=qyJooHmRcdc|alignment=left|valignment=top}}
=References=
<references />
'''[[Bitboards|Up one Level]]'''
