Difference between revisions of "Piece-Lists"
GerdIsenberg (talk | contribs) (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...") |
GerdIsenberg (talk | contribs) |
||
(6 intermediate revisions by the same user not shown) | |||
Line 1: | Line 1: | ||
'''[[Main Page|Home]] * [[Board Representation]] * Piece-Lists''' | '''[[Main Page|Home]] * [[Board Representation]] * Piece-Lists''' | ||
− | + | [[File:Birds Swooping Down and Arrows MET DT7784.jpg|border|right|thumb|300px| [[:Category:Paul Klee|Paul Klee]] - Birds Swooping Down and Arrows <ref>[[:Category:Paul 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>]] | |
+ | |||
+ | '''Piece-Lists''',<br/> | ||
[[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. | [[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. | ||
Line 168: | Line 170: | ||
* [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=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 | * [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 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=23498 Piece List questions] by [[Andrew Short]], [[CCC]], September 04, 2008 | ||
==2010 ...== | ==2010 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=31776 GetSmallestAttacker() in 16x12 board representation] by metax, [[CCC]], January 17, 2010 » [[Static Exchange Evaluation]] | ||
* [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?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=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 | * [http://www.talkchess.com/forum/viewtopic.php?t=63126 PieceLists ?] by [[Mahmoud Uthman]], [[CCC]], February 10, 2017 | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69364 piece lists advantage with bit-boards?] by [[Mahmoud Uthman]], [[CCC]], December 24, 2018 | ||
+ | : [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69364&start=12 Re: piece lists advantage with bit-boards?] by [[Ronald de Man]], [[CCC]], December 26, 2018 » [[Stockfish]], [[asmFish]] | ||
+ | ==2020 ...== | ||
+ | * [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77511 PieceList in older versions of Glaurung Chess Engine] by shahil4242, [[CCC]], June 19, 2021 » [[Glaurung]] | ||
+ | : [http://www.talkchess.com/forum3/viewtopic.php?f=2&t=77511&start=2 Re: PieceList in older versions of Glaurung Chess Engine] by [[Tord Romstad]], [[CCC]], June 19, 2021 | ||
=External Links= | =External Links= | ||
Line 180: | Line 189: | ||
=What links here?= | =What links here?= | ||
'''[[Board Representation|Up one Level]]''' | '''[[Board Representation|Up one Level]]''' | ||
+ | [[Category:Paul Klee]] |
Latest revision as of 22:22, 20 June 2021
Home * Board Representation * Piece-Lists
Piece-Lists,
lists or arrays of all up to 32 pieces (including pawns and king) on the board. Likely, type and 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 square occupied by this piece.
Contents
MicroChess
Peter Jennings' board representation in MicroChess completely relies on an array of 32 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-unmake, Jennings reversed the board by subtracting coordinates from 63 (octal 077), to keep all nodes searched the same 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 [2].
MEMORY LOCATIONS FOR THE PIECES | |||||
COMPUTER PIECES |
YOUR 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 |
New Architecture
As elaborated in his thesis New Architectures in Computer Chess, Chapter 2 Non-Bitboard Architectures [3], Fritz Reul keeps disjoint piece lists in his 32-bit program Loop Leiden, even disjoint lists for bishops with different square color, for multiple loops per piece-type and ray-directions for sliding pieces with compact loop bodies with piece specific code, for instance the blocker loops in capture generation. For an efficient incremental update in making and unmaking moves with from- and 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
int nWhiteRooks; /* counter white rooks */ int white_rook_list[MAX_ROOKS] ; /* MAX_ROOKS = 10 */ ... int white_index_board[64]; /* or 15x12 board array */
Piece List Traversal
The piece list traversal for instance in move generation is straight forward or backward.
Forward
for (int p = 0; p < nWhiteRooks; ) { fromsquare = white_rook_list[p++]; ... }
Backward
for (int p = nWhiteRooks; p > 0; ) { fromsquare = white_rook_list[--p]; ... }
Incremental Update
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 and SEE rarely producing different results, since pieces like rook and knight may traversed in different order.
Make Moves
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
Unmake Moves
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
Linked Lists
Some programs apply 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 [4].
See also
Publications
- Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium
- Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
- Peter Jennings (1976). MicroChess, a Chess playing program for the 6502 Microcomputer. pdf, Courtesy of Peter Jennings, The Computer History Museum
- Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, pdf
Forum Posts
1994 ...
- Speed up UpdatePieceList by Vincent Diepeveen, gnu.chess, April 18, 1994
- piece list possibilities by Tom Kerrigan, CCC, July 07, 1998
- is the "dead bit" a good idea? by Tom Kerrigan, CCC, July 20, 1998
2000 ...
- Re: C or C++ for Chess Programming? by Dan Newman, CCC, August 23, 2000
- "Piece List" - Administration? by Axel Grüttner, CCC, March 03, 2003
- Two questions for bitboard experts by Tord Romstad, Winboard Forum, November 06, 2004 » Bitboards, In Between
- Piece-list representation by Alessandro Scotti, Winboard Forum, July 17, 2005
- Piece List questions by Andrew Short, CCC, September 04, 2008
2010 ...
- GetSmallestAttacker() in 16x12 board representation by metax, CCC, January 17, 2010 » Static Exchange Evaluation
- Re: Is there such a thing as branchless move generation? by Daniel Shawul, CCC, June 10, 2012
- Fast lookup of pieces for move generation without bitboards by Shawn Chidester, CCC, September 10, 2015
- PieceLists ? by Mahmoud Uthman, CCC, February 10, 2017
- piece lists advantage with bit-boards? by Mahmoud Uthman, CCC, December 24, 2018
- Re: piece lists advantage with bit-boards? by Ronald de Man, CCC, December 26, 2018 » Stockfish, asmFish
2020 ...
- PieceList in older versions of Glaurung Chess Engine by shahil4242, CCC, June 19, 2021 » Glaurung
- Re: PieceList in older versions of Glaurung Chess Engine by Tord Romstad, CCC, June 19, 2021
External Links
- Chapter 3: Board Games - 3.1 CHESS from Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
References
- ↑ Paul Klee - Birds Swooping Down and Arrows, 1919, [1] Wikimedia Commons, Metropolitan Museum of Art
- ↑ Peter Jennings (1976). MicroChess, a Chess playing program for the 6502 Microcomputer. pdf, Courtesy of Peter Jennings, The Computer History Museum
- ↑ Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, Chapter 2 Non-Bitboard Architectures
- ↑ Re: Is there such a thing as branchless move generation? by Daniel Shawul, CCC, June 10, 2012