Author: Edward Seid
Date: 13:34:37 09/30/03
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? 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? Question 3: What is PVS? Can someone explain it in terms of what I already know? (Negamax and alpha-beta pruning) 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? Thanks in advance.
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.