Computer Chess Club Archives


Search

Terms

Messages

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

Author: Robert Hyatt

Date: 20:01:47 04/04/00

Go up one level in this thread


On April 04, 2000 at 12:03:27, Tom Kerrigan wrote:

>On April 04, 2000 at 08:56:00, Robert Hyatt wrote:
>
>>On April 04, 2000 at 04:21:07, Tom Kerrigan wrote:
>>
>>>On April 03, 2000 at 22:32:30, Robert Hyatt wrote:
>>>
>>>>On April 03, 2000 at 17:56:20, Tom Kerrigan wrote:
>>>>
>>>>>On April 03, 2000 at 15:33:48, Robert Hyatt wrote:
>>>>>
>>>>>>On April 03, 2000 at 00:06:03, Tom Kerrigan wrote:
>>>>>>
>>>>>>>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.
>>>>>>>
>>>>>>>You are taking a totally different approach to computer chess than everybody
>>>>>>>else in the world.
>>>>>>>
>>>>>>>You are driving a boat when everybody else is driving a car.
>>>>>>>
>>>>>>>This is fine, but the problem is that you are insisting on comparing your boat
>>>>>>>to everybody's car. You're trying to equate sail size to wheel diameter. It's
>>>>>>>possible, but it couldn't be more useless.
>>>>>>>
>>>>>>>Your program does not do quiescence searches, it does not do extensions, it
>>>>>>>probably doesn't do iterative deepening, etc. Comparing your program to other
>>>>>>>programs which DO have these features is not productive.
>>>>>>>
>>>>>>>Until you decide to add these features, you should simply concentrate on
>>>>>>>improving your program and not worry about what other people are doing.
>>>>>>>
>>>>>>>If you have to know, here's how you can compute your branching factor: count how
>>>>>>>many moves you search at each node. Divide by the number of nodes.
>>>>>>>
>>>>>>>-Tom
>>>>>>
>>>>>>
>>>>>>That's not 'branching factor'.  that is "effective branching factor".  Because
>>>>>>at many nodes you search 1 branch, but there are obviously many more moves there
>>>>>>that _could_ be searched...
>>>>>>
>>>>>>this has been a source of confusion almost forever...
>>>>>
>>>>>So it's totally correct for me to say that Crafty's branching factor is 38.
>>>>>
>>>>>-Tom
>>>>
>>>>
>>>>NO
>>>>
>>>>Crafty doesn't have a "branching factor" of 38.  The game of chess has a
>>>>branching factor of roughly 38.  Crafty has an "effective branching factor"
>>>>of 2.5-3.0, roughly.
>>>>
>>>>As I said, branching factor is the average number of legal moves at any node
>>>>in the tree, which is why checkers is often given as 38, while go is on the
>>>>order of 120 or so.  Alpha/beta can 'effectively' lower these numbers, but
>>>>the proper term is then "effective branching factor".
>>>
>>>It seems to me that this issue can be cleared up by drawing some trees.
>>>
>>>If you draw a chess tree, it is pretty clear that the branching factor (branches
>>>from each node) is ~38.
>>>
>>>If you draw Crafty's search tree, it is pretty clear that the branching factor
>>>is ~3.
>>
>>No.. and that is what is causing the confusion.  The branching factor is _not_
>>influenced by the program.  The branching factor stays at 38, no matter whether
>>you search one move per ply or 38... because 'branching factor' is the term
>>used to define the typical number of moves to search at any node in the tree
>>by a minimax search.
>
>Silly me. I thought "branching factor" was a characteristic of a tree. Does this
>mean that the b-tree used by the Windows NT file system has a branching factor
>of 38, too?

Don't know what windows NT file system has to do with chess trees, but the
usual b-tree is an N-ary tree (branching factor N where N is roughly the
number of pointers per index block, but typically a little lower due to what
happens when insertions are done and index blocks are split in half)

But for the topic at hand, "branching factor" _is_ the characteristic of the
tree as you said.  _not_ a characteristic of how the program searches the
tree.  Which is the point.  I can search a chess tree with an effective
branching factor of 1.0, but that doesn't change the branching factor of the
tree itself, which is constant.




>
>>Crafty would therefore have a branching factor of 38.  But we also use the
>
>I said this a few posts ago and you told me that I was absolutely incorrect.
>Seems you are a little confused.
>
>>The literature has always said "38" for chess, period, for 'branching factor'.
>
>Yeah, but the literature never said "38" for Crafty.

the branching factor is _not_ a characteristic of a chess program, its
'effective branching factor' is.  "branching factor" is a characteristic of
the tree, precisely the average number of successors for any node in that
tree.  Which has exactly nothing to do with how you search the tree.  You
can minimax the tree, use alpha/beta.  Or use selective forward pruning.
But the branching factor remains at 38.  The search's effective branching
factor can go down of course...

This is in most any AI book that discusses tree searching...


>
>>>I don't see why you're so keen about this "effective" prefix. As long as you
>>>know which tree you're talking about, it seems unnecessary.
>>How do I know which tree is being discussed?  One term is a constant.  The
>>other is a variable depending on alpha/beta efficiency, forward pruning stuff,
>>etc...
>
>I've never been confused before. Whenever I refer to my program's branching
>factor, I always say "my branching factor" and not "the branching factor of the
>game of chess." I notice that everybody else does this too. Besides, if somebody
>says his branching factor is 5, are you going to jump all over him and explain
>that it's actually 38, or are you going to realize that he's talking about
>something other than chess's branching factor.
>

I simply point out that he is talking about his "effective branching factor"
which is the right term, _not_ "branching factor" which is the wrong term.  If
you like the incorrect term, use it.  However, using consistent terminology
does help discussions.



>>I realize that...  I was simply pointing out the precise term that is correct,
>>such as 'femur' as opposed to "some bone".  Because you could be talking about
>>one bone and I am talking about another.
>
>In this case we are talking about an elephant femur vs. a human femur. But when
>I go to the doctor, he does not make a special point of telling me that my human
>femur is broken, as opposed to my elephant femur.

No, but he probably does say "your femur is broken" rather than "you have a
broken bone somewhere in the upper part of one of your extremities".  Branching
factor means something specific, rather than being a vague term that might mean
the number of successors from the average node, the time ratio of iteration N+1
to iteration N, etc...

It is certainly ok to be imprecise at times, but it does add to overall
confusion at times.  BF means one thing, EBF means another.  99% of the
people using BF here really mean EBF.  Unfortunately, the BF term has already
taken root in AI literature.



>
>-Tom



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.