Author: Robert Hyatt
Date: 16:10:32 10/01/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? >In the literature, what is this technique called? (I think it's 'aspiration >search', but I'm not sure) >Does changing the alpha and beta values as suggested result in faster cutoffs? >How much improvement can be expected? I would think not. You want a score back, not a bound. Because using -9999 as a bound means that the score of -9999 is enough to cause a cutoff (since we always test score <= alpha or score >= beta). I would use 10000 and -10000 myself. Aspiration search simply means you don't use +/- infinity as the initial alpha/beta window. I use roughly previous iteration score +/- .5 pawn myself. > >Queston 2: >Again, consider the case where searching proceeds all the way to the terminal >nodes. That is, there are no evaluation heuristics and each terminal node score >would be either -9999 or 0 or +9999. So far, I've only experimented with >MiniMax (Negamax implementation) and Negamax with alpha-beta pruning (+/- >infinity, no move ordering). >To increase performance, would it be worthwhile to explore other algorithms such >as NegaScout, SSS* or MTD(f)? >The above-mentioned algorithms are the only tree-searching algorithms that I >know of. What are the names of any others? The main point is to pick one and work with it. I've played with negascout, and mtd(f). I didn't particularly see any advantages with either over the basic alpha/beta PVS variant I have used for 25 years. > >Question 3: >What is PVS? Can someone explain it in terms of what I already know? (Negamax >and alpha-beta pruning) > It is a search that tries to search the minimal tree, similar to mtd(f) except that where mtd(f) fails high or low at every node in the tree, when PVS fails high, it relaxes beta and searches again to get a better idea of the score. I can give you pseudo-code if you need it although there are plenty of examples of it floating around on the net. >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? > I'm not sure what that means. Crafty certainly uses alpha/beta, and it also uses iterative deepening. I assume progressive deepening is the same thing. It works with any alpha/beta variant, from simple alpha/beta, thru PVS, and including things like mtd(f). >Thanks in advance.
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.