Computer Chess Club Archives


Search

Terms

Messages

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

Author: Dan Ellwein

Date: 13:02:28 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?
>
>>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.
>
>>>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 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.
>

kinda adds new meaning to the phrase... 'bone of contention'...

(sorry... couldn't resist)

:)

PilgrimDan


>-Tom



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.