Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

AndyTang

Move Generation

This topic is 5757 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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/

Share this post


Link to post
Share on other sites
Advertisement
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]

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
Generally speaking, an array (especially a global one) is much faster than dynamic memory.

First, memcpy''s are slow. Second, your linked list will require an extra four bytes, or eight if it''s doubly linked, for pointer information.. This data must be allocated and freed quite a bit throughout your program. In all, you end up doing a lot of extra work for memory managment that will slow down your program..

Memory is hardly at a premium these days, so I would go with arrays if I were you.

Good luck with your program,
Will

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

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

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

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.

That is not good advice.






ai-junkie.com

[edited by - fup on December 10, 2002 10:26:24 AM]

Share this post


Link to post
Share on other sites
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):


  
// just from memory

int alpha_beta (int depth, int alpha, int beta) {
if (depth == 0) return evaluate();
vector<move> moves; // some memory allocation occured here (in some implementations)

generate_moves(moves); // more will occur here

for (vector<move>::iterator i = moves.begin(); i != moves.end(); ++i) {
make_move(*i);
int score = -alpha_beta(depth-1, -beta, -alpha);
undo_move();
if (score >= beta) return beta;
if (score > alpha) alpha = val;
}
return alpha;
}

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

Share this post


Link to post
Share on other sites
Hi Russell,

" suppose you could use vector like a stack, and allocate a big chunk of memory before the search, and then make use of that"

Precisely.

"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."

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.

And responding in particular to your last comment, which is not good advice to readers of this forum. std::vectors are extremely usful tools when you learn to use them properly. They almost always should be used in place of a standard array(if that type of container is appropriate of course). They give you increased flexibility and the option to easily switch containers (like to a std::list for example) if down the road a std::vector is found to be inapropriate.








ai-junkie.com

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!