Author: Leen Ammeraal
Date: 01:44:16 07/26/02
Go up one level in this thread
On July 26, 2002 at 03:43:53, Russell Reagan wrote: >I was curious if anyone was using STL in their engine, or if that is a bad idea. >For example, I considered using an std::vector to store my legal moves in during >the search. After thinking about this, I realized it probably wasn't a good idea >since vector allocates memory dynamically when calling push_back() (if the >vector is full). > >The question I have is whether or not using a vector in this case is a good or >bad idea, or if it won't really affect performance. > >I do recall that vector only allocates memory some of the time, since when it >allocates memory from multiple push_back()'s, it double's it's capacity, so it >doesn't allocate memory every call to push_back(). > >How about using a list? I don't think that would be any better than using a >vector, if there is anything wrong with vector at all. > >Any thoughts? > >Russell I did not even try vectors to store moves because this seemed inefficient to me. Remember, the memory allocated for a vector is usually much more than is initially needed, as the 'capacity' function shows. This is done to avoid immediate reallocation each time the vector grows. If you are interested, you can download the program examples of my book 'STL for C++ Programmers' and try the program 'capacity.cpp' of Chapter 3. I suppose there will also be some inefficiency with regard to time, both for vectors and for lists. (In general, the STL is implemented very efficiently, however, and it is very useful for many applications.) As for storing moves, it seems much better to me to use a simple global array and to keep track of the index of the first move for each ply; in other words, this array is used as a stack. As for your question about chess programmers using STL, well, a long time ago I did use the STL 'sort' algorithm, which is very fast, for move sorting. However, I later changed this, because it is not always necessary to sort all the moves because of beta cuts, so I now repeatedly find the best one and swap this with the one at the top. Besides, the number of moves is so low that it is doubtful if Quicksort is justified anyway. Summarizing, although I have a lot of experience with STL, I do not use it in my chess program (Queen). Leen Ammeraal http://home.wxs.nl/~ammeraal/
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.