🔒 Locked

Move Generation

Started by AndyTang Dec 6, 2002 at 9:49 AM 8 replies 1.8k views

Original Post

Dec 6, 2002 at 9:49 AM

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/

alvaro

Dec 6, 2002 at 10:43 AM

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]

Kylotan

Dec 6, 2002 at 7:36 PM

AndyTang

Dec 7, 2002 at 9:54 AM

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?

RPGeezus

Dec 7, 2002 at 11:50 AM

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

Russell

Dec 10, 2002 at 8:24 AM

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.

fup

Dec 10, 2002 at 9:24 AM

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]

Russell

Dec 15, 2002 at 12:24 PM

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

fup

Dec 15, 2002 at 2:52 PM

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

Russell

Dec 15, 2002 at 6:22 PM

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.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.