Im trying to make a move generation algorithm for a game similar to chess. Is it better to have a big array (to account for so many moves in the game) or is it better to make a link list (to save memory) but how much speed will the allocation of memory waste/

Use one big array. A linked list will not save any memory. The dynamic allocation/deallocation of memory will kill your speed. I don't use any at all.



[edited by - alvaro on December 6, 2002 11:43:47 AM]

If you''re in C++, consider using std::vector - it gives you most of the advantages of both arrays and linked-lists when used correctly.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Thanks for that...

I heard having things on a stack would also slow things down... so should I have most of the variables global (or as a class members with a class) so I have less things on the stack and as parameters...

Will it make that much of a differenece?

I have had this discussion many, many times with chess programmers who have been programming chess for decades, and some of who are authors of some of the strongest programs in the world. I tried, and tried, and tried, to get them to agree that using an std::vector to store moves from move generation. The ONLY responses I recieved were that a serious game playing engine would NEVER use std::vector for that purpose, or do any kind of memory allocation during a search.

My opinion is that if you''re doing something "just for fun" or just to learn how something works, then it''s ok to use std::vector or a linked list. If, however, you''re doing something important, or you want your program to be strong, go with the large array. That''s how I do it.

quote:Then it would seem they don''t know how to use std::vector properly

I''m not an expert on the "use" of std::vector, but I know how it works. I had to implement it (and std::list, and std::map) in a CS class once.

Maybe you could explain how you plan to use std::vector to store legal moves without ever doing any memory allocation. If you add things to a vector, you do allocation. In some implementations, you do allocation just by declaring the vector. You can see this by declaring an empty vector, then querying it''s capacity() method. In chess, for example, there are an average of ~36 legal moves in any given position. That means that you will do 7 memory allocations, 7 copies of the entire contents of the vector, and 7 deallocations of the previously allocated memory at each node.

quote:Why do you think that using std::vector would necessitate memory allocation during the move generation?

Because that''s how std::vector works. For example, if you do something like (see comments in code):



Memory allocation can be not so bad to quite costly depending on what happens. You could add on 10-1000 or more cycles for every memory allocation depending on what happens, and inside an inner loop like the search in a game playing program, that could be a major performance hit, especially since you''re going to be doing this entire process an average of 7 times for each node you visit. You could call reserve() and hope you allocated enough space so that you can avoid any reallocations.

I suppose you could use vector like a stack, and allocate a big chunk of memory before the search, and then make use of that, but even in this case, there is no need for the use of vector, and the simplest approach would be to use a normal array.

Russell

quote:Quite right. But I was responding to this comment: "The ONLY responses I received were that a serious game playing engine would NEVER use std::vector for that purpose" . As you point out, there is little difference in methods if the memory is allocated prior to the move generation. So the experts are obviously uninformed.

When I asked the "experts" it was always in regard to a situation where memory allocation would be required during the search. You should also understand that the people I heard this from are people who are very serious about computer chess. They are the people who have been doing it for decades and who will travel across the world to compete in computer chess events with their programs. Speed is a very important factor. If using a standard array is 5% faster than using a giant pre-allocated vector, the array gets used. Besides, most of them program in C w/ some assembler. Some of these people go to great lengths to squeeze every last cycle they can from the computer, getting MMX and the main cpu and the floating point cpu all working in parellel, highly optimizing for a particular cpu''s instruction pipe, etc.

There really is no gain from using a vector in the way you specified. At the least, there will be a small amount of overhead in the added conditional to test if the vector needs to allocate more space and any other book keeping it needs to do.

So for the rest of us who are never going to participate in the World Computer Chess Championship, use std::vector until your fingers fall off.