Chess Programming Wiki
Chess Programming Wiki

PieceLists

Home * Board Representation * Piece-Lists

[ Paul Klee - Birds Swooping Down and Arrows [1] 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.

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

Forum Posts

1994 …

2000 …

2010 …

Re: piece lists advantage with bit-boards? by Ronald de Man, CCC, December 26, 2018 » Stockfish, asmFish

2020 …

Re: PieceList in older versions of Glaurung Chess Engine by Tord Romstad, CCC, June 19, 2021

References

  1. ↑ Paul Klee - Birds Swooping Down and Arrows, 1919, [1] Wikimedia Commons, Metropolitan Museum of Art
  2. ↑ Peter Jennings (1976). MicroChess, a Chess playing program for the 6502 Microcomputer. pdf, Courtesy of Peter Jennings, The Computer History Museum
  3. ↑ Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, Chapter 2 Non-Bitboard Architectures
  4. ↑ Re: Is there such a thing as branchless move generation? by Daniel Shawul, CCC, June 10, 2012

Up one Level

Edit this page on GitHub
Prev
Piece Recognition
Next
Pieces