Author: David Eppstein
Date: 11:00:39 05/15/99
Go up one level in this thread
On May 14, 1999 at 16:14:33, Dave Gomboc wrote:
> Your comment re: silicon may well be right, but apparently Hsu argued in his
> thesis that he achieved better parallel speedup using only one bound, so I
> think this must have been a factor in the decision.
I just looked through his thesis again and I think that's accurate, although he
doesn't come out and say exactly that.
What he does say is: (1) What he calls "weak alpha-beta" (with only one bound,
ignoring deep cutoffs) only loses a factor of (1.07)^depth relative to the usual
two-bound alpha-beta [top of page 63]. (2) Attempts at parallelizing strong
alpha-beta have not worked very well [pages 63-66]. (3) His parallel weak
algorithm provides linear speedup over weak alpha-beta [page 79]. He leaves as
an open research question providing a similarly effective parallization of
strong alpha-beta, or at least of something intermediate between weak and strong
alpha-beta [p.81].
BTW, here's the code he describes for the weak alpha-beta algorithm.
Obviously, it's not PVS or MTD(f), it's just a one-parameter simplification of
the usual alpha-beta. He doesn't claim any originality for this algorithm.
weakAlphabeta(p,beta)
position p;
{
int v,alpha;
position q;
if (terminal(p))
return (value(p));
alpha = -INFINITY; /* not the passed value */
while ((q = nextPosition(p))) {
v = -weakAlphabeta(q, -alpha);
if (v > alpha) {
if (v >= beta)
return (v); /* fail high */
alpha = v;
}
}
return (alpha); /* success-->never fail low */
}
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.