25,161
edits
Changes
Created page with "'''Home * Board Representation * Piece-Lists''' '''Piece-Lists''', File:Birds Swooping Down and Arrows MET DT7784.jpg|border|right|thumb|300px|[[Arts#Klee..."
'''[[Main Page|Home]] * [[Board Representation]] * Piece-Lists'''
'''Piece-Lists''', [[File:Birds Swooping Down and Arrows MET DT7784.jpg|border|right|thumb|300px|[[Arts#Klee|Paul Klee]] - Birds Swooping Down and Arrows <ref>[[Arts#Klee|Paul Klee]] - Birds Swooping Down and Arrows, 1919, [https://commons.wikimedia.org/wiki/File:Birds_Swooping_Down_and_Arrows_MET_DT7784.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]
[[Linked List|lists]] or [[Array|arrays]] of all up to 32 [[Pieces|pieces]] (including pawns and king) on the [[Chessboard|board]]. Likely, [[Pieces#PieceTypeCoding|type]] and [[Color|color]] of pieces are associated by a certain index range or disjoint lists or arrays. Each element of the list or array for each particular piece associates the [[Squares|square]] occupied by this piece.
=<span id="MicroChess"></span>MicroChess=
[[Peter Jennings|Peter Jennings']] board representation in [[MicroChess]] completely relies on an array of 32 [[Byte|Bytes]] for each possible piece. Content of the following addresses were either square coordinates in the 0..63 range, or, to indicate a piece was captured and no longer on the board, appropriate values outside that range. After [[Make Move|make]]-[[Unmake Move|unmake]], Jennings reversed the board by subtracting coordinates from 63 (octal 077), to keep all nodes searched the same [[Color|color]]. To alter some bytes inside those addresses with a Monitor program was also the way to enter positions in the first [[6502]]-based [[MicroChess]] on a [[KIM-1]] <ref>[[Peter Jennings]] ('''1976'''). ''[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6d8478 MicroChess, a Chess playing program for the 6502 Microcomputer]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/4-1.MicroChess_%20Manual_for_6502.Micro-Ware/MicroChessManual.PETER_JENNINGS.062303071.sm.pdf pdf], Courtesy of [[Peter Jennings]], [[The Computer History Museum]]</ref>.
{| class="wikitable" style="text-align: left;"
|-
|colspan="6"| MEMORY LOCATIONS FOR THE PIECES
|-
! COMPUTER<br/>PIECES!! !! YOUR<br/>PIECES
|-
| 0050 || King || 0060
|-
| 0051 || Queen || 0061
|-
| 0052 || King Rook || 0062
|-
| 0053 || Queen Rook || 0063
|-
| 0054 || King Bishop || 0064
|-
| 0055 || Queen Bishop || 0065
|-
| 0056 || King Knight || 0066
|-
| 0057 || Queen Knight || 0067
|-
|-
| 0058 || K R Pawn || 0068
|-
| 0059 || Q R Pawn || 0069
|-
| 005A || K N Pawn || 006A
|-
| 005B || Q N Pawn || 006B
|-
| 005C || K B Pawn || 006C
|-
| 005D || Q B Pawn || 006D
|-
| 005E || K Pawn || 006E
|-
| 005F || Q Pawn || 006F
|}
=<span id="NewArchitecture"></span>New Architecture=
As elaborated in his thesis ''New Architectures in Computer Chess, Chapter 2 Non-Bitboard Architectures'' <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''</ref>, [[Fritz Reul]] keeps disjoint piece lists in his 32-bit program [[Loop (Program)#32bit|Loop Leiden]], even disjoint lists for bishops with different [[Color of a Square|square color]], for multiple loops per [[Pieces#PieceTypeCoding|piece-type]] and [[Direction#RayDirections|ray-directions]] for [[Sliding Pieces|sliding pieces]] with compact loop bodies with piece specific code, for instance the [[Vector Attacks#NewArchitecture|blocker loops]] in [[Captures|capture]] [[Move Generation|generation]]. For an efficient [[Incremental Updates|incremental update]] in [[Make Move|making]] and [[Unmake Move|unmaking moves]] with [[Origin Square|from-]] and [[Target Square|to-coordinates]], an '''index board''' - like the common piece board, indexed by those square coordinates - keeps piece-type relative indíces to the appropriate piece lists. The following sample demonstrates how rooks are traversed and how the data structure concerning a single move list of white rooks is updated after making and then unmaking two consecutive moves.
==Declaration==
<pre>int nWhiteRooks; /* counter white rooks */
int white_rook_list[MAX_ROOKS] ; /* MAX_ROOKS = 10 */
...
int white_index_board[64]; /* or 15x12 board array */
</pre>
==Piece List Traversal==
The piece list traversal for instance in [[Move Generation|move generation]] is straight forward or backward.
===Forward===
<pre>for (int p = 0; p < nWhiteRooks; ) {
fromsquare = white_rook_list[p++];
...
}</pre>
===Backward===
<pre>for (int p = nWhiteRooks; p > 0; ) {
fromsquare = white_rook_list[--p];
...
}</pre>
==<span id="IncrementalUpdate"></span>Incremental Update==
[[Incremental Updates|Incremental update]] is demonstrated by making Rb5-b8, Ra8xb8 concerning the white rook list and index board, ignoring the black lists and piece array. Since removing a captured piece is done by copying the last piece of the list to fill the gap of the removed piece, but inserting in unmake is done by appending at the end of the list, the piece list of one piece-type may be shuffled in "random" order, yielding in changed [[Move Ordering|move ordering]] and [[Static Exchange Evaluation|SEE]] rarely producing different results, since pieces like rook and knight may traversed in different order.
===<span id="Make"></span>Make Moves===
<pre>
Initial make(Rb5-b8) make (xb8)
nWhiteRooks--;
index = white_index_board[b5]; index = white_index_board[b8];
white_index_board[b8] = index; square = white_rook_list[nWhiteRooks];
white_rook_list[index] = b8; white_rook_list[index] = square;
white_index_board[square] = index
white_rook_list
nWhiteRooks = 2 nWhiteRooks = 2 nWhiteRooks = 1
0 1 ... 0 1 ... 0 1 ...
┌────┬────┬─~──┐ ┌────┬────┬─~──┐ ┌────┬────┬─~──┐
│ b5 │ h1 │... │ │ b8 │ h1 │... │ │ h1 │ h1*│... │
└────┴────┴─~──┘ └────┴────┴─~──┘ └────┴────┴─~──┘
white_index_board
┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐
8 │ │ │ │ │ │ │ │ | 8 │ │ 0 │ │ │ │ │ │ | 8 │ │ 0*│ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │ │ 0 │ │ │ │ │ │ | 5 │ │ 0*│ │ │ │ │ │ | 5 │ │ 0*│ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ │ │ │ │ │ │ │ 1 | 1 │ │ │ │ │ │ │ │ 1 | 1 │ │ │ │ │ │ │ │ 0 |
└───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘
a b c d e f g h a b c d e f g h a b c d e f g h
* no longer valid indices
</pre>
===<span id="Unmake"></span>Unmake Moves===
<pre>
unmake(xb8) unmake(Rb5-b8)
white_rook_list[nWhiteRooks] = b8; index = white_index_board[b8];
white_index_board[b8]=nWhiteRooks; white_index[b5] = index;
nWhiteRooks++; white_rook_list[index] = b5;
nWhiteRooks = 1 nWhiteRooks = 2 nWhiteRooks = 2
0 1 ... 0 1 ... 0 1 ...
┌────┬────┬─~──┐ ┌────┬────┬─~──┐ ┌────┬────┬─~──┐
│ h1 │ ...│... │ │ h1 │ b8 │... │ │ h1 │ b5 │... │
└────┴────┴─~──┘ └────┴────┴─~──┘ └────┴────┴─~──┘
white_index_board
┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐
8 │ │ 0*│ │ │ │ │ │ | 8 │ │ 1 │ │ │ │ │ │ | 8 │ │ 1*│ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │ │ 0*│ │ │ │ │ │ | 5 │ │ 0*│ │ │ │ │ │ | 5 │ │ 1 │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ │ │ │ │ │ │ │ 0 | 1 │ │ │ │ │ │ │ │ 0 | 1 │ │ │ │ │ │ │ │ 0 |
└───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘
a b c d e f g h a b c d e f g h a b c d e f g h
* no longer valid indices</pre>
=Linked Lists=
Some programs apply [[Linked List|linked lists]] instead of arrays for an efficient removal and insertion of pieces while making or unmaking captures. Sample declaration and code was proposed by [[Daniel Shawul]] in [[CCC]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=468678&t=43971 Re: Is there such a thing as branchless move generation?] by [[Daniel Shawul]], [[CCC]], June 10, 2012</ref>.
=See also=
* [[0x88]]
* [[Bitboards]]
* [[Piece-Sets]]
=Publications=
* [[Dietrich Prinz]] ('''1952'''). ''Robot Chess''. Research, Vol. 6, reprinted 1988 in [[Computer Chess Compendium]]
* [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [http://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
* [[Peter Jennings]] ('''1976'''). ''[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6d8478 MicroChess, a Chess playing program for the 6502 Microcomputer]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/4-1.MicroChess_%20Manual_for_6502.Micro-Ware/MicroChessManual.PETER_JENNINGS.062303071.sm.pdf pdf], Courtesy of [[Peter Jennings]], [[The Computer History Museum]]
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, [https://pure.uvt.nl/ws/files/1098572/Proefschrift_Fritz_Reul_170609.pdf pdf]
=Forum Posts=
==1994 ...==
* [http://groups.google.com/group/gnu.chess/browse_frm/thread/a6b1257a1c386acf Speed up UpdatePieceList] by [[Vincent Diepeveen]], [[GNU Chess#NewsGroup|gnu.chess]], April 18, 1994
* [http://www.stmintz.com/ccc/index.php?id=21856 piece list possibilities] by [[Tom Kerrigan]], [[CCC]], July 07, 1998
* [http://www.stmintz.com/ccc/index.php?id=22472 is the "dead bit" a good idea?] by [[Tom Kerrigan]], [[CCC]], July 20, 1998
==2000 ...==
* [http://www.stmintz.com/ccc/index.php?id=125774 Re: C or C++ for Chess Programming?] by [[Dan Newman]], [[CCC]], August 23, 2000
* [http://www.stmintz.com/ccc/index.php?id=287682 "Piece List" - Administration?] by Axel Grüttner, [[CCC]], March 03, 2003
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=516 Two questions for bitboard experts] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], November 06, 2004 » [[Bitboards]], [[Square Attacked By#InBetween|In Between]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3110 Piece-list representation] by [[Alessandro Scotti]], [[Computer Chess Forums|Winboard Forum]], July 17, 2005
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=468678&t=43971 Re: Is there such a thing as branchless move generation?] by [[Daniel Shawul]], [[CCC]], June 10, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=57588 Fast lookup of pieces for move generation without bitboards] by [[Shawn Chidester]], [[CCC]], September 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=63126 PieceLists ?] by [[Mahmoud Uthman]], [[CCC]], February 10, 2017
=External Links=
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p003.htm Chapter 3: Board Games - 3.1 CHESS] from [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [http://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
=References=
<references />
=What links here?=
'''[[Board Representation|Up one Level]]'''
'''Piece-Lists''', [[File:Birds Swooping Down and Arrows MET DT7784.jpg|border|right|thumb|300px|[[Arts#Klee|Paul Klee]] - Birds Swooping Down and Arrows <ref>[[Arts#Klee|Paul Klee]] - Birds Swooping Down and Arrows, 1919, [https://commons.wikimedia.org/wiki/File:Birds_Swooping_Down_and_Arrows_MET_DT7784.jpg] [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref>]]
[[Linked List|lists]] or [[Array|arrays]] of all up to 32 [[Pieces|pieces]] (including pawns and king) on the [[Chessboard|board]]. Likely, [[Pieces#PieceTypeCoding|type]] and [[Color|color]] of pieces are associated by a certain index range or disjoint lists or arrays. Each element of the list or array for each particular piece associates the [[Squares|square]] occupied by this piece.
=<span id="MicroChess"></span>MicroChess=
[[Peter Jennings|Peter Jennings']] board representation in [[MicroChess]] completely relies on an array of 32 [[Byte|Bytes]] for each possible piece. Content of the following addresses were either square coordinates in the 0..63 range, or, to indicate a piece was captured and no longer on the board, appropriate values outside that range. After [[Make Move|make]]-[[Unmake Move|unmake]], Jennings reversed the board by subtracting coordinates from 63 (octal 077), to keep all nodes searched the same [[Color|color]]. To alter some bytes inside those addresses with a Monitor program was also the way to enter positions in the first [[6502]]-based [[MicroChess]] on a [[KIM-1]] <ref>[[Peter Jennings]] ('''1976'''). ''[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6d8478 MicroChess, a Chess playing program for the 6502 Microcomputer]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/4-1.MicroChess_%20Manual_for_6502.Micro-Ware/MicroChessManual.PETER_JENNINGS.062303071.sm.pdf pdf], Courtesy of [[Peter Jennings]], [[The Computer History Museum]]</ref>.
{| class="wikitable" style="text-align: left;"
|-
|colspan="6"| MEMORY LOCATIONS FOR THE PIECES
|-
! COMPUTER<br/>PIECES!! !! YOUR<br/>PIECES
|-
| 0050 || King || 0060
|-
| 0051 || Queen || 0061
|-
| 0052 || King Rook || 0062
|-
| 0053 || Queen Rook || 0063
|-
| 0054 || King Bishop || 0064
|-
| 0055 || Queen Bishop || 0065
|-
| 0056 || King Knight || 0066
|-
| 0057 || Queen Knight || 0067
|-
|-
| 0058 || K R Pawn || 0068
|-
| 0059 || Q R Pawn || 0069
|-
| 005A || K N Pawn || 006A
|-
| 005B || Q N Pawn || 006B
|-
| 005C || K B Pawn || 006C
|-
| 005D || Q B Pawn || 006D
|-
| 005E || K Pawn || 006E
|-
| 005F || Q Pawn || 006F
|}
=<span id="NewArchitecture"></span>New Architecture=
As elaborated in his thesis ''New Architectures in Computer Chess, Chapter 2 Non-Bitboard Architectures'' <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''</ref>, [[Fritz Reul]] keeps disjoint piece lists in his 32-bit program [[Loop (Program)#32bit|Loop Leiden]], even disjoint lists for bishops with different [[Color of a Square|square color]], for multiple loops per [[Pieces#PieceTypeCoding|piece-type]] and [[Direction#RayDirections|ray-directions]] for [[Sliding Pieces|sliding pieces]] with compact loop bodies with piece specific code, for instance the [[Vector Attacks#NewArchitecture|blocker loops]] in [[Captures|capture]] [[Move Generation|generation]]. For an efficient [[Incremental Updates|incremental update]] in [[Make Move|making]] and [[Unmake Move|unmaking moves]] with [[Origin Square|from-]] and [[Target Square|to-coordinates]], an '''index board''' - like the common piece board, indexed by those square coordinates - keeps piece-type relative indíces to the appropriate piece lists. The following sample demonstrates how rooks are traversed and how the data structure concerning a single move list of white rooks is updated after making and then unmaking two consecutive moves.
==Declaration==
<pre>int nWhiteRooks; /* counter white rooks */
int white_rook_list[MAX_ROOKS] ; /* MAX_ROOKS = 10 */
...
int white_index_board[64]; /* or 15x12 board array */
</pre>
==Piece List Traversal==
The piece list traversal for instance in [[Move Generation|move generation]] is straight forward or backward.
===Forward===
<pre>for (int p = 0; p < nWhiteRooks; ) {
fromsquare = white_rook_list[p++];
...
}</pre>
===Backward===
<pre>for (int p = nWhiteRooks; p > 0; ) {
fromsquare = white_rook_list[--p];
...
}</pre>
==<span id="IncrementalUpdate"></span>Incremental Update==
[[Incremental Updates|Incremental update]] is demonstrated by making Rb5-b8, Ra8xb8 concerning the white rook list and index board, ignoring the black lists and piece array. Since removing a captured piece is done by copying the last piece of the list to fill the gap of the removed piece, but inserting in unmake is done by appending at the end of the list, the piece list of one piece-type may be shuffled in "random" order, yielding in changed [[Move Ordering|move ordering]] and [[Static Exchange Evaluation|SEE]] rarely producing different results, since pieces like rook and knight may traversed in different order.
===<span id="Make"></span>Make Moves===
<pre>
Initial make(Rb5-b8) make (xb8)
nWhiteRooks--;
index = white_index_board[b5]; index = white_index_board[b8];
white_index_board[b8] = index; square = white_rook_list[nWhiteRooks];
white_rook_list[index] = b8; white_rook_list[index] = square;
white_index_board[square] = index
white_rook_list
nWhiteRooks = 2 nWhiteRooks = 2 nWhiteRooks = 1
0 1 ... 0 1 ... 0 1 ...
┌────┬────┬─~──┐ ┌────┬────┬─~──┐ ┌────┬────┬─~──┐
│ b5 │ h1 │... │ │ b8 │ h1 │... │ │ h1 │ h1*│... │
└────┴────┴─~──┘ └────┴────┴─~──┘ └────┴────┴─~──┘
white_index_board
┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐
8 │ │ │ │ │ │ │ │ | 8 │ │ 0 │ │ │ │ │ │ | 8 │ │ 0*│ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │ │ 0 │ │ │ │ │ │ | 5 │ │ 0*│ │ │ │ │ │ | 5 │ │ 0*│ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ │ │ │ │ │ │ │ 1 | 1 │ │ │ │ │ │ │ │ 1 | 1 │ │ │ │ │ │ │ │ 0 |
└───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘
a b c d e f g h a b c d e f g h a b c d e f g h
* no longer valid indices
</pre>
===<span id="Unmake"></span>Unmake Moves===
<pre>
unmake(xb8) unmake(Rb5-b8)
white_rook_list[nWhiteRooks] = b8; index = white_index_board[b8];
white_index_board[b8]=nWhiteRooks; white_index[b5] = index;
nWhiteRooks++; white_rook_list[index] = b5;
nWhiteRooks = 1 nWhiteRooks = 2 nWhiteRooks = 2
0 1 ... 0 1 ... 0 1 ...
┌────┬────┬─~──┐ ┌────┬────┬─~──┐ ┌────┬────┬─~──┐
│ h1 │ ...│... │ │ h1 │ b8 │... │ │ h1 │ b5 │... │
└────┴────┴─~──┘ └────┴────┴─~──┘ └────┴────┴─~──┘
white_index_board
┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐ ┌───┬───┬───┬───┬───┬───┬───┬───┐
8 │ │ 0*│ │ │ │ │ │ | 8 │ │ 1 │ │ │ │ │ │ | 8 │ │ 1*│ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ | 7 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ | 6 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
5 │ │ 0*│ │ │ │ │ │ | 5 │ │ 0*│ │ │ │ │ │ | 5 │ │ 1 │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ | 4 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ | 3 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ | 2 │ │ │ │ │ │ │ │ |
├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┼───┼───┼───┤
1 │ │ │ │ │ │ │ │ 0 | 1 │ │ │ │ │ │ │ │ 0 | 1 │ │ │ │ │ │ │ │ 0 |
└───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘ └───┴───┴───┴───┴───┴───┴───┴───┘
a b c d e f g h a b c d e f g h a b c d e f g h
* no longer valid indices</pre>
=Linked Lists=
Some programs apply [[Linked List|linked lists]] instead of arrays for an efficient removal and insertion of pieces while making or unmaking captures. Sample declaration and code was proposed by [[Daniel Shawul]] in [[CCC]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=468678&t=43971 Re: Is there such a thing as branchless move generation?] by [[Daniel Shawul]], [[CCC]], June 10, 2012</ref>.
=See also=
* [[0x88]]
* [[Bitboards]]
* [[Piece-Sets]]
=Publications=
* [[Dietrich Prinz]] ('''1952'''). ''Robot Chess''. Research, Vol. 6, reprinted 1988 in [[Computer Chess Compendium]]
* [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [http://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
* [[Peter Jennings]] ('''1976'''). ''[http://www.computerhistory.org/chess/full_record.php?iid=doc-431614f6d8478 MicroChess, a Chess playing program for the 6502 Microcomputer]''. [http://archive.computerhistory.org/projects/chess/related_materials/text/4-1.MicroChess_%20Manual_for_6502.Micro-Ware/MicroChessManual.PETER_JENNINGS.062303071.sm.pdf pdf], Courtesy of [[Peter Jennings]], [[The Computer History Museum]]
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, [https://pure.uvt.nl/ws/files/1098572/Proefschrift_Fritz_Reul_170609.pdf pdf]
=Forum Posts=
==1994 ...==
* [http://groups.google.com/group/gnu.chess/browse_frm/thread/a6b1257a1c386acf Speed up UpdatePieceList] by [[Vincent Diepeveen]], [[GNU Chess#NewsGroup|gnu.chess]], April 18, 1994
* [http://www.stmintz.com/ccc/index.php?id=21856 piece list possibilities] by [[Tom Kerrigan]], [[CCC]], July 07, 1998
* [http://www.stmintz.com/ccc/index.php?id=22472 is the "dead bit" a good idea?] by [[Tom Kerrigan]], [[CCC]], July 20, 1998
==2000 ...==
* [http://www.stmintz.com/ccc/index.php?id=125774 Re: C or C++ for Chess Programming?] by [[Dan Newman]], [[CCC]], August 23, 2000
* [http://www.stmintz.com/ccc/index.php?id=287682 "Piece List" - Administration?] by Axel Grüttner, [[CCC]], March 03, 2003
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=516 Two questions for bitboard experts] by [[Tord Romstad]], [[Computer Chess Forums|Winboard Forum]], November 06, 2004 » [[Bitboards]], [[Square Attacked By#InBetween|In Between]]
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=3110 Piece-list representation] by [[Alessandro Scotti]], [[Computer Chess Forums|Winboard Forum]], July 17, 2005
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=468678&t=43971 Re: Is there such a thing as branchless move generation?] by [[Daniel Shawul]], [[CCC]], June 10, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=57588 Fast lookup of pieces for move generation without bitboards] by [[Shawn Chidester]], [[CCC]], September 10, 2015
* [http://www.talkchess.com/forum/viewtopic.php?t=63126 PieceLists ?] by [[Mahmoud Uthman]], [[CCC]], February 10, 2017
=External Links=
* [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p003.htm Chapter 3: Board Games - 3.1 CHESS] from [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [http://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227
=References=
<references />
=What links here?=
'''[[Board Representation|Up one Level]]'''
