deep search on the same best move

[ericlangedijk]

What bothers me most about my engine is it wastes lots of its time on searching deeper and deeper on the same best move.
We are not interested in a 40 moves long PV but only the best move.
Is there any trick to let an engine search alternatives (maybe unexpected good moves inside the pruning festival) and stop wasting its time on this same first best found move over and over again?

[hgm]

I don't know about your engine, but normal engines do search all moves on every iteration. They just don't report anything about moves that are not the best. They start seraching the best move found in the previous iteration, which leads to a new PV. Which could either be printed immediately, or remembered until the end of the iteration, and printed then. After that they continue to search other moves. But if a refutation for these is found that makes the result worse than the move it already has, it discards them without printing anything. (And this is usually the case.) If they do find a better move, they either print the corresponding PV immediately, or remember it in place of the previous PV they found, for later printing.

If you want information on other moves than the best, you would have to run the engine in multi-PV mode. (And if it is your own engine, program it to support such a mode.)

[Eelco de Groot]

I think Eric means more that 'too much time' can be spent on searching a move which does not have to be searched deeper (unless you are overlooking something deep). In a game, there is just the option to simply play this move, because you might need the time later and to put opponent under pressure. So there is this connection with time management but in analysis sometimes you just want to search better for alternatives instead. Some engines make this a philosophy, not to play the obvious move because opponent will be expecting it. Search all the alternatives. Because one of them may be equally good and will surprise your opponent. Added benefit is you already have two good moves now, so it is a form of IID.

I experimented a little (nothing really Elo tested though) with what I called 'hollow PVs'. Because with null window searches which are essentially cheap, you can do these searches around a more shallow PV (which has an alpha beta window, usually (instead of a null window) and that makes it expensive plus usually you do less nullmove etc. in the PV. So the PV takes up half the time in a standard search (say Crafty, at least that is what we had some of these discussions about in the past) All the other moves at the Root together take the other half. Making them a little longer is not very expensive. But this only takes into account the Root moves. If you want to lengthen other moves with null window searches too this usually means opponent moves (side branches from the Black and White PV moves). So then, for the opponent moves, you are doing essentially a pessimistic search. Not an optimistic search.


Rybka in the beginning I remember, had something like an optimistic and pessimistic search too. This was shortly after the free Rybka. I think V. Rajlich there used for instance a lower Beta. If one of your own choices at the Root now clears this lower Beta where it did not do that before (It is not better than the obvious PV move) then this move may be underevaluated. It is a bit like searching this move deeper (the hollow PV thing) but now it first has to clear the lower Beta.

[hgm]

No, that is definitely not what he is asking. He wants the time saved on limiting PV depth used for finding alternative moves from the same position, not for having more time for finding moves in later positions of the same game.

If I read between the lines he expresses the fear that modern searches prune or reduce all side branches so much that they might miss better moves hidden in there. So the suggestion seems to be to search side branchess with less pruning at the expense of searching less deep in the PV. But of course this is exactly what weaker engines do; the ratio of PV depth to side-branch depth is one of the most tuned design factors for optimizing Elo, and has led to these enormously deep PVs.

From my own experience I recall this fear is not entirely imaginary, though. The idea behind the large reductions is that eventually the side branches will be searched deep enough to find alternatives to the PV with merit, and then promote those to PV. This assumes that the PV score is somewhat stable, though. I once used Fairy Stockfish to analize a mini-Shogi game, in a case where this did not work: it was not able to find the move that provided the quickest win. Because the PV move was already a winning one (in mini-Shogi there are no draws, so moves are either winning or losing), and true winning moves are followed by progress that increases the score, the PV score was diverging to ever higher value. Faster winning alternatives would increase faster in score at the same depth, but this was more than offset by the large reduction they were suffering. If the score per move increases twice as fast, but the branch is reduced by a factor 4 compared to the PV, the score in practice only grows half as fast.

Of course none of this would be recognized by optimizing Elo: a fast win gives you just as many points as a slow one.

[syzygy]

What bothers me most about my engine is it wastes lots of its time on searching deeper and deeper on the same best move.
We are not interested in a 40 moves long PV but only the best move.
Is there any trick to let an engine search alternatives (maybe unexpected good moves inside the pruning festival) and stop wasting its time on this same first best found move over and over again?

Enable multipv.

[ericlangedijk]

Yes! I will enable multipv also in some later stage. Never done that!

The frustration (engine is around 2900 but should be able to reach 3100 at least) is that I am staring at long pv lines always starting with the same old move, while I know there is that unexpected silent crazy only winning move.

Probably some pruning or beta cutoff history parameter is not optimal.