25,161
edits
Changes
Created page with "'''Home * Board Representation * Move Generation * DirGolem''' FILE:Golem 1920 Poster.jpg|border|right|thumb|The Golem <ref>[https://en.wikipedia.org/..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Move Generation]] * DirGolem'''
[[FILE:Golem 1920 Poster.jpg|border|right|thumb|The Golem <ref>[https://en.wikipedia.org/wiki/The_Golem:_How_He_Came_into_the_World The Golem: How He Came Into the World, from Wikipedia]</ref> ]]
'''DirGolem''',<br/>
Direction-wise Generation of [[Legal Move|Legal Moves]], is best done with vectors of [[Bitboards|bitboards]] applying [[AltiVec]], [[SSE2]], [[AVX2]] or similar [[SIMD and SWAR Techniques|SIMD architectures]] with appropriate register sets. Legal moves are stored as target-bitboards for all 16 [[Direction#MoveDirections|move directions]] as a kind of unsorted [[Move List|move list]] inside the state of a [[Node|node]]. That are four orthogonal directions with rook-, queen- and king-moves including [[Castling|castling]] and vertical [[Pawn Push|pawn-pushes]], four diagonal directions with bishop-, queen- and king-moves and pawn-captures including [[En passant|en passant]], and eight knight directions. Each [[Target Square|target square]] of each direction set has an unique one-to-one relation to it's [[Origin Square|source square]].
=Prospect=
To get the idea, the following description with scalar [[Cpp|C++]] code intended as pseudo code, is a rough translation of [[HansDamf|HansDamf's]] intrinsic SSE2 code by [[Gerd Isenberg]]. It assumes White to move within a [[Color Flipping|color flipper]] approach. More information for a set-wise [[Static Exchange Evaluation|SEE]], determining [[Check|check]] giving moves including [[Discovered Check|discovered checks]], etc. may be collected and considered. There are zillions of implementation nuances to utilize up to 16 128-bit XMM-, 16 256-bit YMM (AVX2), or even [[AVX-512]] 32 512-bit ZMM-SIMD registers <ref>[http://software.intel.com/en-us/blogs/2013/avx-512-instructions AVX-512 instructions | Intel® Developer Zone], by [http://software.intel.com/en-us/user/335550 James Reinders], July 23, 2013</ref>. The generation is completely branch-less, does not use huge lookup tables, and is intended to hide the latency of a [https://en.wikipedia.org/wiki/Prefetching prefetched] [[Transposition Table|TT]] probe. However, picking any moves or move proposals like [[Hash Move|hash]]- or [[Killer Move|killer moves]] from that list is more expensive and is typically done by a [https://en.wikipedia.org/wiki/Finite-state_machine finite state machine] to ensure proper [[Move Ordering|move ordering]] considering [[MVV-LVA]], [[Hanging Piece|hanging pieces]], etc., as mentioned in [[Pieces versus Directions#DirectionWise|pieces versus directions]].
=Basics=
* [[King Pattern#byCalculation|King Attacks by Calculation]]
* [[Knight Pattern#MultipleKnightAttacks|Multiple Knight Attacks]]
* [[Sliding Piece Attacks#Multiple|Multiple Sliding Pieces]]
* [[General Setwise Operations#OneStepOnly|One Step Only]]
* [[Checks and Pinned Pieces (Bitboards)#OppositeRay|Opposite Ray-Directions]]
* [[Pawn Attacks (Bitboards)#PawnAttacks|Pawn Attacks set-wise]]
* [[Pawn Pushes (Bitboards)#PawnPushSetwise|Pawn Pushes set-wise]]
* [[Pieces versus Directions]]
{{MappingHint}}
=Move Target Sets=
To determine white [[Pin#AbsolutePin|absolutely pinned pieces]] and squares attacked by black pieces, pawns, and king, taboo for the white king, black attacks are generated in a first phase. Those attacks are also utilized to detect whether the own king is in [[Check|check]]. Aggregated collected information is then used in a second phase of legal move target generation.
==Black Attacks==
===Sliders & Super King===
First, all black sliding attacks are generated by [[Dumb7Fill|Dumb7]]- or [[Kogge-Stone Algorithm|Kogge-Stone fill]], unrolled for all eight [[Direction#RayDirections|ray directions]], to aggregate them into a white king taboo bitboard, and to determine and keep line-wise [[Square Attacked By#InBetween|in-between]] bitboards by intersection with [[Checks and Pinned Pieces (Bitboards)#OppositeRay|opposite ray-direction]] attacks of the white king as sliding super piece, best generated by the [[Classical Approach|classical approach]], or alternatively along with the sliding pieces itself as additional SIMD data element processing two opponent fill direction in one run.
<span id="Xray"></span>The occupancy for the black sliding attacks has the white king excluded, so that in case of check by a sliding piece the king is [[X-ray|x-rayed]] to later avoid king moves to otherwise non attacked squares. The in-between sets intersected with own pieces leave [[Pin#AbsolutePin|pinned pieces]], but are also handy to determine an interposing block target set in case of distant sliding checks. In total, seven bitboards are processed as used in the second part of the routine, four line-wise in-between sets, orthogonal and diagonal white king super piece attacks to later determine a possible sliding checking piece, and the aggregated black attacks.
<pre>
U64 horInbetween, verInbetween, diaInbetween, antInbetween;
U64 wKSuperAttacksOrth, wKSuperAttacksDia , bAnyAttacks;
</pre>
Intended members associated with a position object have a m_-prefix, scratch or register variables an underscore:
<pre>
/* black rooks and queens west */
_bAttacks = westAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks = _bAttacks;
_wKSuperAttacks = slidingRayEastAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth = _wKSuperAttacks;
horInbetween = _bAttacks & _wKSuperAttacks;
/* black rooks and queens east */
_bAttacks = eastAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayWestAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth |= _wKSuperAttacks;
horInbetween |= _bAttacks & _wKSuperAttacks;
/* black rooks and queens north */
_bAttacks = nortAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRaySoutAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth |= _wKSuperAttacks;
verInbetween = _bAttacks & _wKSuperAttacks;
/* black rooks and queens south */
_bAttacks = soutAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayNortAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth |= _wKSuperAttacks;
verInbetween |= _bAttacks & _wKSuperAttacks;
/* black bishops and queens north east */
_bAttacks = noEaAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRaySoWeAttacks(m_wKsq, m_occ);
wKSuperAttacksDia = _wKSuperAttacks;
diaInbetween = _bAttacks & _wKSuperAttacks;
/* black bishops and queens south west */
_bAttacks = soWeAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayNoEaAttacks(m_wKsq, m_occ);
wKSuperAttacksDia |= _wKSuperAttacks;
diaInbetween |= _bAttacks & _wKSuperAttacks;
/* black bishops and queens north west */
_bAttacks = noWeAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRaySoEaAttacks(m_wKsq, m_occ);
wKSuperAttacksDia |= _wKSuperAttacks;
antInbetween = _bAttacks & _wKSuperAttacks;
/* black bishops and queens south east */
_bAttacks = soEaAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayNoWeAttacks(m_wKsq, m_occ);
wKSuperAttacksDia |= _wKSuperAttacks;
antInbetween |= _bAttacks & _wKSuperAttacks;
</pre>
===None Sliding Pieces===
Black [[Pawn Attacks (Bitboards)#PawnAttacks|pawn-]] and knight- attacks are best determined by disjoint direction-wise steps and the [[Knight Pattern#MultipleKnightAttacks|multiple knight attacks]] routine. Black [[King Pattern#KingAttacks|king attacks]] may be determined by lookup or [[King Pattern#byCalculation|calculation]]:
<pre>
/* black knight attacks */
bAnyAttacks |= _knightAttacks (m_bKnights);
/* black pawn attacks */
bAnyAttacks |= _bPawnEastAttacks(m_bPawns);
bAnyAttacks |= _bPawnWestAttacks(m_bPawns);
/* black king attacks */
bAnyAttacks |= _kingAttacks(m_bKbb);
</pre>
==Generating White Moves==
Now, with all black attacks and black sliding vs white king in-between sets processed, one generates all legal white moves into 16 move-target bitboards.
===In Check?===
To make [[Check|in check]] or [[Double Check|double check]] handling [[Avoiding Branches|branch-less]], a target mask for all non king moves is calculated, which is needed anyway to remove own white pieces from the attack sets. In case of check it only contains the check giving piece as capture target - distant sliding checks include the in-between set intersected with empty squares as target set for blocking the check. The rare case of double check is considered by a mask (_nullIfDblCheck) computed from the set of check giving pieces - which leaves [[General Setwise Operations#EmptyAndUniverse|empty]] if [[Population Count#SinglePopulatedBitboards|population greater one]] and the universe (~empty) otherwise. Note that the ones' decrement of any single populated bitboard is always positive and leaves the empty set if shifted right 63 arithmetically:
<pre>
U64 allInbetween = horInbetween | verInbetween | diaInbetween | antInbetween;
_blocks = allInbetween & ~m_occ; /* in case of distant check */
_checkFrom = (wKSuperAttacksOrth & (m_bRooks | m_bQueens) )
| (wKSuperAttacksDia & (m_bBishop | m_bQueens) )
| (knightAttacks(m_wKbb) & m_bKnights )
| (wPawnAttacks (m_wKbb) & m_bPawns )
;
I64 _nullIfcheck = ( (I64)( bAnyAttacks & m_wKbb ) - 1) >> 63; /* signed shifts */
I64 _nullIfDblCheck = ( (I64)( checkFrom & (checkFrom-1) ) - 1) >> 63;
_checkTo = _checkFrom | _blocks | _nullIfcheck;
targetMask = ~m_wPieces & _checkTo & _nullIfDblCheck;
</pre>
===Sliding Pieces===
Moves by white sliding pieces are computed with eight Dumb7 or Kogge-Stone fills. Pinned sliders are considered [[Pin#PartialPin|partial pinned]] to move along the pinned direction:
<pre>
/* horizontal rook and queen moves */
_sliders = (m_wRooks | m_wQueens) & ~(allInbetween ^ horInbetween);
m_moveTargets[eWest] = westAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eEast] = eastAttacks (_sliders, m_occ) & targetMask;
/* vertical rook and queen moves*/
_sliders = (m_wRooks | m_wQueens) & ~(allInbetween ^ verInbetween);
m_moveTargets[eNort] = nortAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eSout] = soutAttacks (_sliders, m_occ) & targetMask;
/* diagonal bishop and queen moves */
_sliders = (m_wBishops | m_wQueens) & ~(allInbetween ^ diaInbetween);
m_moveTargets[eNoEa] = noEaAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eSoWe] = soWeAttacks (_sliders, m_occ) & targetMask;
/* antidiagonal bishop and queen moves */
_sliders = (m_wBishops | m_wQueens) & ~(allInbetween ^ antInbetween);
m_moveTargets[eNoWe] = noWeAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eSoEa] = soEaAttacks (_sliders, m_occ) & targetMask;
</pre>
===None Sliding Pieces===
Knight moves with their disjoint unique directions are generated by eight appropriate [[Knight Pattern#Calculation|direction shifts]] with all white knights not [[Pin|pinned]], using the same targetMask considering in check. Pawn captures and [[Pawn Pushes (Bitboards)|Pawn pushes]] also consider [[Pin#PartialPin|partial pins]]. A given [[En passant|en passant]] target square implies a strictly legal move, as already secured while making the triggering double pawn push.
Finally king move targets are generated by eight [[General Setwise Operations#OneStepOnly|one step direction shifts]], masking off target squares occupied by own pieces, or attacked by black, including [[DirGolem#Xray|x-rays]] through the white king in case of check by a sliding piece. [[Castling]] is left to the ambitious reader. In orthodox chess, west or east castling can simply distinguished from ordinal king moves due to the double king step, but requires some more tinkering in [[Chess960]].
<pre>
/* knight moves */
_knights = m_wKnights & ~allInbetween;
m_moveTargets[eNoNoEa] = noNoEa(_knights) & targetMask;
m_moveTargets[eNoEaEa] = noEaEa(_knights) & targetMask;
m_moveTargets[eSoEaEa] = soEaEa(_knights) & targetMask;
m_moveTargets[eSoSoEa] = soSoEa(_knights) & targetMask;
m_moveTargets[eNoNoWe] = noNoWe(_knights) & targetMask;
m_moveTargets[eNoWeWe] = noWeWe(_knights) & targetMask;
m_moveTargets[eSoWeWe] = soWeWe(_knights) & targetMask;
m_moveTargets[eSoSoWe] = soSoWe(_knights) & targetMask;
/* pawn captures and en passant */
_targets = ( m_bPieces & targetMask) | (C64(1) << m_epTarget);
_pawns = m_wPans & ~(allInbetween ^ diaInbetween);
m_moveTargets[eNoEa] |= noEaOne (_pawns) & _targets ;
_pawns = m_wPans & ~(allInbetween ^ antInbetween);
m_moveTargets[eNoWe] |= noWeOne(_pawns) & _targets;
/* pawn pushes ... */
_pawns = m_wPans & ~(allInbetween ^ verInbetween);
_pawnPushs = nortOne (_pawns) & ~m_occ;
m_moveTargets[eNort] |= _pawnPushs & targetMask;
/* and double pushs */
_rank4 = C64(0x00000000FF000000);
m_moveTargets[eNort] |= nortOne (_pawnPushs) & ~m_occ & targetMask & _rank4;
/* king moves */
targetMask = ~(m_wPieces | bAnyAttacks);
m_moveTargets[eWest] |= westOne (m_wKbb) & targetMask;
m_moveTargets[eEast] |= eastOne (m_wKbb) & targetMask;
m_moveTargets[eNort] |= nortOne (m_wKbb) & targetMask;
m_moveTargets[eSout] |= soutOne (m_wKbb) & targetMask;
m_moveTargets[eNoEa] |= noEaOne (m_wKbb) & targetMask;
m_moveTargets[eSoWe] |= soWeOne (m_wKbb) & targetMask;
m_moveTargets[eNoWe] |= noWeOne (m_wKbb) & targetMask;
m_moveTargets[eSoEa] |= soEaOne (m_wKbb) & targetMask;
</pre>
==Finally==
Additionally, all 16 move target bitboards might be aggregated into a union set, so that [[Checkmate|checkmate]] and [[Stalemate|stalemate]] is indicated by the zero flag for early returns, wasting a TT prefetch. Further, some disjoint and aggregated attack and pinned piece information might be utilized in [[Evaluation|evaluation]], maybe best associated with [[Thread|thread]] local memory shared by all [[Node|nodes]] searched, and allocated at the bottom of the [[Stack|stack]] referred by a (this) pointer, with the limited validity from generation until evaluation or the first (null) move is deepened.
=See also=
* [[AVX2]]
* [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[AVX2#KnightAttacks|AVX2 Knight Attacks]]
* [[Checks and Pinned Pieces (Bitboards)]]
* [[Dumb7Fill]]
* [[Fill by Subtraction]]
* [[Fill Algorithms]]
* [[GPU]]
* [[Kogge-Stone Algorithm]]
* [[Pigeon]]
* [[SSE2]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=43971 Is there such a thing as branchless move generation?] by [[John Hamlen]], [[CCC]], June 07, 2012
=External Links=
* [https://en.wikipedia.org/wiki/Golem Golem from Wikipedia]
* [https://en.wikipedia.org/wiki/Golem_%28disambiguation%29 Golem (disambiguation) from Wikipedia]
=References=
<references />
'''[[Move Generation|Up one Level]]'''
[[FILE:Golem 1920 Poster.jpg|border|right|thumb|The Golem <ref>[https://en.wikipedia.org/wiki/The_Golem:_How_He_Came_into_the_World The Golem: How He Came Into the World, from Wikipedia]</ref> ]]
'''DirGolem''',<br/>
Direction-wise Generation of [[Legal Move|Legal Moves]], is best done with vectors of [[Bitboards|bitboards]] applying [[AltiVec]], [[SSE2]], [[AVX2]] or similar [[SIMD and SWAR Techniques|SIMD architectures]] with appropriate register sets. Legal moves are stored as target-bitboards for all 16 [[Direction#MoveDirections|move directions]] as a kind of unsorted [[Move List|move list]] inside the state of a [[Node|node]]. That are four orthogonal directions with rook-, queen- and king-moves including [[Castling|castling]] and vertical [[Pawn Push|pawn-pushes]], four diagonal directions with bishop-, queen- and king-moves and pawn-captures including [[En passant|en passant]], and eight knight directions. Each [[Target Square|target square]] of each direction set has an unique one-to-one relation to it's [[Origin Square|source square]].
=Prospect=
To get the idea, the following description with scalar [[Cpp|C++]] code intended as pseudo code, is a rough translation of [[HansDamf|HansDamf's]] intrinsic SSE2 code by [[Gerd Isenberg]]. It assumes White to move within a [[Color Flipping|color flipper]] approach. More information for a set-wise [[Static Exchange Evaluation|SEE]], determining [[Check|check]] giving moves including [[Discovered Check|discovered checks]], etc. may be collected and considered. There are zillions of implementation nuances to utilize up to 16 128-bit XMM-, 16 256-bit YMM (AVX2), or even [[AVX-512]] 32 512-bit ZMM-SIMD registers <ref>[http://software.intel.com/en-us/blogs/2013/avx-512-instructions AVX-512 instructions | Intel® Developer Zone], by [http://software.intel.com/en-us/user/335550 James Reinders], July 23, 2013</ref>. The generation is completely branch-less, does not use huge lookup tables, and is intended to hide the latency of a [https://en.wikipedia.org/wiki/Prefetching prefetched] [[Transposition Table|TT]] probe. However, picking any moves or move proposals like [[Hash Move|hash]]- or [[Killer Move|killer moves]] from that list is more expensive and is typically done by a [https://en.wikipedia.org/wiki/Finite-state_machine finite state machine] to ensure proper [[Move Ordering|move ordering]] considering [[MVV-LVA]], [[Hanging Piece|hanging pieces]], etc., as mentioned in [[Pieces versus Directions#DirectionWise|pieces versus directions]].
=Basics=
* [[King Pattern#byCalculation|King Attacks by Calculation]]
* [[Knight Pattern#MultipleKnightAttacks|Multiple Knight Attacks]]
* [[Sliding Piece Attacks#Multiple|Multiple Sliding Pieces]]
* [[General Setwise Operations#OneStepOnly|One Step Only]]
* [[Checks and Pinned Pieces (Bitboards)#OppositeRay|Opposite Ray-Directions]]
* [[Pawn Attacks (Bitboards)#PawnAttacks|Pawn Attacks set-wise]]
* [[Pawn Pushes (Bitboards)#PawnPushSetwise|Pawn Pushes set-wise]]
* [[Pieces versus Directions]]
{{MappingHint}}
=Move Target Sets=
To determine white [[Pin#AbsolutePin|absolutely pinned pieces]] and squares attacked by black pieces, pawns, and king, taboo for the white king, black attacks are generated in a first phase. Those attacks are also utilized to detect whether the own king is in [[Check|check]]. Aggregated collected information is then used in a second phase of legal move target generation.
==Black Attacks==
===Sliders & Super King===
First, all black sliding attacks are generated by [[Dumb7Fill|Dumb7]]- or [[Kogge-Stone Algorithm|Kogge-Stone fill]], unrolled for all eight [[Direction#RayDirections|ray directions]], to aggregate them into a white king taboo bitboard, and to determine and keep line-wise [[Square Attacked By#InBetween|in-between]] bitboards by intersection with [[Checks and Pinned Pieces (Bitboards)#OppositeRay|opposite ray-direction]] attacks of the white king as sliding super piece, best generated by the [[Classical Approach|classical approach]], or alternatively along with the sliding pieces itself as additional SIMD data element processing two opponent fill direction in one run.
<span id="Xray"></span>The occupancy for the black sliding attacks has the white king excluded, so that in case of check by a sliding piece the king is [[X-ray|x-rayed]] to later avoid king moves to otherwise non attacked squares. The in-between sets intersected with own pieces leave [[Pin#AbsolutePin|pinned pieces]], but are also handy to determine an interposing block target set in case of distant sliding checks. In total, seven bitboards are processed as used in the second part of the routine, four line-wise in-between sets, orthogonal and diagonal white king super piece attacks to later determine a possible sliding checking piece, and the aggregated black attacks.
<pre>
U64 horInbetween, verInbetween, diaInbetween, antInbetween;
U64 wKSuperAttacksOrth, wKSuperAttacksDia , bAnyAttacks;
</pre>
Intended members associated with a position object have a m_-prefix, scratch or register variables an underscore:
<pre>
/* black rooks and queens west */
_bAttacks = westAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks = _bAttacks;
_wKSuperAttacks = slidingRayEastAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth = _wKSuperAttacks;
horInbetween = _bAttacks & _wKSuperAttacks;
/* black rooks and queens east */
_bAttacks = eastAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayWestAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth |= _wKSuperAttacks;
horInbetween |= _bAttacks & _wKSuperAttacks;
/* black rooks and queens north */
_bAttacks = nortAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRaySoutAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth |= _wKSuperAttacks;
verInbetween = _bAttacks & _wKSuperAttacks;
/* black rooks and queens south */
_bAttacks = soutAttacks (m_bRooks | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayNortAttacks(m_wKsq, m_occ);
wKSuperAttacksOrth |= _wKSuperAttacks;
verInbetween |= _bAttacks & _wKSuperAttacks;
/* black bishops and queens north east */
_bAttacks = noEaAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRaySoWeAttacks(m_wKsq, m_occ);
wKSuperAttacksDia = _wKSuperAttacks;
diaInbetween = _bAttacks & _wKSuperAttacks;
/* black bishops and queens south west */
_bAttacks = soWeAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayNoEaAttacks(m_wKsq, m_occ);
wKSuperAttacksDia |= _wKSuperAttacks;
diaInbetween |= _bAttacks & _wKSuperAttacks;
/* black bishops and queens north west */
_bAttacks = noWeAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRaySoEaAttacks(m_wKsq, m_occ);
wKSuperAttacksDia |= _wKSuperAttacks;
antInbetween = _bAttacks & _wKSuperAttacks;
/* black bishops and queens south east */
_bAttacks = soEaAttacks (m_bBishops | m_bQueens, m_occ ^ m_wKbb);
bAnyAttacks |= _bAttacks;
_wKSuperAttacks = slidingRayNoWeAttacks(m_wKsq, m_occ);
wKSuperAttacksDia |= _wKSuperAttacks;
antInbetween |= _bAttacks & _wKSuperAttacks;
</pre>
===None Sliding Pieces===
Black [[Pawn Attacks (Bitboards)#PawnAttacks|pawn-]] and knight- attacks are best determined by disjoint direction-wise steps and the [[Knight Pattern#MultipleKnightAttacks|multiple knight attacks]] routine. Black [[King Pattern#KingAttacks|king attacks]] may be determined by lookup or [[King Pattern#byCalculation|calculation]]:
<pre>
/* black knight attacks */
bAnyAttacks |= _knightAttacks (m_bKnights);
/* black pawn attacks */
bAnyAttacks |= _bPawnEastAttacks(m_bPawns);
bAnyAttacks |= _bPawnWestAttacks(m_bPawns);
/* black king attacks */
bAnyAttacks |= _kingAttacks(m_bKbb);
</pre>
==Generating White Moves==
Now, with all black attacks and black sliding vs white king in-between sets processed, one generates all legal white moves into 16 move-target bitboards.
===In Check?===
To make [[Check|in check]] or [[Double Check|double check]] handling [[Avoiding Branches|branch-less]], a target mask for all non king moves is calculated, which is needed anyway to remove own white pieces from the attack sets. In case of check it only contains the check giving piece as capture target - distant sliding checks include the in-between set intersected with empty squares as target set for blocking the check. The rare case of double check is considered by a mask (_nullIfDblCheck) computed from the set of check giving pieces - which leaves [[General Setwise Operations#EmptyAndUniverse|empty]] if [[Population Count#SinglePopulatedBitboards|population greater one]] and the universe (~empty) otherwise. Note that the ones' decrement of any single populated bitboard is always positive and leaves the empty set if shifted right 63 arithmetically:
<pre>
U64 allInbetween = horInbetween | verInbetween | diaInbetween | antInbetween;
_blocks = allInbetween & ~m_occ; /* in case of distant check */
_checkFrom = (wKSuperAttacksOrth & (m_bRooks | m_bQueens) )
| (wKSuperAttacksDia & (m_bBishop | m_bQueens) )
| (knightAttacks(m_wKbb) & m_bKnights )
| (wPawnAttacks (m_wKbb) & m_bPawns )
;
I64 _nullIfcheck = ( (I64)( bAnyAttacks & m_wKbb ) - 1) >> 63; /* signed shifts */
I64 _nullIfDblCheck = ( (I64)( checkFrom & (checkFrom-1) ) - 1) >> 63;
_checkTo = _checkFrom | _blocks | _nullIfcheck;
targetMask = ~m_wPieces & _checkTo & _nullIfDblCheck;
</pre>
===Sliding Pieces===
Moves by white sliding pieces are computed with eight Dumb7 or Kogge-Stone fills. Pinned sliders are considered [[Pin#PartialPin|partial pinned]] to move along the pinned direction:
<pre>
/* horizontal rook and queen moves */
_sliders = (m_wRooks | m_wQueens) & ~(allInbetween ^ horInbetween);
m_moveTargets[eWest] = westAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eEast] = eastAttacks (_sliders, m_occ) & targetMask;
/* vertical rook and queen moves*/
_sliders = (m_wRooks | m_wQueens) & ~(allInbetween ^ verInbetween);
m_moveTargets[eNort] = nortAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eSout] = soutAttacks (_sliders, m_occ) & targetMask;
/* diagonal bishop and queen moves */
_sliders = (m_wBishops | m_wQueens) & ~(allInbetween ^ diaInbetween);
m_moveTargets[eNoEa] = noEaAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eSoWe] = soWeAttacks (_sliders, m_occ) & targetMask;
/* antidiagonal bishop and queen moves */
_sliders = (m_wBishops | m_wQueens) & ~(allInbetween ^ antInbetween);
m_moveTargets[eNoWe] = noWeAttacks (_sliders, m_occ) & targetMask;
m_moveTargets[eSoEa] = soEaAttacks (_sliders, m_occ) & targetMask;
</pre>
===None Sliding Pieces===
Knight moves with their disjoint unique directions are generated by eight appropriate [[Knight Pattern#Calculation|direction shifts]] with all white knights not [[Pin|pinned]], using the same targetMask considering in check. Pawn captures and [[Pawn Pushes (Bitboards)|Pawn pushes]] also consider [[Pin#PartialPin|partial pins]]. A given [[En passant|en passant]] target square implies a strictly legal move, as already secured while making the triggering double pawn push.
Finally king move targets are generated by eight [[General Setwise Operations#OneStepOnly|one step direction shifts]], masking off target squares occupied by own pieces, or attacked by black, including [[DirGolem#Xray|x-rays]] through the white king in case of check by a sliding piece. [[Castling]] is left to the ambitious reader. In orthodox chess, west or east castling can simply distinguished from ordinal king moves due to the double king step, but requires some more tinkering in [[Chess960]].
<pre>
/* knight moves */
_knights = m_wKnights & ~allInbetween;
m_moveTargets[eNoNoEa] = noNoEa(_knights) & targetMask;
m_moveTargets[eNoEaEa] = noEaEa(_knights) & targetMask;
m_moveTargets[eSoEaEa] = soEaEa(_knights) & targetMask;
m_moveTargets[eSoSoEa] = soSoEa(_knights) & targetMask;
m_moveTargets[eNoNoWe] = noNoWe(_knights) & targetMask;
m_moveTargets[eNoWeWe] = noWeWe(_knights) & targetMask;
m_moveTargets[eSoWeWe] = soWeWe(_knights) & targetMask;
m_moveTargets[eSoSoWe] = soSoWe(_knights) & targetMask;
/* pawn captures and en passant */
_targets = ( m_bPieces & targetMask) | (C64(1) << m_epTarget);
_pawns = m_wPans & ~(allInbetween ^ diaInbetween);
m_moveTargets[eNoEa] |= noEaOne (_pawns) & _targets ;
_pawns = m_wPans & ~(allInbetween ^ antInbetween);
m_moveTargets[eNoWe] |= noWeOne(_pawns) & _targets;
/* pawn pushes ... */
_pawns = m_wPans & ~(allInbetween ^ verInbetween);
_pawnPushs = nortOne (_pawns) & ~m_occ;
m_moveTargets[eNort] |= _pawnPushs & targetMask;
/* and double pushs */
_rank4 = C64(0x00000000FF000000);
m_moveTargets[eNort] |= nortOne (_pawnPushs) & ~m_occ & targetMask & _rank4;
/* king moves */
targetMask = ~(m_wPieces | bAnyAttacks);
m_moveTargets[eWest] |= westOne (m_wKbb) & targetMask;
m_moveTargets[eEast] |= eastOne (m_wKbb) & targetMask;
m_moveTargets[eNort] |= nortOne (m_wKbb) & targetMask;
m_moveTargets[eSout] |= soutOne (m_wKbb) & targetMask;
m_moveTargets[eNoEa] |= noEaOne (m_wKbb) & targetMask;
m_moveTargets[eSoWe] |= soWeOne (m_wKbb) & targetMask;
m_moveTargets[eNoWe] |= noWeOne (m_wKbb) & targetMask;
m_moveTargets[eSoEa] |= soEaOne (m_wKbb) & targetMask;
</pre>
==Finally==
Additionally, all 16 move target bitboards might be aggregated into a union set, so that [[Checkmate|checkmate]] and [[Stalemate|stalemate]] is indicated by the zero flag for early returns, wasting a TT prefetch. Further, some disjoint and aggregated attack and pinned piece information might be utilized in [[Evaluation|evaluation]], maybe best associated with [[Thread|thread]] local memory shared by all [[Node|nodes]] searched, and allocated at the bottom of the [[Stack|stack]] referred by a (this) pointer, with the limited validity from generation until evaluation or the first (null) move is deepened.
=See also=
* [[AVX2]]
* [[AVX2#Dumb7Fill|AVX2 Dumb7Fill]]
* [[AVX2#KnightAttacks|AVX2 Knight Attacks]]
* [[Checks and Pinned Pieces (Bitboards)]]
* [[Dumb7Fill]]
* [[Fill by Subtraction]]
* [[Fill Algorithms]]
* [[GPU]]
* [[Kogge-Stone Algorithm]]
* [[Pigeon]]
* [[SSE2]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=43971 Is there such a thing as branchless move generation?] by [[John Hamlen]], [[CCC]], June 07, 2012
=External Links=
* [https://en.wikipedia.org/wiki/Golem Golem from Wikipedia]
* [https://en.wikipedia.org/wiki/Golem_%28disambiguation%29 Golem (disambiguation) from Wikipedia]
=References=
<references />
'''[[Move Generation|Up one Level]]'''
