25,161
edits
Changes
no edit summary
'''[[Main Page|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|moves]] played during a [[Chess Game|game of chess]] or inside the [[Search|search]]. There are essentially two types of move lists. One type has alternating White and Black half-moves for [[Game Notation|game notation]] to record the game, continued by the current path or variation of the search. Same applies for the [[Principal variationVariation|principal variation]] as a result of a [[Depth-First|depth-first]] [[Minimax|minimax]] search. Secondly, a move list refers a list of [[Move Generation|generated moves]] for the [[Side to move|side to move]] of a [[Chess Position|position]], a [[Node|node]] of the [[Search Tree|search tree]] keeping the edges to its child-nodes to traverse. Move lists are often conveniently and efficiently implemented as pre-allocated [[Array|arrays]] rather than [[Linked List|linked]] or [[Linked List#Doubly|doubly linked lists]].
<span id="GameList"></span>
=Game List=
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 [[Iteration|iterator]] interface with two methods, one for initializing the move generator, and a method to get the next move. There could be any [https://en.wikipedia.org/wiki/Finite-state_machine finite-state machine] and [[Data|data structures]] hidden by that interface, for instance an array of [[Pieces versus Directions#DirectionWise|16 direction bitboards]], where set bits uniquely define distinct [[Target Square|target squares]]. The advantage of a move list becomes obvious if considering [[Move Ordering|move ordering]] and bookkeeping, the order of moves generated is usually not the order (except [[Hash Move|hash-]] and possibly [[Killer Move|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]], [[Static Exchange Evaluation|SEE]], [[Piece-Square Tables|dedicated piece-square tables]] and [[History Heuristic|history scores]], to perform a [https://en.wikipedia.org/wiki/Selection_sort 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 [[Encoding Moves#MoveIndex|256 moves]] on the processor stack <ref>[https://www.stmintz.com/ccc/index.php?id=424966 Subject: Maximum Number of Legal Moves] by [http://onezero.org/ [Andrew Shapira]], [[Computer Chess Forums|CCC]], May 08, 2005</ref>. Considering possible [[Move Generation#Staged|staged move generation]], or even to save move generation at all for [[Hash Move|hash-]] or [[Killer Move|killer moves]] at confirmed [[Node Types#CUT|Cut-Nodes]], [[Depth#MaxPly|MAX_PLY]] times [[Branching Factor|average branching factor]] plus some safety margin seems sufficient for a list shared by all plies of a path of a [[Depth-First|depth-first]] tree traversal. However, [https://en.wikipedia.org/wiki/Bounds_checking bounds checking] might be applied in a special compiled debug version of the chess program. Further, some programs keep disjoint lists for [[Tactical Moves|tactical moves]] like [[Captures|captures]] and [[Promotions|promotions]], and a separate list for [[Quiet Moves|quiet moves]].
==Sample Layout==
* [http://www.talkchess.com/forum/viewtopic.php?t=53820 std::vector<> considered harmful] by [[Folkert van Heusden]], [[CCC]], September 25, 2014
* [http://www.talkchess.com/forum/viewtopic.php?t=61792 Max moves in a position] by [[Laurie Tunnicliffe]], [[CCC]], October 22, 2016 » [[Chess#Maxima|Chess Maxima]]
* [http://www.talkchess.com/forum/viewtopic.php?t=64642 Move list in stack vs heap ?] by [[Patrice Duhamel]], [[CCC]], Julyx July 18, 2017
=References=
