Iterative deepening, versus the recursion that it was already doing

[evert823]

I understand that in iterative deepening, we search iteratively from the root node with increasing depth.
After each iteration we order the moves, so that the next iteration checks moves from best-so-far to worst-so-far - but again from the ultimate root node.

Big question is now, in a subsequent recursion step, should I also do this?
I don't think so, I would expect an explosive overhead of iterative deepening on all levels.
But to what extent do we use move ordering when we are already deeper in the recursion?

I am in the middle of adding iterative deepening to my engine.
Before that, it did pre-ordering of moves based on a depth 3 search, which it did on all recursion levels (until too close to the leafs).
That worked fine except that generally, the speed was not so satisfactory.

[hgm]

What you refer to is called Internal Iterative Deepening (IID).

First of all: you cannot really order moves from best to worst. With alpha-beta search you usually have only very few moves that you know the exact score of, even in the root. Often only one. The remaining moves are only known to be worse, i.e. their score is an upper bound, usually even exactly the same upper bound, namely the score of the best move.

The Alpha-Beta algorithm is based on the fact that a single refutation ('cut move') is sufficient, and that it is totally irrelevant what your second-best move can do. This can give an enormous reduction of the search tree compared to plain minimax, provided you search the refutation (if there is one, i.e. in 'cut-nodes') first, and don't waste any time on moves that are not refutations instead. The move ordering thus mainly tries to get the moves with the best chances to be a refutation in front.

Iterative Deepening (in the root) makes sense if the deeper iterations are assisted in picking their cut moves by the earlier ones. If there would be no such information transfer between iterations, it would be pretty pointless. (Not entirely; it would still help to ensure you find a resonable move in a given amount of time, as you would always have a move to fall back on if you don't manage to finish the deepest search you were hoping to perform.) The most elaborate way to do that is to have a Transposition Table, in which all positions that were already searched put their cut-moves, so that when these positions are visited again in the next iteration, these moves can be tried first. In practice cut moves do not often change between one iteration and another, so this is already a great step towards making alpha-beta perform close to its theoretical limit. Without TT you could still remember the Principal Variation from the earlier iteration, and search that first, to get a reasonable 'starting score' (in most cases) in the root.

Sometimes a cut-move that worked in the previous iteration fails to cause a cutoff in the next. Then alternatives will be searched, and you might get into a subtree (perhaps even a large one, if this happens close to the root) that was not explored before. Doing a completely 'uninformed' alpha-beta search takes very much longer than one for which you have cut-move suggestions from an earlier iteration. So in that case it is usually much faster to try a less deep search from the troublesome position first, and use the TT entries this produces to speed up the search at the ultimate depth you were striving for. The gain on the deep search will be much larger than the time spend on the 'pilot' search. And the same argument can apply to the pilot search itself, if that still has significant depth; this will also speed up by doing an even less deep pre-pilot search.

This leads to IID, where, in absence of a TT ('hash-') move you start searching at low depth, and gradually increase the depth to the one that was originally requested. Even without TT you have the advantage that you are able to find a cut-move at low depth (i.e. fast), and have to do the deeper search only on that cut-move if it turns out to hold on to its good score at all higher depths. This is how micro-Max/Fairy-Max does it: IID in every node where there is no hash move, and search the best move of every iteration first in the next one, without any further move ordering. If there is a hash move it starts at the next-higher depth as the one at which that hash move was obtained; if that was the currently requested depth minus 1 (because it was left in the TT from the previous iteration), there isn't really any IID at all; it can start immediately at the requested depth.

[chrisw]

To get round the AB non-ordering, you could try doing full minimax for the first four plies or so, time cost is minimal and you get a full move order, albeit shallow-depthed.

[hgm]

You could even do an alpha-beta search with a more open window than necessary, or slightly opened window, instead of full minimax. I.e. a multi-PV search.

You don't really care whether a move that appears to lose a Queen is searched before one that loses a Rook, or after it, if there are also moves available that don't appear to lose anything at all. So when you search the daughters not with window [alpha, beta] but with [alpha - 80, beta] (in centi-Pawn) for the first few iterations, you get exact score for all moves that do not needlessly throw away material.

I do such a thing in Shokidoki, to decide if it is dealing with an 'easy move'. If all other moves score 100cP below the rest in the root it finishes iterating after 1/10 of the nominal search time. As soon as it finds an alternative move that is closer in one of the iterations, it resets this margin to 0, and continues as a normal search for the nominal time.

[evert823]

For my understanding, you're basically saying this:
Besides remembering which moves are best to worst with current knowledge, I should also remember best to worst responses to each of them, and re-use that knowledge in the 2nd level of my recursion in the next iteration. Is that correctly re-phrased?

E.g. after searching for depth 5, best moves are m1, m2, m3
Best responses to m1 are r1-1, r1-2, r1-3
Best responses to m2 are r2-1, r2-2, r2-3
Best responses to m3 are r3-1, r3-2, r3-3
So in the iteration for depth 6 I should start searching m1, but the in the first recursive call first response r1-1, then r1-2, then r1-3
Then same for m2 and so on

[hgm]

Usual method is to remember only the best move from the previous iteration (whether this is an IID iteration in the node itself, or inherited from a previous root iteration through the TT). Other moves are usually not remembered, and if you are lucky, not even known. Because, in the ideal case, a node searches either only a single move, which then produces a beta cutoff (and is remembered), or none of the moves scores above alpha, and they all get the upper bound alpha to the score, without any possibility to distinguish between them.

So most of the move ordering is 'static', based on the character of the move itself: first the captures, in order of decreasing victim values (with attacker value as tie breaker, so called MVV/LVA), and then the non-captures. If a best move is available from a previous iteration (TT or IID), this preceeds all of those. This would already work quite well. Some engines order captures by scores from the piece-square tables, so that centralizing moves are tried before moves into the corner.

Other commonly used heuristics based on 'dynamic' information that help to order the non-captures (of which there are usually many more than captures) are 'killer' (try the same refutation as the one that worked on the previously searched node at this recursion level, if it is also legal here), and 'history' (collect global statistics throughout the tree on how frequently each move causes a cutoff, and try those that do this the most first).

A refinement of the MVV/LVA sorting for captures is to examine potentially losing captures (like QxR) by a 'Static Exchange Evaluation', which examines whether the skirmish on the target square would lose material ('bad capture'), and postpone search of the move to the very end if it does. (Or search it less deep, or prune it completely, depending on the remaining depth.)