Author: Sune Fischer
Date: 01:49:17 07/13/02
Go up one level in this thread
On July 13, 2002 at 04:37:31, Dann Corbit wrote: >On July 13, 2002 at 04:02:49, Uri Blass wrote: > >>On July 13, 2002 at 03:39:06, Dann Corbit wrote: >> >>>On July 13, 2002 at 03:36:54, Uri Blass wrote: >>> >>>>On July 13, 2002 at 01:38:49, Russell Reagan wrote: >>>> >>>>>I have a question about alpha-beta. My understanding is that with perfect move >>>>>ordering, you can get your branching factor down to the square root of the >>>>>min-max branching factor. I did a few walk throughs of small trees using >>>>>alpha-beta because I wanted to "see" what the tree looked like (where cutoffs >>>>>occured), and I don't find this to be the case. I did a simple ternary tree walk >>>>>through, and these are my numbers: >>>>> >>>>>Depth=1 : 4 nodes >>>>>Depth=2 : 9 nodes >>>>>Depth=3 : 49 nodes >>>>>Depth=4 : 132 nodes >>>>> >>>>>Using a min-max search the branching factor should be 3. The branching factor >>>>>for each of these depths was 2.22, 2.45, and 2.69 (which looks to be approaching >>>>>3 with added depth). The square root of 3 is 1.73, so am I misinterpreting what >>>>>I heard about the branching factor and alpha-beta? >>>>> >>>>>In other words...If your min-max branching factor is N, then does using >>>>>alpha-beta with perfect move ordering give you the square root of N as the >>>>>branching factor, or is that the lowest possible limit of the branching factor? >>>>> >>>>>If I understand this all correctly, that means that in chess a branching factor >>>>>below about 6 is not possible without using forward pruning (using alpha-beta)? >>>> >>>>You need to assume also that hash tables are not used to prune the tree. >>>> >>>>I believe that pruning is very important and I exepct 2M nodes per second with >>>>recursive null move pruning(R=3) to beat 200M nodes per second with no pruning >>>>if you use 120/40 time control. >>>> >>>>I believe that programs practically can get good branching factor mainly thanks >>>>to pruning and not thanks to hash tables(at least I do because I still do not >>>>use hash tables to prune the tree). >>> >>>But you order your moves from the hash table! >>>;-) >>> >>>Which came first, the chicken or the egg? >> >>This is only better order of moves and we assume perfect order of moves >>for calculating the branching factor. > >I was talking of trying to actually achieve it. Without a hash table, you will >have to have some sort of genius evaluation to approach it. > >>It is clear that hash tables with no pruning means beanching factor of at least >>5 in the opening position and 6 in the middle game. > >I wonder what the best branching factor for a program is. > >I think Pepito and Chess Tiger are both impressive in that regard. Branch factors depend on the search depth, and that is not well defined. Bob and Christophe had a recent discussion about that, and because some use forward pruning instead of extensions, it will seem as though they search deeper and thus has a lower BF. -S.
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.