https://www.chessprogramming.org/index.php?title=Classical_Approach&feed=atom&action=history
Classical Approach - Revision history
2024-03-28T08:51:03Z
Revision history for this page on the wiki
MediaWiki 1.30.1
https://www.chessprogramming.org/index.php?title=Classical_Approach&diff=25905&oldid=prev
GerdIsenberg at 08:05, 4 November 2021
2021-11-04T08:05:07Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 08:05, 4 November 2021</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l221" >Line 221:</td>
<td colspan="2" class="diff-lineno">Line 221:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><span id="InOneRun"></span></div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div><span id="InOneRun"></span></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==In one Run==  </div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>==In one Run==  </div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>As mentioned by [[Robert Hyatt]] <ref>[<del class="diffchange diffchange-inline">http</del>://www.talkchess.com/<del class="diffchange diffchange-inline">forum</del>/viewtopic.php?<del class="diffchange diffchange-inline">topic_view</del>=<del class="diffchange diffchange-inline">threads</del>&<del class="diffchange diffchange-inline">p</del>=<del class="diffchange diffchange-inline">299564</del>&<del class="diffchange diffchange-inline">t</del>=<del class="diffchange diffchange-inline">30356 </del>Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009</ref>, instead of fetching four [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board, one may already use the [[On an empty Board#PieceAttacks|rook- or bishop attacks]] to reset outer squares from that union set.  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>As mentioned by [[Robert Hyatt]] <ref>[<ins class="diffchange diffchange-inline">https</ins>://www.talkchess.com/<ins class="diffchange diffchange-inline">forum3</ins>/viewtopic.php?<ins class="diffchange diffchange-inline">f</ins>=<ins class="diffchange diffchange-inline">7</ins>&<ins class="diffchange diffchange-inline">t</ins>=<ins class="diffchange diffchange-inline">30356</ins>&<ins class="diffchange diffchange-inline">start</ins>=<ins class="diffchange diffchange-inline">14 </ins>Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009 </ref>, instead of fetching four [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board, one may already use the [[On an empty Board#PieceAttacks|rook- or bishop attacks]] to reset outer squares from that union set.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>A further improvement was suggested by [[Michael Sherwin]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</ref>, to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>A further improvement was suggested by [[Michael Sherwin]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</ref>, to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.</div></td></tr>
<tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l264" >Line 264:</td>
<td colspan="2" class="diff-lineno">Line 264:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=Forum Posts=</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=Forum Posts=</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=257692&t=27113 Re: Thinker output] by [[Robert Hyatt]], [[CCC]], March 25, 2009</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=257692&t=27113 Re: Thinker output] by [[Robert Hyatt]], [[CCC]], March 25, 2009</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>* [<del class="diffchange diffchange-inline">http</del>://www.talkchess.com/<del class="diffchange diffchange-inline">forum</del>/viewtopic.php?<del class="diffchange diffchange-inline">topic_view</del>=<del class="diffchange diffchange-inline">threads</del>&<del class="diffchange diffchange-inline">p</del>=<del class="diffchange diffchange-inline">299564</del>&<del class="diffchange diffchange-inline">t</del>=<del class="diffchange diffchange-inline">30356 </del>Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009</div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>* [<ins class="diffchange diffchange-inline">https</ins>://www.talkchess.com/<ins class="diffchange diffchange-inline">forum3</ins>/viewtopic.php?<ins class="diffchange diffchange-inline">f</ins>=<ins class="diffchange diffchange-inline">7</ins>&<ins class="diffchange diffchange-inline">t</ins>=<ins class="diffchange diffchange-inline">30356</ins>&<ins class="diffchange diffchange-inline">start</ins>=<ins class="diffchange diffchange-inline">14 </ins>Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78562 Bob used to do it this way] by [[Michael Sherwin|Mike Sherwin]], [[CCC]], October 31, 2021</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>=References=</div></td></tr>
</table>
GerdIsenberg
https://www.chessprogramming.org/index.php?title=Classical_Approach&diff=20951&oldid=prev
GerdIsenberg at 20:57, 24 August 2020
2020-08-24T20:57:00Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 20:57, 24 August 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l253" >Line 253:</td>
<td colspan="2" class="diff-lineno">Line 253:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Blockers and Beyond]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Blockers and Beyond]]</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">* [[CFish#AVX2 Attacks|CFish - AVX2 Attacks]]</ins></div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Obstruction Difference]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Obstruction Difference]]</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Pieces versus Directions]]</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>* [[Pieces versus Directions]]</div></td></tr>
</table>
GerdIsenberg
https://www.chessprogramming.org/index.php?title=Classical_Approach&diff=17880&oldid=prev
GerdIsenberg at 20:58, 5 February 2020
2020-02-05T20:58:32Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 20:58, 5 February 2020</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l1" >Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Classical Approach'''</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Classical Approach'''</div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>[[File:Classical Grotesque MET DT7804.jpg|border|right|thumb|[[<del class="diffchange diffchange-inline">Arts#</del>Klee|Paul Klee]] - Classical Grotesque, 1923 <ref>[[<del class="diffchange diffchange-inline">Arts#</del>Klee|Paul Klee]] - <del class="diffchange diffchange-inline">Classical Grotesque, 1923, </del>[https://commons.wikimedia.org/wiki/File:Classical_Grotesque_MET_DT7804.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>[[File:Classical Grotesque MET DT7804.jpg|border|right|thumb|[[<ins class="diffchange diffchange-inline">:Category:Paul </ins>Klee|Paul Klee]] - Classical Grotesque, 1923 <ref>[[<ins class="diffchange diffchange-inline">:Category:Paul </ins>Klee|Paul Klee]] - [https://commons.wikimedia.org/wiki/File:Classical_Grotesque_MET_DT7804.jpg <ins class="diffchange diffchange-inline">Classical Grotesque</ins>]<ins class="diffchange diffchange-inline">, 1923, </ins>[https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The classical approach to generate [[Sliding Pieces|sliding piece]] attacks was probably first used by [[Chess (Program)|Chess]] and [[Kaissa]].</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>The classical approach to generate [[Sliding Pieces|sliding piece]] attacks was probably first used by [[Chess (Program)|Chess]] and [[Kaissa]].</div></td></tr>
</table>
GerdIsenberg
https://www.chessprogramming.org/index.php?title=Classical_Approach&diff=1582&oldid=prev
GerdIsenberg at 12:47, 10 May 2018
2018-05-10T12:47:01Z
<p></p>
<table class="diff diff-contentalign-left" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr style="vertical-align: top;" lang="en">
<td colspan="2" style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: white; color:black; text-align: center;">Revision as of 12:47, 10 May 2018</td>
</tr><tr><td colspan="2" class="diff-lineno" id="mw-diff-left-l270" >Line 270:</td>
<td colspan="2" class="diff-lineno">Line 270:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>'''[[Sliding Piece Attacks|Up one Level]]'''</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>'''[[Sliding Piece Attacks|Up one Level]]'''</div></td></tr>
<tr><td colspan="2"> </td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div><ins style="font-weight: bold; text-decoration: none;">[[Category:Paul Klee]]</ins></div></td></tr>
</table>
GerdIsenberg
https://www.chessprogramming.org/index.php?title=Classical_Approach&diff=1431&oldid=prev
GerdIsenberg: Created page with "'''Home * Board Representation * Bitboards * Sliding Piece Attacks * Classical Approach''' File:Classical Grotesque MET DT7804.jpg|border|right|th..."
2018-05-07T14:52:27Z
<p>Created page with "'''<a href="/Main_Page" title="Main Page">Home</a> * <a href="/Board_Representation" title="Board Representation">Board Representation</a> * <a href="/Bitboards" title="Bitboards">Bitboards</a> * <a href="/Sliding_Piece_Attacks" title="Sliding Piece Attacks">Sliding Piece Attacks</a> * Classical Approach''' File:Classical Grotesque MET DT7804.jpg|border|right|th..."</p>
<p><b>New page</b></p><div>'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * [[Sliding Piece Attacks]] * Classical Approach'''<br />
<br />
[[File:Classical Grotesque MET DT7804.jpg|border|right|thumb|[[Arts#Klee|Paul Klee]] - Classical Grotesque, 1923 <ref>[[Arts#Klee|Paul Klee]] - Classical Grotesque, 1923, [https://commons.wikimedia.org/wiki/File:Classical_Grotesque_MET_DT7804.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]] <br />
<br />
The classical approach to generate [[Sliding Pieces|sliding piece]] attacks was probably first used by [[Chess (Program)|Chess]] and [[Kaissa]].<br />
<br />
{{MappingHint}}<br />
=Ray Attacks= <br />
The classical approach works ray-wise and uses pre-calculated [[On an empty Board#RayAttacks|ray-attacks]] for each of the eight [[Rays#RayDirections|ray-directions]] and each of the 64 [[Squares|squares]]. It has to distinguish between [[On an empty Board#PositiveRays|positive]] and [[On an empty Board#NegativeRays|negative]] directions, because it has to [[BitScan|bitscan]] the ray-attack intersection with the [[Occupancy|occupancy]] in different orders. That usually don't cares for getting line- or piece attacks, since one likely unrolls all directions needed for a particular line or piece - otherwise one may rely on a [[BitScan#GeneralizedBitscan|generalized bitscan]].<br />
<br />
''We rely on the compass rose to enumerate ray-directions:''<br />
<pre><br />
noWe nort noEa<br />
+7 +8 +9<br />
\ | /<br />
west -1 <- 0 -> +1 east<br />
/ | \<br />
-9 -8 -7<br />
soWe sout soEa<br />
</pre><br />
<br />
==Positive Rays== <br />
Attacks of Positive Ray-Directions:<br />
<pre><br />
East (+1) North (+8) NorthEast (+9) NorthWest (+7)<br />
. . . . . . . . . . . 1 . . . . . . . . . . . 1 . . . . . . . .<br />
. . . . . . . . . . . 1 . . . . . . . . . . 1 . 1 . . . . . . .<br />
. . . . . . . . . . . 1 . . . . . . . . . 1 . . . 1 . . . . . .<br />
. . . . . . . . . . . 1 . . . . . . . . 1 . . . . . 1 . . . . .<br />
. . . R 1 1 1 1 . . . R . . . . . . . B . . . . . . . B . . . .<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
</pre><br />
===Conditional=== <br />
The first step gets the [[On an empty Board#RayAttacks|ray-attack]] on the otherwise empty board. Potential blockers are then determined by intersection with the [[Occupancy|occupancy]], the set of all pieces. The first blocker, if any, is the least significant one-bit of the intersection. A [[BitScan#Bitscanforward|bitscan forward]] determines the square of the first blocker, to reset it's ray-bits from the attack set. For instance a bishop on g2:<br />
<pre><br />
occupied & NorthWest(g2) {a8, c6}<br />
1 . 1 1 1 1 1 1 1 . . . . . . . 1 . . . . . . .<br />
1 . 1 1 1 1 1 1 . 1 . . . . . . . . . . . . . .<br />
. 1 1 . . . . . . . 1 . . . . . . . 1 . . . . .<br />
. . . . . . . . . . . 1 . . . . . . . . . . . .<br />
. . . . . . . . & . . . . 1 . . . = . . . . . . . .<br />
. . . . . . 1 . . . . . . 1 . . . . . . . . . .<br />
1 1 1 1 1 1 B 1 . . . . . . . . . . . . . . . .<br />
1 1 1 1 1 . 1 1 . . . . . . . . . . . . . . . .<br />
<br />
xor NorthWest(c6 = bitscanForward{a8,c6}<br />
1 . . . . . . .<br />
. 1 . . . . . .<br />
. . . . . . . .<br />
. . . . . . . .<br />
. . . . . . . .<br />
. . . . . . . .<br />
. . . . . . . .<br />
. . . . . . . .<br />
<br />
= final northWest Attacks<br />
. . . . . . . .<br />
. . . . . . . .<br />
. . 1 . . . . .<br />
. . . 1 . . . .<br />
. . . . 1 . . .<br />
. . . . . 1 . .<br />
. . . . . . . .<br />
. . . . . . . .<br />
<br />
</pre><br />
<br />
<pre><br />
U64 rayAttacks[8][64];<br />
<br />
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
if ( blocker ) {<br />
square = bitScanForward(blocker);<br />
attacks ^= rayAttacks[dir8][square];<br />
}<br />
return attacks;<br />
}<br />
</pre><br />
<span id="Branchless"></span><br />
===Branchless=== <br />
Branches are evil with todays super pipelined processors. Even if branch-prediction heuristics become smarter, [[Avoiding Branches|branch-less]] solutions allow better scheduling and parallel speedup of independent instruction chains, like processing several directions.<br />
<br />
Considering todays fast [[x86-64]] [[x86-64#gpinstructions|bsf-instruction]] of [https://en.wikipedia.org/wiki/Intel_Core_2 Core 2] or [https://en.wikipedia.org/wiki/AMD_K10 K10], a branch-less solution may be worth a try. Due to the fact the [[Occupancy|occupancy]] of [[First Rank Attacks#TheOuterSquares|the outer squares]] doesn't affect the attack set, setting the most significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.<br />
<pre><br />
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
_BitScanForward64 (&square, blocker | C64(0x8000000000000000));<br />
return attacks ^ rayAttacks[dir8][square];<br />
}<br />
</pre><br />
==Negative Rays== <br />
Attacks of Negative Ray-Directions:<br />
<pre><br />
West (-1) South (-8) SouthWest (-9) SouthEast (-7)<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .<br />
1 1 1 R . . . . . . . R . . . . . . . B . . . . . . . B . . . .<br />
. . . . . . . . . . . 1 . . . . . . 1 . . . . . . . . . 1 . . .<br />
. . . . . . . . . . . 1 . . . . . 1 . . . . . . . . . . . 1 . .<br />
. . . . . . . . . . . 1 . . . . 1 . . . . . . . . . . . . . 1 .<br />
</pre><br />
===Conditional=== <br />
Works the same way, but needs [[BitScan#Bitscanreverse|reverse bitscan]] to find the first blocking piece, if any.<br />
<pre><br />
U64 getNegativeRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
if ( blocker ) {<br />
square = bitScanReverse(blocker);<br />
attacks ^= rayAttacks[dir8][square];<br />
}<br />
return attacks;<br />
}<br />
</pre><br />
===Branchless=== <br />
The branch-less solution with a fast [[x86-64]] [[x86-64#gpinstructions|bsr-instruction]] allows better scheduling and parallel speedup of independent instruction chains, like processing several directions. Setting the least significant bit ensures to scan at least an outer square, which would address an empty ray set anyway, therefor not affecting the final result with no blocker or a most outer one.<br />
<pre><br />
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
_BitScanReverse64 (&square, blocker | 1);<br />
return attacks ^ rayAttacks[dir8][square];<br />
}<br />
</pre><br />
<br />
<span id="Generalized"></span><br />
==Generalized== <br />
The idea of the [[BitScan#GeneralizedBitscan|generalized bitscan]] may be used to share the same code for all directions. The implementation of isNegative(dir8), a macro or inline-function, depends on the definition or enumeration of the directions and is likely a compare or test instruction.<br />
===Conditional=== <br />
The conditional by a good predictable branch on blocker is favorable - specially for slow bitscans with some chance to skip it, e.g. in endings.<br />
<pre><br />
U64 getRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
if ( blocker ) {<br />
square = bitScan(blocker, isNegative(dir8));<br />
attacks ^= rayAttacks[dir8][square];<br />
}<br />
return attacks;<br />
}<br />
</pre><br />
===Branchless=== <br />
The branch-less routine provides a dirMask as universal set for negative rays and the empty set for positive rays, to implement the [[BitScan#GeneralizedBitscan|generalized bitscan]]. The dirBit-or ensures to scan at least outer square with empty ray sets.<br />
<pre><br />
U64 getRayAttacks(U64 occupied, enumDir dir8, unsigned long square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
blocker &= -blocker | dirMask[dir8];<br />
blocker |= dirBit [dir8]<br />
_BitScanReverse64 (&square, blocker | dirBit[dir8]);<br />
return attacks ^ rayAttacks[dir8][square];<br />
}<br />
</pre><br />
<br />
==Zero Count== <br />
If available, Leading- or Trailing Zero Count instructions may be used instead of bitscan for another branch-less solution of the classical attack getter. Since they leave 64 for empty sets, it needs to make the ray attack [[Array|arrays]] one greater to allow index by 64 which contains an empty set - or one needs to map 64 to 63 for positive directions.<br />
<pre><br />
U64 rayAttacks[8][65];<br />
<br />
U64 getPositiveRayAttacks(U64 occupied, enumDir dir8, enumSquare square) {<br />
U64 attacks = rayAttacks[dir8][square];<br />
U64 blocker = attacks & occupied;<br />
int firstBlockingSquare = trailingZeroCount(blocker);<br />
attacks ^= rayAttacks[dir8][firstBlockingSquare];<br />
return attacks;<br />
}<br />
</pre><br />
LeadingZeroCount instead of bitscanReverse may be done similarly, considering the reversed order.<br />
<br />
<span id="Wrapper"></span><br />
=Line Attacks= <br />
As mentioned, line attacks are the [[General Setwise Operations#Union|union]] of positive and opposite negative [[Rays#RayDirections|ray-directions]] - since they are disjoint one may also use 'xor' or 'add':<br />
<pre><br />
U64 diagonalAttacks(U64 occ, enumSquare sq) {<br />
return getPositiveRayAttacks(occ, noEa, sq)<br />
| getNegativeRayAttacks(occ, soWe, sq); // ^ +<br />
}<br />
<br />
U64 antiDiagAttacks(U64 occ, enumSquare sq) {<br />
return getPositiveRayAttacks(occ, noWe, sq)<br />
| getNegativeRayAttacks(occ, soEa, sq); // ^ +<br />
}<br />
<br />
U64 fileAttacks (U64 occ, enumSquare sq) {<br />
return getPositiveRayAttacks(occ, nort, sq)<br />
| getNegativeRayAttacks(occ, sout, sq); // ^ +<br />
}<br />
<br />
U64 rankAttacks (U64 occ, enumSquare sq) {<br />
return getPositiveRayAttacks(occ, east, sq)<br />
| getNegativeRayAttacks(occ, west, sq); // ^ +<br />
}<br />
</pre><br />
<br />
=Piece Attacks= <br />
==Union of Line Attacks== <br />
Of course piece attacks are the union of the line attacks:<br />
<pre><br />
U64 rookAttacks (U64 occ, enumSquare sq) {<br />
return fileAttacks(occ, sq)<br />
| rankAttacks(occ, sq); // ^ +<br />
}<br />
<br />
U64 bishopAttacks (U64 occ, enumSquare sq) {<br />
return diagonalAttacks(occ, sq)<br />
| antiDiagAttacks(occ, sq); // ^ +<br />
}<br />
<br />
U64 queenAttacks (U64 occ, enumSquare sq) {<br />
return rookAttacks (occ, sq)<br />
| bishopAttacks(occ, sq); // ^ +<br />
}<br />
</pre><br />
<span id="InOneRun"></span><br />
==In one Run== <br />
As mentioned by [[Robert Hyatt]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=299564&t=30356 Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009</ref>, instead of fetching four [[On an empty Board#RayAttacks|ray-attacks]] on the otherwise empty board, one may already use the [[On an empty Board#PieceAttacks|rook- or bishop attacks]] to reset outer squares from that union set. <br />
<br />
A further improvement was suggested by [[Michael Sherwin]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009</ref>, to union the occupancy with the outer bits 0 and 63. Together with appropriate bits set in separate ray-masks, this yields to an efficient branchless solution with 13 64-bit operations in total and 4.5 KByte for the lookup tables for both rooks and bishops each.<br />
<br />
<pre><br />
struct {<br />
U64 bitsN; // bits North, including MSB (bit 63)<br />
U64 bitsE; // bits East, including MSB<br />
U64 bitsS; // bits South, including LSB (bit 0 == 1)<br />
U64 bitsW; // bits West, including LSB <br />
} CACHE_ALIGN rayWstop[64]; <br />
<br />
U64 attacksEmpty[64];<br />
U64 rayN[64];<br />
U64 rayE[64];<br />
U64 rayS[64];<br />
U64 rayW[64];<br />
<br />
U64 rookAttacks(U64 occ, unsigned int sq) {<br />
unsigned long ulN, ulE, ulS, ulW;<br />
occ |= C64(0x8000000000000001);<br />
_BitScanForward64(&ulN, occ & rayWstop[sq].bitsN);<br />
_BitScanForward64(&ulE, occ & rayWstop[sq].bitsE);<br />
_BitScanReverse64(&ulS, occ & rayWstop[sq].bitsS);<br />
_BitScanReverse64(&ulW, occ & rayWstop[sq].bitsW);<br />
return attacksEmpty[sq]^rayN[ulN]^rayE[ulE]^rayS[ulS]^rayW[ulW];<br />
} <br />
</pre><br />
<br />
=See also=<br />
* [[Bitfoot#ABBitboards|Bitfoot - A/B Bitboards]]<br />
* [[Blockers and Beyond]]<br />
* [[Obstruction Difference]]<br />
* [[Pieces versus Directions]]<br />
<br />
=Publications=<br />
* [[Stuart Cracraft]] ('''1984'''). ''Bitmap move generation in Chess''. [[ICGA Journal|ICCA Journal]], Vol. 7, No. 3, pp. 146–153<br />
* [[Fridel Fainshtein]] ('''2006'''). ''An Orthodox k-Move Problem-Composer for Chess Directmates''. M.Sc. thesis, [[Bar-Ilan University]], [http://www.problemschach.de/KMOVEComposer.pdf pdf], Appendix D - 64-bit Representation, pp. 105<br />
* [[Fridel Fainshtein]], [[Yaakov HaCohen-Kerner]] ('''2006'''). ''A Chess Composer of Two-Move Mate Problems''. [[ICGA Journal]], Vol. 29, No. 1, [http://homedir.jct.ac.il/~kerner/pdf_docs/ICGA_computer_composer.pdf pdf], Appendix E: 64-bit representation<br />
<br />
=Forum Posts=<br />
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=257692&t=27113 Re: Thinker output] by [[Robert Hyatt]], [[CCC]], March 25, 2009<br />
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=299564&t=30356 Re: Yet another bitboard attack generator] by [[Robert Hyatt]], [[CCC]], October 28, 2009<br />
* [http://www.talkchess.com/forum/viewtopic.php?t=30971 Modified old 64 bit attack getter] by [[Michael Sherwin]], [[CCC]], December 06, 2009<br />
<br />
=References=<br />
<references /><br />
<br />
'''[[Sliding Piece Attacks|Up one Level]]'''</div>
GerdIsenberg