25,161
edits
Changes
Created page with "'''Home * Programming * Data * Attack and Defend Maps''' border|right|thumb|[[Arts#Bak|Samuel Bak - Sheltering Myths, 1998..."
'''[[Main Page|Home]] * [[Programming]] * [[Data]] * Attack and Defend Maps'''
[[FILE:ShelteringMyths.jpg|border|right|thumb|[[Arts#Bak|Samuel Bak]] - Sheltering Myths, 1998 <ref>[https://static1.squarespace.com/static/594044bd3a041171e0426683/t/5a12fc6b53450acdbebfc69d/1511193725379/Bak_The+Game+Continues_2000.pdf The Game Continues - Chess in the Art of Samuel Bak] (pdf) from [https://www.puckergallery.com/artists/#/samuel-bak/ Samuel Bak - represented by Pucker Gallery since 1969]</ref> ]]
'''Attack and Defend Maps''',<br/>
also called '''Attack Tables''', refer to data-structures, most often [[Array|arrays]], containing attack or defend information for every pawn or piece and/or the transposed information for each square, which pieces [[Square Control|control]], that is either attack or defend it. These Maps are useful for [[Evaluation|evaluation]] purposes such as safe [[Mobility|mobility]], [[Static Exchange Evaluation|SEE]] and of course [[Move Generation|move generation]]. While the piece centric attack information, a set of attacked squares per piece, is often encoded as [[Bitboards|bitboard]], there are more alternatives for storing the square centric information, about attacking pieces.
=Maintaining Attacks=
==Incremental Update==
The piece centric and/or square centric information is often initialized at the [[Root|root]] and [[Incremental Updates|updated incrementally]] during the [[Search|search]] while [[Make Move|making]] and [[Unmake Move|unmaking]] [[Moves|moves]]. The idea is that a move has often only a local influence on the attack tables, and that it is usually cheaper to change only those squares which changed from- or to-attacks, rather than all squares from scratch. This is especially true during the [[Opening|opening]] or early [[Middlegame|middlegame]] phase, but does become more expensive in the late middlegame or [[Endgame|endings]] with sliding pieces, especially queens.
==On the Fly==
Programmers like [[Joël Rivat]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/71f7b5ee3764f082 Chess programming using bitboards] by [[Joël Rivat]], [[Computer Chess Forums|rgcc]], August 18, 1995</ref>, [[Robert Hyatt]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/33c57503391f3a89 Speed of Move Generator] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgcc]], August 15, 1995, post 5 by [[Robert Hyatt]] where he mentions on the fly generation with [[Rotated Bitboards|rotated bitboards]]</ref>, [[Ed Schroder|Ed Schröder]] and [[Gerd Isenberg]] avoid or have abandoned incrementally updated attack tables and rely on the paradigm to process information if needed. A lot of nodes don't need the attack information at all, or only a small part of it. With all the [[Hash Table|hash tables]], incremental update tends to do some unnecessary work, considering the update costs in "worst case" positions, f.i. queen endings, where one move change the attack information of many squares.
On the other hand, if attack tables are available, one should utilize the information as much as possible for a smarter search and evaluation to gain exponentially. Anyway, one has to be careful with too complicated data structures and update code.
=Implementations=
==Classical Approach==
The square centric classical approach with bitboards was used in [[Chess (Program)|Chess 4.5]] and descibed by [[Larry Atkin]] and [[David Slate]] <ref>[[David Slate]] and [[Larry Atkin]] ('''1977'''). ''CHESS 4.5 - The Northwestern University Chess Program.'' [[Chess Skill in Man and Machine]] (ed. [[Peter W. Frey]]), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted ('''1988''') in [[Computer Chess Compendium]]</ref> . The incrementally updated attack tables, from which most move generation is done, are called ''ATKFR'' and ''ATKTO''. ''ATKFR'' is a set of 64 bitboards which give, for each square, all the squares attacked by the piece, if any, that resides on the square. ''ATKTO'' ([[Square Attacked By]]) is the transpose of ''ATKFR'', giving for each square, the locations of all pieces that attack that square. For instance the square E4 (T) is attacked by a black rook at E8, a black knight at F6, and defended by a white rook at E1 and a white pawn at D3 <ref>[http://www.craftychess.com/hyatt/bitmaps.html Rotated bitmaps, a new twist on an old idea] by [[Robert Hyatt]]</ref> :
<pre>
attacks_to[E4]
. . . . 1 . . .
. . . . . . . .
. . . . . 1 . .
. . . . . . . .
. . . . T . . .
. . . 1 . . . .
. . . . . . . .
. . . . 1 . . .
</pre>
==Alternatives==
There are several alternatives for keeping the square centric information what pieces attack each particular square.
===Piece-Sets===
A [[Square Attacked By]] bitboard aka ''ATKFR'' as possible union-set of multiple pawns and pieces of either side require intersections with piece bitboards, or [[BitScan|bitscanned]] square lookups, to determine which pieces and how many attack or defend.
Based on a fixed piece-type and bit-position relation with usual material dispositions (for each side, no more than one queen, two rooks, one bishop per square color, two knights), 32-bit [[Piece-Sets]] already inherit the information which pieces (and how many of both sides) attack a particular square, one can even imagine a 16-bit lookup inside a 64KByte table to get an denser attack indicator/count byte for each color a lá [[Attack and Defend Maps#EDsLookup|Ed Schröder]]. [[MS-DOS]] [[IsiChess]] maintained an [[Array|array]] of 64 32-bit piece-sets for every square, and an array of up to 32 attack-to bitboards for every piece. However working with piece-sets requires an additional indirection via a [[Piece-lists|Piece-list]] to get the square of that piece.
<span id="EDsLookup"></span>
===Ed's lookup===
As described by [[Ed Schroder|Ed Schröder]] in ''Evaluation in REBEL'' <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#HW Evaluation in REBEL (hanging pieces)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]], also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]</ref> , [[Rebel]] uses two board tables for both sides, one [[Byte|byte]] entry each, the three lower bits contain an attack counter, while the five upper bits indicate the presence of least one pawn or piece attacking/defending:
<pre>
+------+------+------+------+------+------+------+------+
| BIT0 | BIT1 | BIT2 | BIT3 | BIT4 | BIT5 | BIT6 | BIT7 |
+------+------+------+------+------+------+------+------+
| Number of | PAWN |KNIGHT| ROOK | QUEEN| KING |
| ATTACKERS | |BISHOP| | | |
+------+------+------+------+------+------+------+------+
</pre>
The information might be inaccurate in some cases since it loses some information if multiple pieces of one kind are involved. However, since [[Static Exchange Evaluation|SEE]] might be erroneous anyway due to [[Pin|pins]], [[X-ray|x-rays]] or [[Overloading|overloaded pieces]], Ed's scheme seems sufficient for practical purposes - and it is fast. Each byte (for both sides) can act as index inside pre-calculated three-dimensional table to perform an SEE by looking up a target piece or square, attack- and defend-byte:
<pre>
char see_table [14][256][256]; // 14*64 K = 896 KByte
see = see_table[Piece][attackByte][defendByte];
</pre>
While the counter might be updated incrementally, the piece indicators as possible union of multiple pieces (i.e. two knights and one bishop) is not that simple to update, thus Ed generates those tables in evaluation on the fly by scanning the pieces of the board.
===Direction wise===
An other alternative to incremental updated attack tables is motivated by direction wise fill algorithms like [[Kogge-Stone Algorithm|Kogge-Stone]] for sliding pieces, and that one may hide memory latencies from probes of the [[Transposition Table|transposition table]]. Especially [[Pawn Attacks (Bitboards)|pawn attacks]] are cheap to determine on the fly, and likely reduce the set of capture targets of least valuable pieces defended by pawns, which are otherwise object of [[Quiescence Search]] or [[Static Exchange Evaluation|SEE]].
=See also=
* [[Piece-Sets]]
* [[Bitboards]]
: [[Sliding Piece Attacks]]
: [[Square Attacked By]]
: [[Pieces versus Directions]]
=Forums Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/71f7b5ee3764f082 Chess programming using bitboards] by [[Joël Rivat]], [[Computer Chess Forums|rgcc]], August 18, 1995
* [https://www.stmintz.com/ccc/index.php?id=30023 Attack Tables] by [[Roberto Waldteufel]], [[CCC]], October 20, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=209546 Counting attacked squares: how?] by [[Leen Ammeraal]], [[CCC]], January 24, 2002
* [https://www.stmintz.com/ccc/index.php?id=260736 attacks_from[] and attacks_to[] info] by Nagendra Singh Tomar, [[CCC]], October 21, 2002
* [https://www.stmintz.com/ccc/index.php?id=266390 Attack tables] by [[Andreas Herrmann]], [[CCC]], November 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=363519 The Zappa Attack Table Code] by [[Anthony Cozzie]], [[CCC]], May 05, 2004
* [https://www.stmintz.com/ccc/index.php?id=373246 bitboards and incrementally updated attack tables] by [[Eric Oldre]], [[CCC]], June 30, 2004
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=171 Attack table] by Anonymous, [[Computer Chess Forums|Winboard Forum]], October 06, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1626 Attack table musings] by GeoffW, [[Computer Chess Forums|Winboard Forum]], February 11, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=20370 Incremental updating for positional evaluation] by [[Steven Edwards]], [[CCC]], March 27, 2008
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=267994&t=27965 Piece attacks count] by [[Marco Costalba]], [[CCC]], May 18, 2009 » [[Population Count]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=52085 Incrementally-updated attack map] by [[Harm Geert Muller]], April 21, 2014 » [[Incremental Updates]]
=References=
<references />
'''[[Data|Up one Level]]'''
[[FILE:ShelteringMyths.jpg|border|right|thumb|[[Arts#Bak|Samuel Bak]] - Sheltering Myths, 1998 <ref>[https://static1.squarespace.com/static/594044bd3a041171e0426683/t/5a12fc6b53450acdbebfc69d/1511193725379/Bak_The+Game+Continues_2000.pdf The Game Continues - Chess in the Art of Samuel Bak] (pdf) from [https://www.puckergallery.com/artists/#/samuel-bak/ Samuel Bak - represented by Pucker Gallery since 1969]</ref> ]]
'''Attack and Defend Maps''',<br/>
also called '''Attack Tables''', refer to data-structures, most often [[Array|arrays]], containing attack or defend information for every pawn or piece and/or the transposed information for each square, which pieces [[Square Control|control]], that is either attack or defend it. These Maps are useful for [[Evaluation|evaluation]] purposes such as safe [[Mobility|mobility]], [[Static Exchange Evaluation|SEE]] and of course [[Move Generation|move generation]]. While the piece centric attack information, a set of attacked squares per piece, is often encoded as [[Bitboards|bitboard]], there are more alternatives for storing the square centric information, about attacking pieces.
=Maintaining Attacks=
==Incremental Update==
The piece centric and/or square centric information is often initialized at the [[Root|root]] and [[Incremental Updates|updated incrementally]] during the [[Search|search]] while [[Make Move|making]] and [[Unmake Move|unmaking]] [[Moves|moves]]. The idea is that a move has often only a local influence on the attack tables, and that it is usually cheaper to change only those squares which changed from- or to-attacks, rather than all squares from scratch. This is especially true during the [[Opening|opening]] or early [[Middlegame|middlegame]] phase, but does become more expensive in the late middlegame or [[Endgame|endings]] with sliding pieces, especially queens.
==On the Fly==
Programmers like [[Joël Rivat]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/71f7b5ee3764f082 Chess programming using bitboards] by [[Joël Rivat]], [[Computer Chess Forums|rgcc]], August 18, 1995</ref>, [[Robert Hyatt]] <ref>[http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/33c57503391f3a89 Speed of Move Generator] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgcc]], August 15, 1995, post 5 by [[Robert Hyatt]] where he mentions on the fly generation with [[Rotated Bitboards|rotated bitboards]]</ref>, [[Ed Schroder|Ed Schröder]] and [[Gerd Isenberg]] avoid or have abandoned incrementally updated attack tables and rely on the paradigm to process information if needed. A lot of nodes don't need the attack information at all, or only a small part of it. With all the [[Hash Table|hash tables]], incremental update tends to do some unnecessary work, considering the update costs in "worst case" positions, f.i. queen endings, where one move change the attack information of many squares.
On the other hand, if attack tables are available, one should utilize the information as much as possible for a smarter search and evaluation to gain exponentially. Anyway, one has to be careful with too complicated data structures and update code.
=Implementations=
==Classical Approach==
The square centric classical approach with bitboards was used in [[Chess (Program)|Chess 4.5]] and descibed by [[Larry Atkin]] and [[David Slate]] <ref>[[David Slate]] and [[Larry Atkin]] ('''1977'''). ''CHESS 4.5 - The Northwestern University Chess Program.'' [[Chess Skill in Man and Machine]] (ed. [[Peter W. Frey]]), pp. 82-118. Springer-Verlag, New York, N.Y. 2nd ed. 1983. ISBN 0-387-90815-3. Reprinted ('''1988''') in [[Computer Chess Compendium]]</ref> . The incrementally updated attack tables, from which most move generation is done, are called ''ATKFR'' and ''ATKTO''. ''ATKFR'' is a set of 64 bitboards which give, for each square, all the squares attacked by the piece, if any, that resides on the square. ''ATKTO'' ([[Square Attacked By]]) is the transpose of ''ATKFR'', giving for each square, the locations of all pieces that attack that square. For instance the square E4 (T) is attacked by a black rook at E8, a black knight at F6, and defended by a white rook at E1 and a white pawn at D3 <ref>[http://www.craftychess.com/hyatt/bitmaps.html Rotated bitmaps, a new twist on an old idea] by [[Robert Hyatt]]</ref> :
<pre>
attacks_to[E4]
. . . . 1 . . .
. . . . . . . .
. . . . . 1 . .
. . . . . . . .
. . . . T . . .
. . . 1 . . . .
. . . . . . . .
. . . . 1 . . .
</pre>
==Alternatives==
There are several alternatives for keeping the square centric information what pieces attack each particular square.
===Piece-Sets===
A [[Square Attacked By]] bitboard aka ''ATKFR'' as possible union-set of multiple pawns and pieces of either side require intersections with piece bitboards, or [[BitScan|bitscanned]] square lookups, to determine which pieces and how many attack or defend.
Based on a fixed piece-type and bit-position relation with usual material dispositions (for each side, no more than one queen, two rooks, one bishop per square color, two knights), 32-bit [[Piece-Sets]] already inherit the information which pieces (and how many of both sides) attack a particular square, one can even imagine a 16-bit lookup inside a 64KByte table to get an denser attack indicator/count byte for each color a lá [[Attack and Defend Maps#EDsLookup|Ed Schröder]]. [[MS-DOS]] [[IsiChess]] maintained an [[Array|array]] of 64 32-bit piece-sets for every square, and an array of up to 32 attack-to bitboards for every piece. However working with piece-sets requires an additional indirection via a [[Piece-lists|Piece-list]] to get the square of that piece.
<span id="EDsLookup"></span>
===Ed's lookup===
As described by [[Ed Schroder|Ed Schröder]] in ''Evaluation in REBEL'' <ref>[http://www.top-5000.nl/authors/rebel/chess840.htm#HW Evaluation in REBEL (hanging pieces)] from [http://www.top-5000.nl/authors/rebel/chess840.htm How Rebel Plays Chess] by [[Ed Schroder|Ed Schröder]], also available as [http://members.home.nl/matador/Inside%20Rebel.pdf pdf]</ref> , [[Rebel]] uses two board tables for both sides, one [[Byte|byte]] entry each, the three lower bits contain an attack counter, while the five upper bits indicate the presence of least one pawn or piece attacking/defending:
<pre>
+------+------+------+------+------+------+------+------+
| BIT0 | BIT1 | BIT2 | BIT3 | BIT4 | BIT5 | BIT6 | BIT7 |
+------+------+------+------+------+------+------+------+
| Number of | PAWN |KNIGHT| ROOK | QUEEN| KING |
| ATTACKERS | |BISHOP| | | |
+------+------+------+------+------+------+------+------+
</pre>
The information might be inaccurate in some cases since it loses some information if multiple pieces of one kind are involved. However, since [[Static Exchange Evaluation|SEE]] might be erroneous anyway due to [[Pin|pins]], [[X-ray|x-rays]] or [[Overloading|overloaded pieces]], Ed's scheme seems sufficient for practical purposes - and it is fast. Each byte (for both sides) can act as index inside pre-calculated three-dimensional table to perform an SEE by looking up a target piece or square, attack- and defend-byte:
<pre>
char see_table [14][256][256]; // 14*64 K = 896 KByte
see = see_table[Piece][attackByte][defendByte];
</pre>
While the counter might be updated incrementally, the piece indicators as possible union of multiple pieces (i.e. two knights and one bishop) is not that simple to update, thus Ed generates those tables in evaluation on the fly by scanning the pieces of the board.
===Direction wise===
An other alternative to incremental updated attack tables is motivated by direction wise fill algorithms like [[Kogge-Stone Algorithm|Kogge-Stone]] for sliding pieces, and that one may hide memory latencies from probes of the [[Transposition Table|transposition table]]. Especially [[Pawn Attacks (Bitboards)|pawn attacks]] are cheap to determine on the fly, and likely reduce the set of capture targets of least valuable pieces defended by pawns, which are otherwise object of [[Quiescence Search]] or [[Static Exchange Evaluation|SEE]].
=See also=
* [[Piece-Sets]]
* [[Bitboards]]
: [[Sliding Piece Attacks]]
: [[Square Attacked By]]
: [[Pieces versus Directions]]
=Forums Posts=
==1995 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/71f7b5ee3764f082 Chess programming using bitboards] by [[Joël Rivat]], [[Computer Chess Forums|rgcc]], August 18, 1995
* [https://www.stmintz.com/ccc/index.php?id=30023 Attack Tables] by [[Roberto Waldteufel]], [[CCC]], October 20, 1998
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=209546 Counting attacked squares: how?] by [[Leen Ammeraal]], [[CCC]], January 24, 2002
* [https://www.stmintz.com/ccc/index.php?id=260736 attacks_from[] and attacks_to[] info] by Nagendra Singh Tomar, [[CCC]], October 21, 2002
* [https://www.stmintz.com/ccc/index.php?id=266390 Attack tables] by [[Andreas Herrmann]], [[CCC]], November 20, 2002
* [https://www.stmintz.com/ccc/index.php?id=363519 The Zappa Attack Table Code] by [[Anthony Cozzie]], [[CCC]], May 05, 2004
* [https://www.stmintz.com/ccc/index.php?id=373246 bitboards and incrementally updated attack tables] by [[Eric Oldre]], [[CCC]], June 30, 2004
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=171 Attack table] by Anonymous, [[Computer Chess Forums|Winboard Forum]], October 06, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=1626 Attack table musings] by GeoffW, [[Computer Chess Forums|Winboard Forum]], February 11, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=20370 Incremental updating for positional evaluation] by [[Steven Edwards]], [[CCC]], March 27, 2008
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=267994&t=27965 Piece attacks count] by [[Marco Costalba]], [[CCC]], May 18, 2009 » [[Population Count]]
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=52085 Incrementally-updated attack map] by [[Harm Geert Muller]], April 21, 2014 » [[Incremental Updates]]
=References=
<references />
'''[[Data|Up one Level]]'''
