Now that you have read my first sentences, you might already have an idea of my next sentence, and especially of the word it begins with. Yes, correct, it is "however"
However, there is at least one thing which I consider to be simply not appropriate for designing a chess engine, and that is the way you deal with the generation of valid moves and their ordering at the beginning of each new node. What you seem to do at each node is:
- you generate all possible moves;
- you store a list of all *positions* resulting from making these moves;
- you check each of these positions for legality, and throw illegal ones out of the list;
- for the remaining list of valid successor positions, you evaluate each of these positions using your normal evaluation function;
- you sort the whole list of positions based on the score;
- finally, you search all moves in that order with a standard alpha-beta search.
If I got this about right then I think this is *by far* more than necessary. Let me tell you what you *should* do instead. I know this would turn out to be a major redesign, and this will hurt you for sure. But you should realize where you stay without it, I think.
- Generate all possible moves, and store the *moves* (not the resulting positions) in a move list. One "move" object represents kind of an "event" and contains at least the square numbers of the "from" and "to" squares plus the type of the promotion piece.
- Evaluate all these moves without actually making them on the board by assigning some simple, static value that can be retrieved very quickly from the move itself plus the current board state. Use this value for move ordering, instead of the evaluation function. Take care that most captures are ordered to the top of the move list. As a first approach, use the MVV/LVA principle to order captures, and some other heuristic, like history heuristic, to order non-captures. Also use the killer move heuristic to improve ordering of non-captures.
- Do not care about move legality in the context of move generation; instead, after making a pseudo-legal move on the board during search, check for legality and return an appropriate value for illegal positions. Due to the many cutoffs alpha-beta implies, this saves many legality checks for positions which never occur on the board.
It is true that there are also a lot of engines implementing a legal move generator. But they do it differently, with a lot of knowledge, for instance about pins or about which moves may be illegal at all and which not. They do not do "make - legality check - unmake" for all possible moves.
If you create a new version of your engine and do it this way, I'm pretty sure this will already give you a boost of about two or three plies.
You can do more, of course. I did not take enough time to read your quiescence search code carefully enough in order to judge about it. But at a first glance, it looks a little bit unusual for me, in that I don't recognize the typical, most important "stand pat" element in your quiescence search algorithm. It seems you are using the same search function for both full search and quiescence search, and I feel there must be something wrong with it. You need to implement quiescence search in a separate function where you start with calling the evaluation function, and if the score does not already cause a beta cutoff, try to improve on this score by searching all captures in an "intelligent" order (e.g. also MVV/LVA which is common).
These are some of the most obvious points for me, although there may be more.
Sven
