Author: Robert Hyatt
Date: 16:11:50 10/01/03
Go up one level in this thread
On September 30, 2003 at 16:49:41, Gian-Carlo Pascutto wrote: >On September 30, 2003 at 16:34:37, Edward Seid wrote: > >>If you've read my previous posts, you'll know that I'm new to chess programming, >>so my questions may be novice-sounding. >> >>Question 1: >>I've been reading the literature about alpha-beta pruning. Normally, the >>initial call to alpha-beta is with alpha = -infinity and beta = +infinity. If >>one wanted to do a tree search all the way to the terminal nodes, where the >>score would be either -9999 or 0 or +9999, would it make sense to set alpha = >>-9999 and beta = +9999 in the first call to alpha-beta? > >I'd use -10000 and +10000, but it probably makes no difference. > >>In the literature, what is this technique called? (I think it's 'aspiration >>search', but I'm not sure) > >I don't know of any specific name. Aspiration search would be setting alpha >and beta to (for example) -100 and +100 respectively. If the score is indeed >within those two, you'll run a bit faster. If it isn't, you'll need to research. > >>Does changing the alpha and beta values as suggested result in faster cutoffs? >>How much improvement can be expected? > >IIRC aspiration search is very roughly 20% or so? I think I got about 10% typically, but then I lose where I have to re-search so it is probably a bit less than that. > >>To increase performance, would it be worthwhile to explore other algorithms >such as NegaScout, SSS* or MTD(f)? > >Forget about SSS*. The others are ok to experiment with. But focus on >move ordering first. > >>Question 3: >>What is PVS? Can someone explain it in terms of what I already know? (Negamax >>and alpha-beta pruning) > >PVS = Negascout They aren't quite the same. Close, however. > >>Question 4: >>About progressive and iterative deepening, I read in a paper that "this type of >>selective expansion is not performed by programs employing the alpha-beta >>algorithm". What algorithms are able to employ progressive and iterative >>deepening? > >Alpha beta can be combined with iterative deepending. > >-- >GCP
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.