Author: Pham Minh Tri
Date: 05:22:37 11/01/00
Go up one level in this thread
On November 01, 2000 at 00:17:29, Robert Hyatt wrote: >On November 01, 2000 at 00:15:50, Robert Hyatt wrote: > >>On October 31, 2000 at 22:37:37, leonid wrote: >> >>>On October 31, 2000 at 22:01:05, Robert Hyatt wrote: >>> >>>>On October 31, 2000 at 19:47:52, Pham Minh Tri wrote: >>>> .... >> >> >>First, the _right_ formula: >> >>N = W^floor(D/2) + W^ceil(D/2) + 1 >> >>floor is D/2 rounded down to nearest int, ceil is rounded up to nearest int. >> >>D is the depth of search >> >>W is the width (or number of nodes at each position) >> That formula (exactly N = W^floor(D/2) + W^ceil(D/2) - 1) is found by D.E. Knuth and R.W.Moore in their article entitled "An Analysis of Alpha-Beta Pruning" in Artificial Intellegence 6 (1975). It could be broken into two formulas for easier computing: N = 2*W^(D/2) - 1 for D even (I use this before) N = W^((D+1)/2) + W^((D-1)/2) -1 for D odd And this result could be achieved only in the optimally-ordered tree, when "the best move is considered first at each position". I think this requirement is very difficult to meet in practice. In their article, the authors did not mention hashtable, nullmove, rasoring (some of them ware still not discovered). So I think the formula must give us a large number, much more than the ones of the modern programs. And no chess programmer want to reach that number. >>Since for a modern program, D is dynamic, and for _all_ chess programs W is >>certainly not a constant, this can't be used for anything useful. >> >>The way to find optimal N is to do a search to depth=N, and save the best >>move at each ply where there is a best move, using the hash table (it must >>be big enough to not overwrite _anything_). During this search, you get your >>value for N. Then re-search, but always search the hash move first, to give >>optimal move ordering. Now you get optimal N. You can compare those... > > >I should add that the quoted within 30% of optimal seems wrong. I recall >Hans Berliner doing a test like this and I believe he quoted 100%. IE the >searched tree was about twice as big as the optimal tree, which is _still_ >very good since we can't possibly have perfect move ordering.
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.