Author: Robert Hyatt
Date: 07:52:53 03/29/04
Go up one level in this thread
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...
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.