Author: Alessandro Damiani
Date: 00:46:16 03/09/99
Go up one level in this thread
On March 08, 1999 at 14:29:34, Christophe Theron wrote: >On March 08, 1999 at 13:48:48, Steve Maughan wrote: > >>I have come across NegaScout and am wondering if it would be worth implementing >>in my program. I understand the principle but what is the payoff? How many >>extra ply (if any) would it give over a plain old Alpha Beta search? Is it ever >>slower than Alpha-Beta? Does (virtually) everyone do it? >> >>All help appreciated! >> >>Steve Maughan > >NegaScout won't give you an extra ply of depth, but it is nevertheless a >significant speedup. > >The drawback is that in some programs that use the values of alpha and beta to >selectively prunes some subtrees you can have consistency problems when >re-searching. It used to be a problem for me when beta=alpha+1 (which happens >very often with NegaScout). Hash table management can even make things worse. > >But after all, if you succeed in fixing these quirks, NegaScout is slightly >better than AlphaBeta. > >I am still keeping an eye on it in the current versions of Tiger. I have a >"#define NEGASCOUT 1" that I can set to 0 to go back to simple AlphaBeta. From >time to time I run some tests to be sure NegaScout is better. It is indeed, but >not by much. > > > > Christophe Hi! I have changed from Alpha-Beta to NegaScout because of Singular Extensions. The big advantage of NegaScout is that at the root of the search 'tree' you know which move will be the PV-move: if the null-window test tells you that the current move is better than the best move it will be researched and get the best move. So NegaScout gives you more information about the pv than Alpha-Beta. If you use heuristics that change the length of the paths of the 'tree' then you will notice search anomalies (contradictions between a null-window test and a research). To avoid this I have removed the fail-soft part of NegaScout, accepting the consequences. In Fortress I only use Singular Extensions at pv-nodes. Using NegaScout the program accepts a pv only if all singular moves on it are searched deeper and is still best. Of course the cost is high! But I hope that a better forward pruning will change that (the current forward pruning is too risky). Alessandro
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.