Author: Ralf Elvsén
Date: 02:58:15 07/13/02
Go up one level in this thread
On July 13, 2002 at 02:29:16, TEERAPONG TOVIRAT 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)? >>How much will PVS lower the branching factor with no forward pruning? > > >Hi, > >Quite a while back,I discussed with Ralf about this topic. >He is very good at math. He worked out a formula to calculate >the number of nodes on odd and even ply. We reached a >conclusion that the branching factor from alpha-beta is approximately >the square root of that of minimax ONLY if the minimax branching >factor is much more than 3. It's said in chess we have branching factor >around 40.So, you may try to increase the branching factor to see the >difference. I 'm sorry I can't remember Ralf's formulas. >Perhaps,he may post here again. > >Teerapong I think you are referring to something I wrote about the number of makemoves compared to the number of generatemoves depending on the branching factor N. This number was non-trivial to compute but had a nice limit as N grows. But the effective average branching factor of alpha-beta is the squareroot of N for all N. Ralf
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.