Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Definition of branching factor?

Author: Tony Werten

Date: 02:39:41 01/31/01

Go up one level in this thread


On January 30, 2001 at 21:10:12, Robert Hyatt wrote:

>On January 30, 2001 at 17:46:28, Severi Salminen wrote:
>
>>Hi!
>>
>>What is the definition of BF and how is it calculated (this has probably been
>>discussed N times, but...)? Now I'm calculating like this:
>>              ______________________
>>BF=(DEPTH-1)|(Nodes/root_move_count)
>>
>>So it means (DEPTH-1)th root.
>>
>>Example (from Vincent's position): DEPTH=9 plies, Nodes=2'000'000 and we have 38
>>legal moves in root.
>>     ____________
>>BF=8|2'000'000/38 = 3.9
>>
>>Could this be close to the truth?
>>
>>Severi
>
>
>There are two terms that are intermixed often:
>
>1.  "branching factor" usually means the average number of branches from a
>node, which for chess averages 35-38 (depending on who you believe) for the
>whole game.
>
>2.  "effective branching factor" is roughly calculated as you mentioned.  IE
>nodes for iteration N-1 divided into nodes for iteration N.  Or you can use
>the time.
>
>This is really "effective branching factor" because there is _nothing_ that
>can reduce the true branching factor other than pure forward pruning, where
>some moves are thrown out at each and every ply with no searching of any
>kind.  IE for Crafty, EBF is roughly 3.0...  which is actually impossible
>on the surface since alpha/beta reduces the branching factor by roughly
>the square root of it.  square root of 38 is just over 6, which is a
>reasonable branching factor for alpha/beta.  To get lower, in the case of
>crafty, rather than culling some moves by not searching them at all, I simply
>search many of them to a lower than usual depth because of the null-move R
>value...
>
>numbers around 3 are very good IMHO.  I only wish mine stayed there all the
>time.  But it can easily run up to 10 or more in oddball positions where
>the move ordering breaks down at deeper depths...

Is this only in odd positions or do you notice ebf going up with dept as well ?

In my program it seems impossible to keep ebf below 3 if dept becomes bigger
than say 12. ( except for endgame positions )

Tony




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.