Computer Chess Club Archives




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

Author: Robert Hyatt

Date: 05:58:21 04/04/00

Go up one level in this thread

On April 04, 2000 at 04:36:30, Andreas Stabel 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:
>>>>>>>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.
>>>>>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.
>>>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.
>>So I would say that the game of chess has a branching factor of 38, whereas
>>Crafty has a branching factor of 3.
>>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.
>>If you read my original post again, it is clear that I'm talking about Lenoid's
>>branching factor, and not the branching factor for the game of chess.
>I don't agree that the branching factor of chess is 38, I would rather say 31.
>The reason is a scan I did of Dan Corbits game collection giving the
>following statistics:
>Read a total of 1496327 games with 112004996 moves including variations,
>giving an average of 8.45 bytes per move.
>There were 6605 variations (left parentesises) containing 63879 moves.
>Excluding the variations there were 111941117 moves giving rise to
>  113437444 positions, including the start position, with a total
>  of 3545011178 legal moves giving an average of 31.25 legal moves in
>  an average position.
>Andreas Stabel

that might well be a better number for all I know.  However, games is not a
perfect way to find this, as early resignations affect the number, as does
not playing the game out to mate every time...  and not trying all possible
moves but rather following a narrow concept of 'best move'...

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.