Computer Chess Club Archives




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

Author: leonid

Date: 12:21:46 04/02/00

Go up one level in this thread

On April 02, 2000 at 10:51:07, Robert Hyatt wrote:

>On April 01, 2000 at 22:49:09, leonid wrote:
>>On April 01, 2000 at 20:24:02, Robert Hyatt wrote:
>>>On April 01, 2000 at 13:38:00, leonid wrote:
>>>>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,
>>>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:
>>Do the "iteration" signify simply number of ply? And do you say "get the
>>following times" in the sense of time to solve the position for given ply in
>>(maybe) seconds ?
>>>iteration   time
>>>     1        0
>>>     2        3
>>>     3        9
>>>     4       24
>>>you compute three values:
>>>t1=3-0 = 3;
>>>t2=9-3 = 6;
>>>you can compute two estimates of your effective branching factor:
>>>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?
>>I have the impression that your way to calculate is different from mine. If the
>>word "iteration" I undertood really as it must be.
>>My biggest problem, in all my calculation, was the fact that I can see the time
>>that it took in other games starting from ply 6, on mine AMD 400Mhz. This way I
>>have no access to find the speed for the lowest two plies. And it is those
>>lowest two plies that do the most of the work. They can dramatically change the
>>speed of the entire game. I know, for instance, that you also have written your
>>lowest ply in different way and probably many other did.
>>With my respect!
>what you want is the total time to complete iteration N divided by the total
>time to complete iteration N-1.  Or the total nodes for each, which ought to
>be roughly equivalent.

Probably it is so since they are highly related. For this moment I am looking
only for one factor expecting that the next will be placed automatically. First
factor will be arranged when the time for each next level (half move or ply)
will demand less time increase that now. If best games (brute force search) it
is around 4 or 5 time increase, mine demand 6 or more. This I say when average
number of nodes per ply is around 30 nodes for entire game (for all plies).

If I will see this increase for all the levels (plys) in my game it will be
around 2.1 times (nodes). This small number if due only to the efficency of
lowest two plies. They make increase for the entire game as low as 7%. Average
30 nodes * 7% = 2.1 nodes (times increase). Problem is that I found that my
increase, in demand of time, starting with 6 ply (below are too quick to know
response with other games) is  around 21% or 6.3 nodes (or time increase).

Would like to know:
What is the average time increase that usually game demand in other games for
ENTIRE GAME? I ask this since I am not able to see those numbers in other games
that mine. Only starting with the ply 6 that other best games give some time
possible to compare.

As I said before I am taken by all those "banching factor" since it is the only
reason why I did not started finalizing my game. All basic logic is ready. Even
if my logic could do well its average time, inefficency of the upper plys make
me loose, after my calculation, at least 10 times speed between lowest two plies
and ply 10. My real time up to the ply 10 is good.

Thanks for all suggestions and numbers!


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.