Author: Bruce Moreland
Date: 21:24:20 01/25/98
Go up one level in this thread
On January 25, 1998 at 22:49:01, James Long wrote: >On January 25, 1998 at 20:00:34, Bruce Moreland wrote: > >> >>On January 25, 1998 at 17:55:45, James Long wrote: >>>Now I'm ready to write some move generation routines. >>>In previous versions of Tristram, I declared a >>>global array CHESS_MOVE moves[MAXPLY][MAXPLY]. >>> >>>This time I'm thinking about using a doubly linked >>>list, or even an array of singly linked list >>>MoveList moves[MAXPLY]. >> >>What is the point of this data structure? I don't know why you'd need a >>memory allocator at all. > >The point? An array of movelist. It contains a list of >moves at each ply. The size of each list varies, which >is why I would need a memory allocator. Make one large one-dimensional array. At the first ply, start filling in moves at offset zero in this array. Keep track of the number there are. Pass this number somehow when you recurse into "search", and start filling moves for that ply at this new index. This is effectively a mark and release scheme with pretty much zero computational overhead. It is fast, takes about ten minutes to implement, and will not be a source of bugs, especially if you protect the last element in the array with an assert. Additionally, it's more memory efficient than your first scheme, since you can dimension this array at a few thousand elements and be done with it, no matter how deeply you search, since you typically won't use very many of the elements. Rather than dimensioning each ply for the worst possible case for a single ply, you can dimension the whole thing for the worst case for all the plies added up, which is a lot less. Finally, this method has been used in other chess programs and is known to work well. bruce
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.