Author: Russell Reagan
Date: 22:38:49 07/12/02
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? 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.