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 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.