Author: martin fierz
Date: 08:09:19 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 > ah, i didn't know about this factor 2. but of course these are just details :-) >:) > >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... hmm, factor 2 with roughly 90% move ordering, means a gain of roughly 10% less nodes for every move ordering % you improve.... worth looking into then :-) cheers martin
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.