(I)ID and PV dropout

[hgm]

The following is a good example of poor search performance, which I think should be curable:

Code: Select all

 12	+1.64	1601.9M	742&#58;47.75	<done>
 12	+1.64	1530.6M	740&#58;04.54	i15h13 i3b10 e11d12 m2e10 f12f11 b10d10! h13f12
 12	+0.81	4237.1M	690&#58;00.43	h15i14 i4i13+ i15i13 i3h5 i13h13
 12	-0.57	2225.2M	626&#58;45.00	m14h14 i3h5 j12h12 i4i13+ i15i13 m4i4 j16i15 h5o12! o14o12 f3o12+ j15l15 i4i13+
 12	-2.55	630.6M	579&#58;28.42	m14i14 h6h15 i14h15 i3h6 i13h13 h6i6 h13i14 i6o12! o14o12 f3o12+ j15l15 o12l11! j12i11 l11j8 i14j13 j8h6 i11h10 i4i15+ j16i15
 12	-3.20	944.3M	450&#58;55.31	d13b15 h6h15 j15h15 i4i13+ i15i13 i3i6 m15l14 i6d11! i13g14 d2i7 j16i15 d11b14! d14b14 i7b14 b16a14 m2c12+
 12	-5.26	2574.9M	365&#58;06.03	d13c14 h6h15 g16h15 i3b10 m14i14 b10d11! h15g14 d11h7 i13h13
 12	-6.82	2594.9M	230&#58;55.83	d13e14 h6h15 j15h15 i3f6 i13h13 f6i9 m14i14 i9i14! g12i14 i4i14
 12	-9.51	3502.1M	114&#58;44.02	j12h12 f3k8 h12h11 k8h11 h15h11 h6h11 j15i14 h11g12+ i13h13 g12g11 e11d12 m2g8
 11	+2.60	1318.6M	43&#58;28.18	<done>
 11	+2.60	539.6M	16&#58;25.80	j12h12 i4i13+ m13i13 i3i9 i15g14 h6h12+ g12h12,h12g12 i9j8 n13j13 j8m11! j13j14 m11n14! o16n14 m2f9
 10	+4.60	192.1M	5&#58;52.31	<done>
 10	+4.60	167.8M	5&#58;03.26	j12h12 i4i13+ m13i13 i3i9 i13i14 i9j10 m14j14 j10j14! d14j14 h6g5 n13j13 m4i4 g15i13
  9	+4.65	45.4M	1&#58;31.54	<done>
  9	+4.65	28.6M	0&#58;54.71	j12h12 i4i13+ m13i13 i3i9 i13i14 i9j10 m14j14 j10j14! d14j14 h6g5 g12f10 m4j4
...

From the first iteration on the search focuses on the move j12h12, because it was left as hash move from the search of a previous position in the game. Initially this looks a good choice, but at d=12 its score suddenly drops from positive to -9.51.

After that the search is in trouble. It knows nothing about the other moves from previous iterations, other than that it can keep their score under +2.6, and has no idea which is best or even reasonable. Their refutation trees are not adequate for the much lower alpha, and have to be restructured completely. (the individual daughter nodes do IID for this.) And many of those now score above the new alpha, improving on the previous PV many times, gradually improving alpha, which takes enormous effort each time it happens.

Aspiration would have been beneficial here; if the d=12 iteration would have start ed with a window {1.60, 3.60} the old PV move, j12h12, and most of the not-so-successful alternatives would have failed low against it at appreciably less effort, and only the move that finally comes up as best would have needed the same long PV-providing search it took now. In other situations, where there is no good alternative, and the entire root score would fall badly, you would suffer a number of fail lows, however, until you enlarged the aspiration window enough to encompass the -9.51 score. So aspiration backfires when despite the score drop the old PV remains best.

Of course you can argue that when the score drops to -9.51 (a disadvantage of about a Queen) the game is lost anyway, and it doesn't matter much how much time you waste. But it can also happen that you were already ahead, and that your score is dropping from +10 to +1, and then it can make all the difference. When your opponent is pondering, thinking long in a position where something good for him can only be found by deep search, giving him much extra ponder time seems ill advised.

If I see a PV drop like this in interactive analysis, I usually restart the analysis immediately. The bad score of the old hash move stays in the hash table, and from the very first iteration on practically excludes this move from the search. So that this search immediately zooms in on the best alternative, and starts building refutation trees for the other moves adequate for keeping them below the score of this alternative. In my experience this can then complete the iteration where the PV score dropped in a few minutes, where it otherwise would take hours.

So I wonder if the search should not restart iteration from low depth automatically. Note that other PV nodes where IID is done are equivalent to the root, so perhaps it should be done there too. This is a bit dangerous, though, because you could get stuck in an infinite loop of restarting (I)ID if the score of some of the moves that flunked out to trigger this restart get lost from the hash table. Perhaps the node itself should keep a copy of the hash entries of all its daughters in its local data, to make sure this info can never be overwritten.

Anyway, a safer (but perhaps less effective) version of this can be done by not restarting the (I)ID from scratch, but just reverting to the previous iteration. So if the PV move from iteration N suffers a disastrous score drop in iteration N+1, don't continue with the other moves at N+1 and the new window, but lower the iteration counter before continuing. This would identify the best N-ply alternative at appreciably lower effort, and then again attempt iteration N+1 with this as PV move. Of course this move can flunk out again at N+1 ply, compared to the (already lowered) score, but you could repeat the procedure until you find a move that doesn't. This way you would never actually lower the iteration count; you would just refuse to accept its increment, and you could only do that as many times as you have moves.

