Author: Tony Werten
Date: 23:55:30 03/29/04
Go up one level in this thread
On March 29, 2004 at 10:52:53, Robert Hyatt wrote: >On March 29, 2004 at 10:18:55, martin fierz wrote: > >>On March 29, 2004 at 10:17:18, martin fierz wrote: >> >>>everybody knows that with plain alpha-beta, a fixed number of moves N per node, >>>and perfect move ordering a search to depth D needs >>> >>>nodes(depth) = sqrt(N)^(D/2) nodes. >> >>[snip] >> >>sorry, typo, that should of course read either: >> >>nodes(depth) = sqrt(N)^D or >>nodes(depth) = N^D/2) >> >>but not both... :-) >> >>cheers >> martin > > >Or better: > >nodes = W ^ ceil(D/2) + W ^ floor(D/2) + 1 > >or, for D even > >nodes = 2 * W ^ (D/2) + 1 > > > >:) > >I think someone published a paper on this in the JICCA several years ago, >Schaeffer comes to mind... I'll try to locate it when I get to the office... > >It was analyzing how close to the "minimal tree" current chess programs get. I >think the answer was "2x". IE we search about 2x what a perfectly ordered >search would do... But it is comparing apples and oranges. The theory of perfect tree is without hashtables. Programs get 2x with hashtables, while they should be able to search less than 1x. Tony
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.