Dynamic storage in C++ for chess move generation

Question

I'm coding a chess engine in C++ and I'm currently working on move generation. I'm confused as to how I should be storing moves as they are generated. I'm relatively new to C++, but is there some some of dynamic object that I can use to store moves as they come (since I cannot know how many there are).

score 2 · Answer 1 · answered Jul 10 '15 at 07:22

You're looking for something like an std::vector - a template that represents a collection whose size changes dynamically:

Vectors are sequence containers representing arrays that can change in size.

Just like arrays, vectors use contiguous storage locations for their elements, which means that their elements can also be accessed using offsets on regular pointers to its elements, and just as efficiently as in arrays. But unlike arrays, their size can change dynamically, with their storage being handled automatically by the container.

Ah, I was thinking of vector, but I wasn't sure. Thanks! – Shreyas Jul 10 '15 at 07:45 — Shreyas, Jul 10 '15 at 07:45

score 2 · Accepted Answer · edited May 23 '17 at 12:22

2

There are many containers in C++, depending of situation you can use an std::vector, or something else.

As to choose a container would require more information from your chess engine (like how many times would it be resized, does movements can be added at front and back of your container, etc), we cannot give you a direct answer with data that you gave.

Please take a look at this question to define which one would be the most adapted for your case.

edited May 23 '17 at 12:22

Community

1
1

answered Jul 10 '15 at 07:25

Aracthor

5,757
6
31
59

I don't think that Vectors are fitting the requirements of move-generation and -storage in chess, since you would want additional information about the move, for example if it is a hit move/en passant/promotion/castling et cetera. – xXliolauXx Jul 11 '15 at 22:40
You could calculate this information later on, but it would take significantly longer than if you did it directly, and you will need the information many times in your program (move ordering, moving pieces, tts, and so on). I think using a simple custom class would be much more performant and easier to implement. – xXliolauXx Jul 11 '15 at 22:46

score 0 · Answer 3 · answered Jul 10 '15 at 08:10

Many chess engines heavily use recursion. When your think say 5 moves (5 ply) ahead you're actually getting into 5 recursive calls. If you enter a call, the local variables of that function invocation are stored on the stack. So it theoretically it would suffice to have a local "chessboard", e.g. an array of fields, each holding a piece (or being empty) since all the chessboards would be retainend on the stack automatically until their function invocation returns. Since stack space is usually limited, you could also have each invocation (stack frame) only hold a pointer to a piece of heap memory, allocate it when you enter the function, dealloc when you leave it again. Each function invocation returns to it's caller the "score" (cumulative value) of the combinations at a "deeper" recursion level (using the value of pieces as usual (pawn = 1, queen = 9 etc.). Instead of allocating separate boards you could store them in a vector. The advantage is that your memory is less likely to get fragmented. Each invocation can then e.g. hold the index of its chess board state in the vector.

Dynamic storage in C++ for chess move generation

3 Answers3