Previous Next
Some of the intended changes turn out not to be improvements, as judged from self play. In particular the two-sided quiescence does not seem worth it. It is too expensive in the current setup, with its slow move generator, which has to scan through all moves for finding recaptures, to test for threats at the QS level.
From testing against TSCP, where micro-Max 4.0 gets a clear whipping at equal search time, it seems that the main shortcomings are not so much tactical as well strategic. In particular, micro-Max is way to passive with Pawns, and it really breaks it that it has no notion of passed Pawns. In addition, it is clumsy with Rooks, and lets the opponent take the 6th rank way too easily. King safety is another blind spot: sometimes micro-Max gets it into its head to run for the center with his King in the early middle game. Needless to say, this then results in a quick mate, or loss of a Queen+ to prevent it. All this is not so easy to fix: it requires lots of specialized code. And what is worse, even when I fix it (going way over my length limit), the score against TSCP does not seem to go up significantly. It just loses in other, less obvious ways.
Many of the games where micro-Max is far ahead because of a good tactical shot, it draws by three-fold repetition or by the 50-move rule. Drawn positions it sometimes loses because it stupidly converts to a lost Pawn end-game. Tactically, it is sometimes outclassed because the 'recapture only' QS does fail to recognize pins, discovered threats and overloads early enough. All this costs many points, and is much easier to fix.
The next version of micro-Max will focus on the tactical and general shortcomings, and for the moment ignore the strategic weaknesses. This means awareness of the 50-move and three-fold repetition rules, in order not to bungle won games, and a penalty for exchanging pieces when it is behind, in order not to lose draws. In addition it will have an improved Quiescence Search that will try all 'good' captures, rather than just recaptures, so that it is not blind to hanging pieces. This improved QS is also a necessary prerequisite for succesful null-move pruning: after a null move there are by definition no recaptures, and the failure to recognise other threats in QS would lead to way to optimistic pruning at low remaining search depth. The implementation of Iterative Deepening will be improved as a side effect of all this.
The new QS will consider all good captures, i.e. those captures that win material in the exchange on the target square itself (evaluated by only taking recaptures into account). To implement this, QS now gets 2 levels, recapture-only QS1, and the more elaborate QS2 (which only adds something if a simple recapture was not already enough for refutation). The latter uses iterative deepening: it always starts as a QS1. In the second iteration (the true QS2) it only considers moves that at QS1 level came out good. QS2 thus is a 'deeper' search than QS1 (2 iterations, in stead of 1).
The decision to deepen the search to the QS2 level has to be taken on a move by move basis. This introduces the concept of 'conditional deepening'. The reply to any capture in the second pass of QS2 has to be searched at least at QS1 level, and only if the score there is above a certain threshold, it is also searched at QS2 level (which usually makes the score go down, because the opponent gets a wider set of possible replies).
To recognize repetition draws, the game history should be recorded. The hash table is the natural place for this, all positions are stored there anyway. Positions that occur in the root (i.e. that are really occurring in the game) should just be protected from overwriting. Their score should be changed to an absolute zero (the draw score). There are so few of such positions (a few hundred in a very long game) that that will not have any impact on hash-table performance.
Of course it should still be possible to retrieve the game-history positions. This requires the hash keys to remain valid between (game level) moves, as is not the case in version 4.0. Preserving the hash keys between moves will have the advantage that the search tree of an earlier move will still be present in the hash table, speeding up the search. Especially in end-games, where the trees get very deep, and the overlap between trees on subsequent moves is very large, this allows a much deeper search.
The repetition draw will only recognize positions that have truly been played. Return to positions occurring in the search tree is not treated as special. So if an eternal check can be forced by a sacrifice, it will probably not see it.
To avoid unnecessary draws by undecisive play in a won position, a fifty-move counter will be added at the game level. It will be cleared on any capture and pawn move. If the 50-move count gets dangerously high when ahead, this encourages Pawn moves. If the position is really won, such Pawn moves sooner or later will bring promotions within the horizon.
Each side will keep track of the number of pieces (non-Pawns) the opponent has left. If behind in total material (value including Pawns) or number of pieces, trading off of pieces is penalized. This piece count can also conveniently be used as a measure of when the end-game starts, and avoid the King to be drawn towards the center before that.
Null-move pruning can be implemented easily in the presence of the previous improvements. To avoid problems with zugzwang, it is disabled when we do not at least have one piece beside the King. The null-move search is always done above QS level, because it doubles as a check test. (In QS the static evaluation acts as the null-move result, and a true search would be too expensive. Check-mates cannot be recognized in QS, so there also is no need to know if we are in check there.)
The replies to the null move are thus always searched at least to QS1 level (which also recognizes King captures, and thus acts as a check test). At this level it returns at least the static evaluation, limiting the null-move score to this value. Only if the static evaluation is good enough to cause a fail high, the null-move search is deepened further (if needed). This is a second case where the deepening of the search is conditional on the score of a previous iteration.
As noted above, there are several situations in which we want to search a specific move to a certain depth only conditionally, i.e. stop at a smaller depth if the score is not good enough. The decision to abort can be conveniently taken in the daughter node that searches the replies: such a node will do iterative deepening, and the deepening loop can be aborted when the score of the best move exceeded a threshold. Both in the null-move search as in QS this occurs.
We could also do that in the process of normal iterative deepening, though: As soon as a move fails high at a certain depth (not yet equal to the maximum depth we want to reach) deepen its search to the maximum, or until it no longer fails high. This has the advantage of wielding out beta-cutoffs that eventually turn out to be red herrings: by deepening the search only for this single move (in the ID loop of the daughter node) the search of the other moves is not disturbed. If we would have deepened in the current node (as is usually done) all other moves except this one would be skipped, as long as the move gave a beta cutoff. If the beta cutoff in the end proved false, we would be stuck at high search depth with no idea which move to try next. To prevent that situation the mechanism of conditional deepening is also applied to cut moves.
Previous Next