Author: Robert Hyatt
Date: 08:14:43 01/31/01
Go up one level in this thread
On January 31, 2001 at 09:28:58, Vincent Diepeveen wrote: >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. I don't have any idea about how to modify the knuth/moore analysis to take transpositions into consideration. However, while your statement that deeper leads to more transpositions is true, it is practically limited. In the middlegame, nobody is going to do 20+ ply searches, while in simple endings like fine #70, 30-40+ plies is trivial. In the latter case, transpositions go wild. But for 12-13-14 ply searches, I see the hit ratio so low in my program it isn't an issue in the middlegame. IE I need on the order of 32mb per second of search to prevent overwrites in the table. A 100 second search would need 3 gigs, which is not practical. A 20 ply search would need more memory that currently exists on the planet, which makes this impractical. This would be fairly easy to test with today's programs... turn off all extensions, null-move, etc, and let them search as deeply as possible, computing the effective branching factor ply by ply. It will probably get a tiny bit smaller for deeper depths, but not anything significant. > >>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. Yes... but the question is by how much. I would suspect the multiplier is just below 1.0, so that every additional depth drops the branching factor by some amount. I don't think it would _ever_ reach .5 in the middlegame. Of course, in a position where the true branching factor is <= 8 (fine 70 for example) this reduction can get quite large. > >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.