Author: Roberto Waldteufel
Date: 07:21:06 06/18/98
Go up one level in this thread
On June 18, 1998 at 00:33:24, Don Dailey wrote: >On June 17, 1998 at 22:25:12, Roberto Waldteufel wrote: > >> >> >>On June 15, 1998 at 12:41:26, Ren Wu wrote: >>> >> >>>I used to use PVS but switch to NegaScout some time ago, but after that >> >> >>Please would you explain what is the difference? I was under the impression that >>PVS and Negascout were one and the same algorithm, namely search first move with >>window [alpha,beta], then search remaining moves with window [alpha, alpha+1] >>with a research if necessary. If this is wrong, I would like to know. >> >>Best wishes, >> >>Roberto > >PVS and scout are the same as far as I know. PVS means principal >variation search. The "nega" in negascout is the practice of >negating the scores from level to level and changing the point of >view of alpha and beta. > >This is to provide a consistant frame of reference and turns min-max >into maxi-max, both sides try to maximize the score. It is a >semantical distinction and changes nothing but makes the code a >little more natural to deal with: > > >/* prototype */ >int search( int alpha, int beta, int depth ); > >/* recursive call with nega-max */ >score = -search( -beta, -alpha, depth-1 ); > > >Sometimes programmers put a window around even the first move. But >the "classic" algorithm searches the first move with alpha and >beta which at root of tree is -INF +INF. > >I use MTD which in a nutshell is ALWAYS using a zero width >window. How you pick the window determines which version of >MTD you use. I use MTD(f) with my own modifications to improve >the behavior of it. > >All these algorithms are just various manipulations of the window >and together they are called "aspiration searches." Using a >window other than alpha and beta is speculative and always risks >doing a re-search but the net affect (at least when using hash >tables) is a general speedup. MTD is the most efficient of all >these because it takes the aspiration paradigm to the limit but >it is also a pain to deal with and has lots of tricky side affects. >Most consider it not worth the trouble. > > >- Don Thanks for your reply:- this is what I thought - basically PVS and negascout are pseudonyms, unless we take PVS to mean that the scores are not negated. I find it confusing therefore to see comparisons made between them as if they were something different from each other. I currently use negascout with a half-pawn window (ie plus or minus a quarter of a pawn), but used Negamax (all nodes with infinite window) before that and found that the zero window searches helped speed things up quite a lot. I am interested to read that you use Aske Plaat's MTD(f) algorithm. I tried this some time back, but, in contrast to Plaat's findings, I did not find it to be as fast as Negascout. Maybe I was doing something wrong, but I found that the number of researches was too high for the speed of null window search to pay off. I found this in tests with programs playing Chess, Checkers and Connect4. How many passes do you typically have to make on each iteration? Of course, in theory you might only need two, but more usually I needed between 8 and 12 passes, and on occasion much more. Perhaps my evaluation functions were either too fine, or too eratic. Idid not find the coding of MTD(f) to be a pain. It's actually less complex than other variants of alpha-beta in the sense that you only need alpha (or beta) to be passed, so fewer parameters on the stack. I was just disapointed that I couldn't make it work as well as my existing Negascout code. Best wishes, Roberto
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.