Author: Gian-Carlo Pascutto
Date: 13:49:41 09/30/03
Go up one level in this thread
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? >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 >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.01 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.