Hi,
I took a brief look into the source code that was published
here. I think that the programmer has done a good job so far - creating a program that plays correct chess is already a huge work and needs a lot of patience and precision. Congratulations to the author, and welcome to a hobby that will never release you!
In my opinion the program needs a major rework on the design level regarding these points at least:
1) separation of move generation from creation of tree nodes (as pointed out by Daniel, I see this as one of the main problems);
2) memory management: at each node some arrays of bitboards and nodes are allocated using "new" but that memory is never released, and furthermore extensive use of "new" in a chess engine is a huge performance killer.
There might be even more issues, and clearly there is also quite a lot of work to be done from the usual "check list" to turn a program that can "only" play chess according to the rules into a decent chess engine matching our current standards. But before I post that check list (I had actually prepared one but then discovered the major issues above), some redesign appears to be inevitable.
The standard way of move generation is to store all (legal or pseudo-legal) moves of the current position in a move list, where each move is represented by almost minimal information that would be needed to actually make the move on the board when required, usually "from" and "to" square, promotion piece type and possibly also other information like castling type or information to en passant captures or pawn double steps. Moves are then ordered (or assigned a value that can be used to select the next best move) before entering the move loop during search. When a move is selected next, it will be made on the board, and only then you have a new node of the search tree. Creating all successor nodes of the current node during move generation creates really a huge overhead in an alphaBeta search since alphaBeta will visit only a fraction of all nodes, so almost the whole work of creating nodes in advance (and, as in the given implementation, immediately testing it for legality) will be wasted.
It is important that this node will disappear again as soon as the move leading to it will be undone, either directly (if the move was illegal) or after returning from searching its subtree. Dynamic memory allocation is far from optimal for chess engines, but if it is used then at least the memory management must be correct. There are a couple of changes to fix this but it can be done so that the program stops eating up all memory of the PC. The key point is to call "delete[]" at an appropriate time for the two arrays that have been allocated at the end of the growConnections() function. I can help here if required, as well as with some advice for a redesign of the "move generator / search" collaboration. Just PM me.
Sven
