I also use "nearly" unlimited move lists since I push all generated moves on top of a move stack. Each move list has its own segment of the move stack and stores a pointer to the beginning of that segment and one to the stack top. The move list itself is part of a "position" data structure for which there is a separate stack with one entry per ply of the whole game, including the search. When making a move, the move list of the newly reached position gets initialized by setting both "beginning" and "top" pointers to the "top" of the previous position's move list (thereby having an empty list initially). When unmaking, the previous move list is available immediately since the old "top" had been stored.
Overflow of the move stack could be checked easily but with the chosen limit of the move stack an overflow should never happen in practice. An important detail here is that the position stack contains all positions from the beginning of the game but the move stack only contains moves belonging to move lists from the root of the search. This is because the root move list can always be reproduced very quickly when needed. Otherwise the size limit of the move stack would somehow also depend on the maximum possible length of the game. Access to move list contents of previous moves is never required for me, so I accept to have "invalid" move lists for all positions above the current search root.
Doing it this way uses less memory than maintaining for instance an array of 256 moves for each level of search, either on the stack of the recursive search function or in some data structure. This in turn allows to avoid having a fixed maximum search depth which can never be exceeded by a program due to its internal data structure limits. Given my flexible approach, only the move stack overflow and the maximum number of total moves in a game must be observed.
I think this is mostly well-known and nothing very special or tricky. Nevertheless, for those interested I can post a part of my data structures here, reduced to relevant stuff only:
Code: Select all
class MoveList
{
// ...
Move * m_first; // the beginning of this move list's stack segment
Move * m_top; // the entry where the next generated move would be written to, like in:
// *m_top++ = some_move;
};
class Position
{
// ...
MoveList m_moveList;
Move m_move; // the move that was made on the board from here
// ... and some more status info like hash key, ep target, castling rights, fifty, ...
};
class Game
{
// ...
Move m_moveStack [5000];
Position m_positionStack [1000];
};
Sven
