Author: Sune Fischer
Date: 11:38:47 07/18/02
Go up one level in this thread
On July 18, 2002 at 13:35:11, Dann Corbit wrote: >On July 18, 2002 at 04:42:20, Sune Fischer wrote: >[snip] >>If they run at the same speed, and you have a lower branch factor, you should >>win. >>If you don't, then I guess your pruning is faulty in the lower plies. >> >>The thing gets muddy when people do pruning/extensions, the simple exponential >>model doesn't really hold water, eg. I suspect the branch factor is not even a >>constant as a function of depth. > >At some point the curve will look like a simple exponential model. > >Near the origin, OF COURSE it is not true. You have all sorts of possible start >up costs -- clearing hash tables, generating lists of structures -- all sorts of >overhead possibilities. > >The whole notion of O(f(n)) behavior is that at some point, the most dominant >part of the function will start to dominate. > >So consider the function: > >f(x) = 5 + 3x + 2x^2 + exp(3*x) > >Near zero, the most important part of this equation is the constant term! > > >We would expect that early on, the branching factor is practically irrelevant, >but very soon it becomes the main focus of the equation. Yeah, but your model: >>C0 * exp( C1 * x) >>verses >>C2 * exp( C3 * x) assumes you have a constant branch factor (C1 and C3). That is probably true for a clean alpha-beta, but you need to prove it also holds when pruning, extensions, hashtables, repetition detection are in use. I believe a more accurate model should include variation with depth: N1 = A1(d) * exp( B1(d) * x) + C1 N2 = A2(d) * exp( B2(d) * x) + C2 with the depth d possibly being a function of x (not to mention a function of position:). -S.
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.