Piece-Lists are 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.
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[1].
MEMORY LOCATIONS FOR THE PIECES
COMPUTER
YOUR
PIECES
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[2], 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 capturegeneration. 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.
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[3].
Table of Contents
Piece-Lists are 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.
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 [1].New Architecture
As elaborated in his thesis New Architectures in Computer Chess, Chapter 2 Non-Bitboard Architectures [2], 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
Piece List Traversal
The piece list traversal for instance in move generation is straight forward or backward.Forward
Backward
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 indicesUnmake 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 indicesLinked 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 [3].See also
Publications
Forum Posts
1994 ...
2000 ...
2010 ...
External Links
References
What links here?
Up one Level