Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Branching factor, make me confuse more that ever.

Author: Robert Hyatt

Date: 17:24:02 04/01/00

Go up one level in this thread


On April 01, 2000 at 13:38:00, leonid wrote:

>Hello!
>
>Maybe you could take me out of my endless confusion about "branching factor".
>Confusion come from the way that you can compare two different games. Would like
>your help in finding useful numbers about this factor.
>
>Reason for concern about "branching factor" is that it make me loose 10 times
>speed when logic search 10 ply deep starting from ply 3.  Calculation was done,
>as precise as I could, comparing brute force search without any extensions for
>two games.
>
>Branching factor for me (I know it is not the usual one but very practical one)
>is division of number of nodes seeing in ply against total number of nodes for
>given ply. If number of nodes seeing was 5 and number of nodes for this ply 32
>-"branching factor" is around 16%.
>
>Confusion is that when I found my branching factor for the entire game it was
>around 7%. When I see the branching factor for the ply over two lowest it is as
>high as 21%. In good games I could see branching factor only starting from ply 6
>and it is around 15%. I have no idea what is the branching factor in other games
>calculated for entire game.
>
>Please indicate me branching factor for entire game and for the ply over 6 if
>you can. It could help me. Please say me this factor only for the brute force
>search. In quick logic my branching factor is different and much smaller.
>
>Thanks for your help,
>Leonid.


the 'branching factor' number is generally used wrongly. It is roughly 38 in
the game of chess, averaged over the complete game.  "effective branching
factor" is the number you are really looking for.  Best way to calculate that
is to do a search, then compute the following:

for each iteration, compute exactly how much time it took. IE suppose you
get the following times:

iteration   time

     1        0
     2        3
     3        9
     4       24

you compute three values:

t1=3-0 = 3;
t2=9-3 = 6;
t3=24-9=15;

you can compute two estimates of your effective branching factor:

b1=6/3
b2=15/6

those are the interesting numbers. IE if you know the time to do a depth=n
search, what do you multiply that by to compute how long it will take to do
depth N+1?



This page took 0.01 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.