25,161
edits
Changes
no edit summary
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==
