Author: Dann Corbit
Date: 11:56:21 07/18/02
Go up one level in this thread
On July 18, 2002 at 14:38:47, Sune Fischer wrote: >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:). Of course, the model is much too simple. For instance, on one ply the branch factor may be 3, then next 3.5 and the next 2.8. Because of extensions (or the lack thereof) a branching factor may change radically from position to position -- especially when a long series of captures or checks is available. But the basic notion serves as a simplifying guide, I think. On the other hand, perhaps Einstein said it best: "Things should be made as simple as possible -- but no simpler."
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.