Previous Next
With all modifications so far version 4.0 is now down to 1834 characters, leaving ~210 characters for new features. One of the first things I am going to try when version 4.0 is finished (i.e., when I am out of ideas how to shrink it further) is to specialize the first few iterations of the iterative-deepening loop. This could go something like this:
Iteration:
Iterations 1 and 2 could be considered part of a more advanced evaluation. They are not really part of the deepening process. It was just convenient to 'borrow' two iterations from the iterative-deepening loop, since they need a loop over all moves, which is just what a deepening iteration does. The mobility count that results can replace the piece-square table that version 3 uses (saving a lot of characters in the initialization and access of these tables). This far more expensive evaluation will push down the nodes-per-second quite a lot, but that might be worth it. In particular, I want to go this way because it makes the evaluation of King safety easy: during the mobility counting I want to move the King as a Queen, and count phantom King's moves with a large negative weight. This results in a large negative score for a King that looks out into the open.
Another advantage of going through the opponents moves first is that we know in advance when we are in check (even in an end leaf). This information could be used to limit the moves that we try in later iterations to those that resolve the check, and in particular avoid moves that certainly don't (like the null move...).
Iteration 3 is exactly what version 3.2 already does in iteration 1. It implements Quiescence Search by awarding an extension to relevant moves (so far only recaptures). Rather than continuing with a normal one-ply full-width search after it, (or returning with the static evaluation score if we are in an end leaf), I always (i.e. also in QS) want to follow it by threat detection first (i.e. looking what happens if it were his turn, after I do noting). In particular we are interested in immediate material threats, i.e. if the opponent can capture something (this is still a QS, after all). So responses to the null-move will typically be captures with the piece that last moved, not so much ordinary moves that launch a new attack (which would manifest itself only after another null move...).
It is not clear to me yet if such a null-move is best implemented by recursively calling D() again,
or by simply switching colors and generate the null-move responses in the present instance of D()
(and switch back colors after that).
Note that in iteration 2 colors are also switched,
and that I laid out the passes in such a way that below a certain 'depth'
the colors simply alternate from one iteration to the next.
Clear is that the responses to the null move will have to be searched under conditions that do not allow another null move,
i.e. not go beyond iteration 3,
because that would lead to an immediate infinite chaining of null moves.
But if pass 4 generates the responses itself, rather than just the null-move,
this is automatically guaranteed,
and the generated opponent's moves can be further searched under normal QS rules.
Null-move after a null-move response is no problem,
the fact that is likely to be a very bad thing to do
(ignoring the fact that the null-move response captured one of our pieces!)
is enough to have such branches die out pretty quickly.
Anyway, the purpose of threat detection is to see if the score drops substantially compared to the static evaluation if we pass our turn (i.e. if there is a threat pending). It can be skipped if in pass 3 we already found a move that was better than the static score, since the static evaluation is already superseded in that case, and we are not interested to know if it goes down even more. In the same way, if there is no threat, (i.e. if the null-move is not worse than the current static evaluation score, because the opponent does not have any QS-allowed move to beat it), we can skip iteration 5, since it would merely be an exact repetition of 3. Otherwise we have to take the null-move result as the new reference value (rather than the static score), and try to improve on that. To this end iteration 5 will reconsider the QS moves of iteration 3, (they failed low in iteration 3, but might not fail low compared to the new reference), and consider moves that could remove the threat as well (e.g. withdrawal of the threatened piece). The threat-evasion moves considered in pass 5 should not become threats themselves, to prevent infinite progressions of threats, each threat-solving extension causing a new threat that again leads to an extension, threat-evasion extensions should be searched under restricted rules, ignoring counter threats. The purpose of threat-evasion is not to undertake anything new, just to verify that taking the static evaluation in the current position is not overly optimistic. This means the replies to such moves should be treated up to pass 3 only, and the window can be set such that the first move that solves the threat cuts off pass 5 (beta = current eval).
It might seem a bit wasteful to redo in pass 5 what we already did in pass 3. Wouldn't it be more efficient to skip pass 3 and immediately go to 4 and 5? In fact, the answer is a firm NO. Threat detection is a dangerous weapon, that could easily lead to indefinite extension of the tree. Captures, and especially recaptures, sooner or later have to die out, but threats (e.g. checks) can continue forever. If the opponent captures something that I can easily recapture, it would be really foolish to analyze what havoc he can wreck with this doomed piece. Usually it is a lot, and recapturing not only prevents all that but gains our material back as well. Even if we would finally not gain (all) the material back, because we are responding to a winning capture for the opponent, recapturing keeps him busy and might still beat the static score. Thus always look at recaptures first, and only if they don't gain you material you need to consider other options. You could also view pass 3 as an aspiration search, assuming that we will be able to gain material by a recapture, and therefore able to search them efficiently with a narrow window (alpha = current eval). If that did not work we do have to do a re-search with wider window (alpha = null-move score < current eval), but the amount of work wasted on the earlier search was so small that on the average this pays off.
The null-move of iteration 4 is always searched at minimal depth initially, i.e. QS-allowed moves only. If it fails high (i.e. there is no threat, and the static score is already enough to cut off this branch) rather than skipping iteration 5 and starting the ordinary search, we could also deepen the null-move search instead. If it then would not find any threat upto some safe depth, a pre-determined number of plies (usually 2) less than the requested depth, we could refrain from the normal search completely. This saves a lot of search effort, since the normal search would eventually go to full depth, and we might accidentally pick a move that is worse than the null-move (they exist!) to search first, so that we would have to search multiple moves before we achieve the beta cutoff.
The underlying idea is that if the opponent can not hurt us in N-2 ply when we do nothing, the search of our best move to N ply will almost certainly not be able to 'dig up some dirt' either. Because even if there would have been trouble on ply number N-1 after the null-move, we almost always can find a real move that postpones this trouble to ply N+1, (beyond the horizon), if it doesn't actually solve the problems pre-emptively. (E.g. exchange of a piece that he has to recapture first, or a counter-threat on a high piece of his that he then has to withdraw).
These assumptions are dangerous if we have only a few moves, because then there might be zugzwang positions, or the entire situation might be devoid of tactics that could buy time. But the mobility count done in iteration 1 can be used to decide if it is save to go for the null-move pruning, or that we better resume the ordinary search to full depth.
As you can see, the list of wishes is long and ambitious!
But the outline of how to do it is there.
The various topics addressed will grow into independent pages,
directly accessible from the index page, as I implement them.
I won't update the discussion here, so it might become obsolete at some point.
Any bets on how much of all that we will be able to squeeze into 210 characters...???
Previous Next