Author: Vincent Diepeveen
Date: 06:28:58 01/31/01
Go up one level in this thread
On January 30, 2001 at 21:10:12, Robert Hyatt wrote: >On January 30, 2001 at 17:46:28, Severi Salminen wrote: > >>Hi! >> >>What is the definition of BF and how is it calculated (this has probably been >>discussed N times, but...)? Now I'm calculating like this: >> ______________________ >>BF=(DEPTH-1)|(Nodes/root_move_count) >> >>So it means (DEPTH-1)th root. >> >>Example (from Vincent's position): DEPTH=9 plies, Nodes=2'000'000 and we have 38 >>legal moves in root. >> ____________ >>BF=8|2'000'000/38 = 3.9 >> >>Could this be close to the truth? >> >>Severi > > >There are two terms that are intermixed often: > >1. "branching factor" usually means the average number of branches from a >node, which for chess averages 35-38 (depending on who you believe) for the >whole game. 35 is true for human games. For computer games in middlegame it sure is 40, all my measurements can out at 40 exactly. Note i only counted legal move generation. Progs which don't do legal moves will be above 40. >2. "effective branching factor" is roughly calculated as you mentioned. IE >nodes for iteration N-1 divided into nodes for iteration N. Or you can use >the time. > >This is really "effective branching factor" because there is _nothing_ that >can reduce the true branching factor other than pure forward pruning, where >some moves are thrown out at each and every ply with no searching of any >kind. IE for Crafty, EBF is roughly 3.0... which is actually impossible >on the surface since alpha/beta reduces the branching factor by roughly >the square root of it. square root of 38 is just over 6, which is a This is partly true. the deeper you search the more transpositions you have effectively reducing the number of moves you need to *theoretically* search. So where the average number of legal moves i measured in middlegame is 40, with reduction of transpositions it is *a lot* smaller. I don't know a SINGLE model of alpha beta where people took into account transpositions. So all theoretic models can be already thrown overboard when talking about an alpha-beta search with transpositiontables. >reasonable branching factor for alpha/beta. To get lower, in the case of >crafty, rather than culling some moves by not searching them at all, I simply >search many of them to a lower than usual depth because of the null-move R >value... >numbers around 3 are very good IMHO. I only wish mine stayed there all the >time. But it can easily run up to 10 or more in oddball positions where >the move ordering breaks down at deeper depths... If fliprate (chance a position which you need to search was already in hashtable for some reason AND position was stored as being then <= alpha but now after being searched flipped to >= beta) is small, then effecitively you are busy researching the same tree over and over again, which greatly reduces branching factor when getting at bigger depths where loading factor alpha of hashtable is very big. More probes of course also help a bit, but especially when you search the same tree over and over again. As soon as you start to explore new domains, then the big problem starts. Of course getting new moves as principal variation also means you start exploring new domains, a few new PVs each ply let the branching factor sometimes explode here as well as unlimited extensions, but *not* something else. With a real huge hashtable, branching factor obviously needs to get smaller and smaller when searching deeper. Other forward pruning as nullmove does make the overhead of the number of nodes less here, but definitely never improved my branching factor at big depths. Vincent
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.