Tricks in iterative deepening; was Re: AEGON '97

[Ingo Althoefer]

Robert Hyatt wrote:
>[...]
>This is a classic case of move X looking good for many plies, then move
>Y looking very slightly better, but only because a deeper search thinks it
>is. Probably one more ply and Rebel would have switched back to Nf6. And
>there's not much you can do about this case
>[...]

Probably the following setting saves some computing time in situtations
of this type:

Assume that at search depth t move X gets the best value, and that X was also
best in the previous iterations. Then make the depth(t+1) search for X which
may result in evaluation v(X). Now choose an appropriate epsilon > 0, and take
threshold v(X)+epsilon ( instead of threshold v(X) ) for all the others moves.

So they would displace X only if they were at least epsilon better. Maybe a
choice of epsilon = ca. 0.08 pawn units ( the optimal value will of course
depend on other parameters of the program ) would result in considerably fewer
useless back/forth switches at the top, thus saving computing time. Also such a
small value for epsilon would not suppress moves which were clearly superior.

When my observations a few years ago were right, alt least Richard Lang had
been using this in some of his Mephisto programs.

Ingo Althoefer.

[Robert Hyatt]

Ingo Althoefer (alth...@pdec01.uucp) wrote:

: Robert Hyatt wrote:
: >[...]
: >This is a classic case of move X looking good for many plies, then move
: >Y looking very slightly better, but only because a deeper search thinks it
: >is. Probably one more ply and Rebel would have switched back to Nf6. And
: >there's not much you can do about this case
: >[...]

: Probably the following setting saves some computing time in situtations
: of this type:

: Assume that at search depth t move X gets the best value, and that X was also
: best in the previous iterations. Then make the depth(t+1) search for X which
: may result in evaluation v(X). Now choose an appropriate epsilon > 0, and take
: threshold v(X)+epsilon ( instead of threshold v(X) ) for all the others moves.

: So they would displace X only if they were at least epsilon better. Maybe a
: choice of epsilon = ca. 0.08 pawn units ( the optimal value will of course
: depend on other parameters of the program ) would result in considerably fewer
: useless back/forth switches at the top, thus saving computing time. Also such a
: small value for epsilon would not suppress moves which were clearly superior.

Several of us did this for a long time. Where I ran into trouble with it is when
I started using "PVS", where about 99.9999% of the moves in the tree are searched
with the window N,N+1. When you then "fudge" this window upward, which is what I
did in an early version of CB before I switched to PVS, it actually hurts PVS
performance, because the new null-width window is shifted above (or below, depending
on odd/even plies) the window you used to search the PV move. And 1/2 of the hash
hits from this PV move would not apply to the remainder of the moves that are searched.

Whenever I try this, the performance drop is measurable. Whether it is offset by
not changing moves is a good question. I found that if I set the "delta" large
enough, i could avoid the odd/even flip flop you often see, where it likes X at
ply N, but at N+1 it switches to Y, then at N+2 back to X, and so forth... That
is *horriblly inefficient* and breaks alpha/beta badly. The right offset will
avoid this pretty well.. but it will also mean that you can never improve your
root score by <= "delta".. here's the downside:

You get "stuck" on the first move, and it becomes hard to "leave" it. If the eval
says the second move is +.030 better, shouldn't it be better? If not, then maybe
the eval/search need work? In any case, it is easy to test...

: When my observations a few years ago were right, alt least Richard Lang had