Author: Robert Hyatt
Date: 07:36:59 07/13/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? Your formula is wrong. The correct formula is N = W ^ floor(D/2) + W ^ ceil(D/2) > Now, what is N? It is the number of _terminal_ positions assuming a fixed depth search where every node has exactly W moves to search. IE for pure minimax, N=W^2. If you have 5 moves at the root, 5 moves at each successor position, you have 25 terminal positions. If you want to compute the total nodes within the tree, you have to sum the counts for D=1, D=2, ..., D=N. >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? > the usual shortcut in the formula I gave you is that for D=even, you can replace it by N = 2 * W^(D/2) W^(D/2) is basically sqrt(W^D) note that 2 factor that must be accounted for also... Notice also that a chess tree _never_ has a "constant branching factor" it is dynamic throughout the tree. >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? That is essentially correct. To get down to the 2-3-4 values we see today, requires some sort of selectivity. > >Thanks very much for your replies. > >Russell
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.