[Cardoso]

Hi,
the lack of replies shows this is a topic not much though out in game tree searching theory. Nevertheless I think it is an important one, since on some FLs my engine takes too long to find the best move, and many times it doesn't find it in the allocated amount of time.

I tried to cure this patological problem but without success.
I tried the following:
1 - only restart ID from ply 1 after a certain depth or time ellapsed, for example 30 seconds.
2 - maintain a counter for each iteration depth (int FLcounter[MAXPLY] of how many restarts happened due to a FL at that iteration and limit it to 2 or 3 times max, after that limit do not allow any more restarts on that iteration. At each new search (new position at the root) zero all counters.

I suspect your idea can sort of work, since we can get the PV moves faster, but to get the "real score" I think we need to get back to the iteration depth where the problem was visible. Ok maybe not exactly at that iteration because of reductions/extensions of PV and non PV nodes are different, so it could indeed happen the algorithm is advatageous, but it must be done right of course.

Anyway when I tried this it really didn't work at the time, I don't remember all the details, I guess I'll try it again but this time instead of restarting to ply 1, maybe I'll try a reduction of maybe 2 or 3 plies in the iteration depth counter.
Another thing I'm not sure is if we should restart immediately on a FL detection (wich was what I did in the past), or wait after relaxing alpha on the current iteration, research and check if the score returned is "much" worse than the score of the previous iteration. If so only then restart/reduce the iteration deepening.

[ZirconiumX]

Well, I read this at first, but was busy.

If my memory serves me correct, Robert Houdart (while he still frequented the forums) mentioned that Houdini does something like this, but it drops three plies when the best move fails low to find a better move.

I think the idea is a good one, but I don't know how much - if anything - it's worth.

[Rebel]

If I see a PV drop like this in interactive analysis, I usually restart the analysis immediately. The bad score of the old hash move stays in the hash table, and from the very first iteration on practically excludes this move from the search. So that this search immediately zooms in on the best alternative, and starts building refutation trees for the other moves adequate for keeping them below the score of this alternative. In my experience this can then complete the iteration where the PV score dropped in a few minutes, where it otherwise would take hours.

Maybe you remember Win Rens with Gambit 80/81, he did the same even without HT back then.

[Cardoso]

Maybe you remember Win Rens with Gambit 80/81, he did the same even without HT back then.

Hi Ed,
I don't know Gambit, but wasn't around 1981/82 that appeared Cyrus chess by Martin Bryant for the ZX Spectrum 48K? I also had Colossos chess and Chess Master.
As a teenager I was fascinated with those programs (still am).
Of course even I could fool them several times but they were still fun.
And to think of the KNs differences between those programs and today's top engines is impressive, cpus evolved a lot since then.
Of course Intel killed cpu progress in recent years by lack of competition, but I think now we are entering in a new phase thanks to AMD's agressive products.

[bob]

In a perfect world, the ideal strategy would be to start at ply=1 again. Every iteration should still reject the failed low move thanks to the hash table, so it is almost like searching from ply 1 again, but with that move completely excluded.

However, when I played with this, I ran into one problem, namely that there is no guarantee that the key TT entries will remain long enough. One example was move A failed low, and it started over and quickly found move B, which was better until it got back to depth 12. But while realizing that B was also bad, it overwrote important entries, so that once again A fails high in early iterations but at depth 12 it once again fails low. And this will continue until time is exhausted and you never get to the best move.

A huge TT is one answer, but obviously it only works in a limited way, since any TT can be overwritten with a large enough tree...

[Cardoso]

How about this:

When probing the hash table and comparing the draft of each hash entry with the current search depth, allways add to the draft a variable wich is allways zero, except when we do the Iterative Deepening restart. We could set it to maybe 1 or 2 plies, this will artificially inflate the hash entries draft and so it can help keeping the previous hash entries in the hash longer.
One variation of this is to do this process only on exact hash entries.
I'm just not sure when to reset that variable back to zero, if only when there is a new position at the root to search, or at the current search when we pass the ID depth that caused the ID restart.

what do you think of this Bob?

[bob]

It might defer the problem, but it won't cure it as you have to use an always store approach or the search will simply stall. And the minute you erase one of these critical entries, you set up for a never-ending iteration loop where the best move fails low, you restart, and eventually that move fails high again until you get to the critical iteration where it fails low once again...

I liked the idea when I first tested it, but after losing a couple of games on ICC, and studying this problem, I remained with my current approach that never re-starts the search, and which will suffer as HGM mentioned at times.

[Evert]

If the point is finding an alternative move, can we not remember the bad move (and perhaps the line / score that proof it is bad), exclude it and search for an alternative?

[hgm]

Well, it is better to remember how bad it was than to absolutely exclude it. There is no guarantee that any of the other moves will be better, so you don't want to force the engine to pick one of those.

To solve the problem mentioned by Bob I proposed to store a copy of all hash entries (or actually just the relevant data in it: score, depth and bound type) of the daughter nodes in the parent. Then you can be 100% certain the info is never lost. The score is passed back to the parent anyway, the requested depth is know there, and the bound type implied by the score and window. It just takes 4 extra bytes per move in the move list.