Author: Dann Corbit
Date: 10:35:11 07/18/02
Go up one level in this thread
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!
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
double x;
double constant_term = 5;
double linear_term;
double quadratic_term;
double exponential_term;
double y;
puts(" 5 + 3*x + 2x^2 + exp(3*x)=y");
for (x = 0; x < 30; x += 0.5) {
linear_term = 3.0 * x;
quadratic_term = 2 * x * x;
exponential_term = exp(3.0 * x);
y = constant_term + linear_term + quadratic_term + exponential_term;
printf("%2g %7g %10g %15g %g\n", constant_term, linear_term,
quadratic_term, exponential_term, y);
}
return 0;
}
/*
5 + 3*x + 2x^2 + exp(3*x)=y
5 0 0 1 6
5 1.5 0.5 4.48169 11.4817
5 3 2 20.0855 30.0855
5 4.5 4.5 90.0171 104.017
5 6 8 403.429 422.429
5 7.5 12.5 1808.04 1833.04
5 9 18 8103.08 8135.08
5 10.5 24.5 36315.5 36355.5
5 12 32 162755 162804
5 13.5 40.5 729416 729475
5 15 50 3.26902e+006 3.26909e+006
5 16.5 60.5 1.46507e+007 1.46508e+007
5 18 72 6.566e+007 6.56601e+007
5 19.5 84.5 2.94268e+008 2.94268e+008
5 21 98 1.31882e+009 1.31882e+009
5 22.5 112.5 5.91052e+009 5.91052e+009
5 24 128 2.64891e+010 2.64891e+010
5 25.5 144.5 1.18716e+011 1.18716e+011
5 27 162 5.32048e+011 5.32048e+011
5 28.5 180.5 2.38447e+012 2.38447e+012
5 30 200 1.06865e+013 1.06865e+013
5 31.5 220.5 4.78935e+013 4.78935e+013
5 33 242 2.14644e+014 2.14644e+014
5 34.5 264.5 9.61966e+014 9.61966e+014
5 36 288 4.31123e+015 4.31123e+015
5 37.5 312.5 1.93216e+016 1.93216e+016
5 39 338 8.65934e+016 8.65934e+016
5 40.5 364.5 3.88085e+017 3.88085e+017
5 42 392 1.73927e+018 1.73927e+018
5 43.5 420.5 7.79489e+018 7.79489e+018
5 45 450 3.49343e+019 3.49343e+019
5 46.5 480.5 1.56565e+020 1.56565e+020
5 48 512 7.01674e+020 7.01674e+020
5 49.5 544.5 3.14468e+021 3.14468e+021
5 51 578 1.40935e+022 1.40935e+022
5 52.5 612.5 6.31626e+022 6.31626e+022
5 54 648 2.83075e+023 2.83075e+023
5 55.5 684.5 1.26866e+024 1.26866e+024
5 57 722 5.68572e+024 5.68572e+024
5 58.5 760.5 2.54816e+025 2.54816e+025
5 60 800 1.14201e+026 1.14201e+026
5 61.5 840.5 5.11812e+026 5.11812e+026
5 63 882 2.29378e+027 2.29378e+027
5 64.5 924.5 1.028e+028 1.028e+028
5 66 968 4.60719e+028 4.60719e+028
5 67.5 1012.5 2.0648e+029 2.0648e+029
5 69 1058 9.25378e+029 9.25378e+029
5 70.5 1104.5 4.14726e+030 4.14726e+030
5 72 1152 1.85867e+031 1.85867e+031
5 73.5 1200.5 8.32999e+031 8.32999e+031
5 75 1250 3.73324e+032 3.73324e+032
5 76.5 1300.5 1.67312e+033 1.67312e+033
5 78 1352 7.49842e+033 7.49842e+033
5 79.5 1404.5 3.36056e+034 3.36056e+034
5 81 1458 1.5061e+035 1.5061e+035
5 82.5 1512.5 6.74986e+035 6.74986e+035
5 84 1568 3.02508e+036 3.02508e+036
5 85.5 1624.5 1.35575e+037 1.35575e+037
5 87 1682 6.07603e+037 6.07603e+037
5 88.5 1740.5 2.72309e+038 2.72309e+038
*/
We would expect that early on, the branching factor is practically irrelevant,
but very soon it becomes the main focus of the equation.
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.