Author: Andreas Herrmann
Date: 09:40:37 08/15/03
Go up one level in this thread
On August 15, 2003 at 07:52:41, Uri Blass wrote:
>On August 15, 2003 at 07:23:04, Andreas Herrmann wrote:
>
>>On August 15, 2003 at 01:50:53, Ed Schröder wrote:
>>
>>>On August 15, 2003 at 01:04:21, Federico Corigliano wrote:
>>>
>>>>What's the formula for calculating the (effective) branching factor in Rebel 12
>>>>(DOS)?
>>>>I'm interesting in add it to my engine.
>>>>
>>>>Greetings,
>>>>Federico
>>>
>>>
>>>Frederico,
>>>
>>>The most easiest and fair rule I could think off is to maintain the time of the
>>>first mainvariation of the current iteration (t1) and the time of the first
>>>mainvariation of the previous iteration (t2), then the branch factor is:
>>>
>>>bf=t1/t2
>>>
>>>My best,
>>>
>>>Ed
>>
>>The branching factor descibes the average number of child nodes. So the formula
>>should be
>>bf = (t1-t2)/t2
>>or better
>>bf = (n1-n2)/n2
>>
>>where
>>t1 = the total time for iterartion n
>>t2 = the total time for iterartion n-1
>>n1 = the total nodes until iterartion n
>>n2 = the total nodes until iterartion n-1
>>
>>Andreas
>
>No
>when people use the name branching factor they mean t1/t2(by your definition
>the best possible branching factor is 0 and not 1).
>
>I do not know definitions from book but the important definition is definition
>that people use and your definition is not what I see used.
>
>Uri
>
>Uri
It's described in several papers. Just search for it with Google.
Excample for the starting Pos, if you would search all nodes, then you have
for white a branching factor of 20 and in the next iteration for black also a bf
of 20.
bf = (420-20)/20 = 20 {for depth 2)
If you use the other formula, you got a wrong bf
bf = 420/20 = 21
But black has not 21 answer moves to each move from white.
And in a check mate position or in a stalemate position, where is no child node
you have a bf = 0.
Here some sample definitions:
a) The average number of successor states for nodes in the search space
is known as the branching factor.
http://www.cee.hw.ac.uk/~alison/ai3notes/subsection2_6_3_4.html
b) ...Because the branching factor (the number of children a node can have) in
a binary heap is 2, the base of the logarithm in O(lg n) is 2 as well. ...
http://www.csee.umbc.edu/courses/undergraduate/341/fall02/projects/proj4/341-Fall02-p4.shtml
c) .. We assume that each internal node has the same number of children; this
number is known as the branching factor. ...
http://www.ics.uci.edu/~eppstein/180a/970417.html
d) The branching factor is the number of possible moves (children).
http://www.cs.rpi.edu/~hollingd/ai/lectures/games.ppt
and so on...
You will find a lot of papers/sources in the net with similiar definitions.
But i also know, that a lot of people calculate the bf wrong.
regards
Andreas
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.