Author: Uri Blass
Date: 01:02:49 07/13/02
Go up one level in this thread
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. 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. Uri
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.