Re: Game Tree Programming Idea: Selectivity via modified alpha-beta pruning

Andy Walker <news@xxxxxxxxxxxx> writes:

Peter Osterlund wrote:

Suppose you search the PV using standard alpha-beta, and suppose it
returns a score of 1.00 up to the root. Using normal alpha-beta, the
remaining moves for the root position would be searched with a window
such that the search terminates as soon as the score is known to be <=
1.00. My idea is to terminate as soon as the score is known to be <=
1.10. You can obviously miss the best move in that case, but not if
the best move is a lot better than the best move you found so far.

OK. In a "straight" alpha-beta search, this does indeed [I
guess, though as always the proof lies in experimentation rather than
intuition] save some nodes at the expense of accuracy. It's less
clear that it saves nodes in some versions of minimal windowing; I'd
need to think a little harder to convince myself!

I agree. Tests are needed to find out if there will be any noticeable
speedup. I know that the corresponding idea can give a very
significant speedup when solving combinatorial optimization problems
using branch & bound, but that doesn't automatically mean that the
idea will be good for alpha beta too.

After finishing such a search, you can be sure that the computed score
is at most 0.10 lower than the mini-max score.

OK. OTOH, if [eg in a tactical situation] your PV turns out to
be a lot better than anything else, then you haven't gained anything,
whereas if there are [in a positional situation] lots of moves with
nearly the same value, then you have thrown away whatever positional
acumen your program in fact possesses. On the third hand, I've known
positions where the computer seems to be "agonising" between two lines
that differ by 0.01, and you want to shake it and say "look, it really,
really doesn't matter whether you play A or B, just plump for one", and
in those cases it could be a big win.

A case I had in mind was this: Suppose move A, B, C, D have
approximately equal score at a given search depth, but at the next
higher search depth, move D reveals a new tactical possiblity, and
therefore has a significantly higher score. In that case if your
search order is A, B, C, D, you want to quickly dismiss B and C as
"not much better than A", so that you have a bigger chance of finding
the tactical opportunity in move D before the time runs out.

(It starts to get complicated though, if you do the same thing at
other levels than the root level in the search tree.)

In general, it's *harder* to do things only at the root level
than everywhere -- it means you need special code for that level.

Sorry, I was unclear again. I meant that analyzing the approximation
error is complicated, not that it is complicated to implement the
idea.

One can quite easily conclude that if you do this approximation (by
amount "delta") at K different levels, the approximation error at the
root is no more than K * delta. However that quickly becomes too large
to be practical if you intend to do it at all levels in the search
tree.

I was thinking that maybe under some circumstances it would be
possible to prove a better bound for the error than "K * delta".
However, proving such a bound appeared to be complicated.

If I now understand you correctly, it just means replacing the code
that assigns the score to alpha by code that assigns (score + 100)
to alpha [if we're measuring in millipawns].

Yes, that's correct.

Surely someone has already tried this? If not, go ahead ...!

Maybe I will. However, I was initially suggesting this as a way to
make the original posters idea work. His idea was in a broad sense
"take something good from branch and bound and apply it to alpha
beta".

--
Peter Osterlund - petero2@xxxxxxxxx
http://web.telia.com/~u89404340
.

Relevant Pages

  • Re: cube root of a given number
    ... ROOT-SOLVING METHOD for computing, say, THE FIFHT ROOT OF 2. ... sheer luck if a best approximation was found. ... to scrutiny." ... remarks you have made in this posting. ...
    (sci.math)
  • Re: cube root of a given number
    ... ROOT-SOLVING METHOD for computing, say, THE FIFHT ROOT OF 2. ... sheer luck if a best approximation was found. ... to scrutiny." ... remarks you have made in this posting. ...
    (sci.math)
  • Re: time complexity
    ... Finding the real value is not exactly a simple mathematical exercise. ... Zeroin returns an estimate for the root with accuracy ... b - the last and the best approximation to the root ... double tol) ...
    (comp.lang.c)
  • Re: cube root of a given number
    ... ROOT-SOLVING METHOD for computing, say, THE FIFHT ROOT OF 2. ... Form the mediant ... you can use your methods for simultaneous approximation of ... sheer luck if a best approximation was found. ...
    (sci.math)
  • Re: Installation of SCREEN with multi access
    ... root" nor "suid alpha". ... What I did do was cd to the binaries directory and then "chmod +s ... It's supposed to be owned by user beta, but with multi set "on" so alpha ...
    (comp.unix.solaris)