Previous Next
Micro-Max 3.2 uses the conventional way of internal iterative deepening: at each depth starting from zero up to the requested depth, a normal search process is done. Beta cutoffs are handled within the iteraton: as soon as a move is found with a score above the upper window limit beta, (l in micro-Max), the iteration terminates without searching any further moves. The next iteratiton will then start with this best move, and as long as the fail high persists, each iteration will consider only this single move. If we reach the requested depth through this process, there is no problem.
But if a move that previously failed high at a much larger depth turns out not so good after all, the iteration where this happens would have to start looking for alternatives. The problem then is that micro-Max has no idea whatsoever about the quality of the remaining moves. These have only been considered at a much lower depth, if at all. The risk that a completey ridiculous move is picked next to search at high depth is thus appreciable. Micro-Max does not remember what the second-best move was, and even if it did, it might never have seen this move yet.
In version 4.5 care is taken not to skip any moves of interest at any depth. To not affect the efficiency, it is important to waste time on searching other moves as long as we have reason to expect that there is a move that can cause a beta cutoff that would make the score of these other moves irrelevant. But if the cutoff is not realised after all, the search simply continues where it was when the cutoff candidate was discovered. So if the requested depth is 8, and we the best move in a non-cut 1-ply search appears a cut-move at 2 ply upto 5 ply, but does not fail high anymore at 6 ply, then the search for cut moves will continue at 2-ply level, not at 6-ply level.
To this end the deepening of the cut move is not done by the deepening loop in the node where the move is done, but delegated to the daughter node. The iteration number than simply stays stuck at the value where the cut-move candidate was discovered during the deepening of this single move. As long as the cut-move candidate fails high, meaning the reply fails low in the daughter node searching this move, this daughter node continues searching it at larger depth, all the way to the maximum depth at which it is needed. This way, the search of a move can only result in a fail high if it fails high at maximum depth. Thus, if a move gets a fail-high score, not only does it cause a beta cutoff in the current iteration, but it will immediately terminate all higher iterations as well: it will be the first move considered there, and the hash-table lookup in the daughter will reveal that it had already been searched sufficiently deep with a score good enough to fail high. So there is no need to do these higher iterations, and the beta cutoff might as well jump directly out of the deepening loop.
In all other cases the returned score will not cause a beta cutoff. The iteration will then not be terminated, but continue with the next move. This makes discovery of another good move posible at low search depth, which will then be searched as priority move in deeper iterations. This keeps open the possibility to find another cut-move candidate at the lowest possible cost, which will then deepen itself all the way to a final beta cutoff.
To implement the self-deepening,
the search routine D() does have a second depth argument s.
This argument informs the routine what the maximum depth is to which the current parent
will eventualy deepen the search of this move.
The ordinary depth argument n gives the depth that is requested in the current iteration of the parent.
It is mandatory to reach this latter depth,
while the former depth should be viewed as an optional depth
to which we might surge ahead to get a quick fail low (= cutoff in the parent).
In stead of stopping the iterative deepening when the depth d reaches n,
as long as the search failed low, (m<=q),
it continues deepening past this requested depth upto the eventual depth s.
The required condition to continue the deeping loop is added in the while clause.
The current iteration depth d
(or actually d-1, as we call D() to search the reply, not the move itself),
is passed for n,
while n-1 is passed for s.
Previous Next