Author: TEERAPONG TOVIRAT
Date: 23:29:16 07/12/02
Go up one level in this thread
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
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.