Move List

From Chessprogramming wiki
Jump to: navigation, search

Home * Programming * Data * Move List

A Move List is a data structure inside a chess program with the aim to collect, administrate and process moves played during a game of chess or inside the search. There are essentially two types of move lists. One type has alternating White and Black half-moves for game notation to record the game, continued by the current path or variation of the search. Same applies for the principal variation as a result of a depth-first minimax search. Secondly, a move list refers a list of generated moves for the side to move of a position, a node of the search tree keeping the edges to its child-nodes to traverse. Move lists are often conveniently and efficiently implemented as pre-allocated arrays rather than linked or doubly linked lists.

Game List

The game list keeps moves of the game already played from the initial up to the current root position of the search, plus the current path or variation actually searching. A global game object maintains an index of the root position, initialized with zero after the game starts. When a move was found and played after search, or a move was entered by the opponent player, it is stored under the post incremented index.

Despite the length of the game may vary, one usually takes a once allocated fixed sized array for a maximum number of half moves to occur in the game, considering MAX_PLY of a deep trailing search. Despite the theoretical maximum length of a chess game of 11797 half moves, as limited by the Fifty-move Rule [1][2], 1024 (or even less) halfmoves should practically suffice [3]. On the other hand, it is not a big deal to reallocate the list rarely.

Sample Layout

                       Move List
                       +---------+ 
Initial Position  ->   |    0    |  1. White move
                       +---------+ 
 moves already         |    1    |  1... Black move
 played                +---------+ 
                       |    2    |  2. White move
                       +---------+ 
                       |   ...   | 
                       +---------+ 
                       |   r-1   | 
                       +---------+ 
Root Position   ->     |    r    |  ply 0
                       +---------+ 
 Current               |   r+1   |  ply 1  
 Variation             +---------+ 
                       |   ...   | 
                       +---------+ 
Searched Node   ->     |    x    |  ply x-r
                       +---------+ 
                       |   ...   | 
                       +---------+ 
                       |   1023  | 
                       +---------+ 

Signature List

A correspondent array might be used for Zobrist- or BCH signatures. Along with remembering an index of the last irreversible move (Halfmove Clock), such a list is handy to recognize two- or threefold repetitions. Since the hash signature list refers positions (nodes) rather than moves (edges), it contains one more element than its corresponding move list, that is even an empty game list and halfmove count zero implies a signature list with one element, the key of the initial position. However, it is not necessary to make that list the same length as the move list of the game, and it may shortened after playing an irreversible move. If the Fifty-move Rule is implemented correctly, 100 entries should suffice.

Parallel Search Considerations

It makes sense each process or thread keeps a local copy of the game move list, at least, depending on the implementation, the search tree part. Assuming the above structures, while starting a parallel search at the root, all move lists (including corresponding hash signatures) in all involved processes or threads are once synchronized by a master, that is copied from index zero up to the root position index. During the parallel search, at so called split points or nodes, the variation of the current search tree from root until this split node, needs to be copied as well.

Search Lists

Search lists keep generated moves for the side to move of a node. Their access in conjunction with move generation is usually hidden behind an iterator interface with two methods, one for initializing the move generator, and a method to get the next move. There could be any finite-state machine and data structures hidden by that interface, for instance an array of 16 direction bitboards, where set bits uniquely define distinct target squares. The advantage of a move list becomes obvious if considering move ordering and bookkeeping, the order of moves generated is usually not the order (except hash- and possibly killer moves) they should execute, which requires to evaluate moves and to assign a score by various heuristics and static and dynamic move and square properties, i.e. MVV-LVA, SEE, dedicated piece-square tables and history scores, to perform a selection sort from the move list, to try the best evaluated moves first in most implementations.

Since the number of moves per side and position may vary, one may think about a dynamically allocated list on the heap, to reallocate if more space is needed during generation. This is quite expensive inside the search and typically avoided. Chess programmers tend to administrate their own once allocated or static array of moves, shared by all levels of the search, or alternatively keep distinct move arrays for each ply of up to 256 moves on the processor stack [4]. Considering possible staged move generation, or even to save move generation at all for hash- or killer moves at confirmed Cut-Nodes, MAX_PLY times average branching factor plus some safety margin seems sufficient for a list shared by all plies of a path of a depth-first tree traversal. However, bounds checking might be applied in a special compiled debug version of the chess program. Further, some programs keep disjoint lists for tactical moves like captures and promotions, and a separate list for quiet moves.

Sample Layout

N ::= MAX_PLY * BF

                       Move List
                       +---------+ 
Root Position   ->  {  |    0    |  first generated move of the search (already tried)
                    {  +---------+ 
 moves already      {  |    1    |           for each ply of the search
 tried at ply 0     {  +---------+          +-----------------+
                       |    2    | <--------| next 2 play     |         
 moves to try       {  +---------+          +-----------------+  Ply 0 
 at ply 0           {  |   ...   |     +----| next 2 generate |         
                       +---------+     |    +-----------------+---+
                       |    i    | <---+        | next 2 play     |   
                       +---------+              +-----------------+  Ply 1
                       |   ...   |              | next 2 generate |
                       +---------+              +-----------------+---+
                       |   N-1   |                  | next 2 play     | 
                       +---------+                  +-----------------+  Ply 2 
                                                    | next 2 generate |
                                                    +-----------------+---+
                                                         | ...            |

Processing the Move List

While starting the search, 'next to play' and 'next to generate' of ply index zero are both initialized with the first index, zero, referring the next free move slot inside the list. Move generation fills the list and increments 'next 2 generate' accordantly. Before actually traversing the move list within the loop of the search routine, the local movelist (so far) starting with 'next 2 play' (inclusive) until 'next 2 generate' (exclusive) may be ordered for best alpha-beta performance, likely assigning scores to the moves to perform a selection sort, possibly swapping moves inside the local list to try apparently better moves early. After picking a move from the list for make move and searching ahead, 'next 2 play', indexing the move just picked, is post incremented. If 'next 2 play' equals 'next 2 generate', no more generated moves are available on that ply-level, and it is about to terminate the move loop, or - if using staged move generation, to start the next generation phase, possibly further incrementing 'next 2 generate'.

This scheme works recursively thoroughly all ply depths. At the start of the search at a node ply+1 it is required to perform following initialization on the search stack:

next_2_generate[ply+1] ::= next_2_generate[ply];
next_2_play[ply+1]     ::= next_2_generate[ply];

See also

Publications

Forum Posts

References

  1. 50-Züge-Regel - Schachmathematik from Wikipedia.de (German)
  2. Eero Bonsdorff, Karl Fabel, Olvai Riihimaa (1966) Schach und Zahl - Unterhaltsame Schachmathematik. Seite 11-13, Walter Rau Verlag, Düsseldorf (German)
  3. Defending Humanity's Honor by Tim Krabbé, see game NewRival - Faile with 493 moves, and playing 402 moves with bare kings!
  4. Subject: Maximum Number of Legal Moves by Andrew Shapira, CCC, May 08, 2005

Up one Level