Author: Robert Hyatt
Date: 07:12:28 03/30/04
Go up one level in this thread
On March 30, 2004 at 02:55:30, Tony Werten wrote: >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 I am ot sure that is true. IE some hash hits shrink the tree. Others make it bigger...
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.