Author: Jeremiah Penery
Date: 11:00:43 10/17/99
Go up one level in this thread
On October 17, 1999 at 12:48:54, Ratko V Tomic wrote: >The effective branching factor would be a _constatnt_ branching >factor which would produce the same number of nodes at the >bottom of the tree for the same depth as the actual tree had >(in the actual tree the branching is not constant; it may vary >from node to node). So by the definiition you have relation: > > N = B ^ D > >where B is the effective branching factor, D is depth and N is >the number of evaluated nodes (the leaf nodes since internal nodes >are not evaluated). From here you can calculatete B as: > > B = exp(ln(N)/D) > >which is what I used to calculate B for the examples. Using >ratios of processing times for Time(D+1)/Time(D) is only an >approximation which ignores the times spent outside of the >evaluation function. 'T' is the _total_ time for the search. From the time the search begins to when it ends, it is exactly what a stopwatch would show for the time. It counts move generation, evaluation, hash table lookups, TB probes, etc. > Namely, in that case the number of nodes >evaluated at any level would be: N=T*NPS where NPS is nodes _evaluated_ >per second (not same as nps in your column) and T is processing time >in seconds. Since the branching factor (as defined earlier) is the >ratio of N's for D+1 and D, you do get B=T(D+1)/T(D). But since >relation N=T*NPS isn't accurate, since some time is spent outside >of the evaluation function, i.e. the actual relation is T=N/NPS+X, >where X is this extra time outside of evaluation, the B obtained via >time ratios is only an approximation when X is ignored. > >Applying this to your table you will have: > >Depth Tot.kN Delta.kN BF Time[s] kN/s >-------------------------------------------- > 8 1044 .... .... 9.5 110 > 9 2121 1123 2.18 18.5 115 > 10 5782 3661 2.27 47.75 121 > 11 15431 9649 2.30 124 124 > 12 62174 46743 2.45 495 125 >-------------------------------------------- By the equations you gave, I can see that these numbers are correct. However, I still don't (logically) see how, for example, the BF at depth 12 isn't around 4 or 5. It took 4x as long (total time) to complete depth 12 as depth 11, and 4.88 times as much DeltaTime (12-ply time minus 11-ply time) than D11. Also, the Delta.kN was 4.8x higher for D12 than D11, and it is 4x the amount of total nodes. >So your Crafty (ver 16.19) does have much smaller effective branching factor >than the one which came with Fritz (ver 16.6). The B might be also dependent >on settings (I used defaults). Your version seems to be rigged for a more >selective search (it goes deeper but possibly is less accurate). I used the default settings, too (except for my source modifications). Actually, I would think my modifications would have the opposite effect - I reduced the R-value for the null-move reduction, which should make the branching factor higher, and make the search more accurate. *shrug*
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.