TalkChess.com

[Sven Schüle]

Hi Richard,

your program deals a lot with allocating heap memory, and I think that is a major slowdown. I suggest not to use dynamic allocation at all, at least for everything you do within your search (resp. perft). You might consider using something like this:

- a fixed-sized "move stack" holding all moves being generated during the whole search (e.g. 20 moves for the root position followed by 20 moves for the position at ply 1 followed by 22 at ply 2 ...), logically partitioned into stack segments (see below), and

- a fixed-sized "position stack" (you can also call it "tree" since it contains something like "nodes") holding all data that is needed once per ply, including (maybe) board state, flags, data needed to undo a move, killer moves, other search-related data, and finally data describing the move list of that node which might simply be a pair of "first" and "top" indices referring to the move stack segment belonging to that node (where "top" is one beyond the last used entry, to simplify implementation).

When doing it like this (which is quite common in C/C++ chess programs and should definitely be possible also in C#) your move generator will no longer call "new Move(...)", you will simply overwrite existing Move entries on the move stack each time you generate moves, and your search will not create new nodes but simply move up and down the "position stack" (or tree). Making a move would imply to initialize the new move list like "first = prevNode.top; top = prevNode.top;".

Dimensioning these two stacks is not difficult. A move stack size of 20000 entries and a position stack size of 1000 entries should be sufficient for all future applications, although much smaller sizes are more realistic.

That should also avoid all those "boxing" issues ...

Sven