Author: Dann Corbit
Date: 23:30:54 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? > >Thanks very much for your replies. Without seeing what the tree looks like, it is hard to comment on what the search should look like. We simple stop searching through a forward "bag" (to use Bruce's terminology) as soon as we see that we get our finger cut off when we reach into it. If there are 20 forward moves possible for (say) ten plies in a row, then a full blown minimax search will search 20^10 =10240000000000 nodes in a ten ply search. An alpha beta search will examine only sqrt(20^10) nodes or 3200000 nodes in doing the same search if you have perfect move ordering. However, suppose that you always guessed the worst move first and the second worst move second... and the best move last. Then your alpha-beta search will search the original 10240000000000 nodes again. So the value in the alpha-beta search only happens fully if we guess the move order in a very good way. The value of the PVS search is that we search the pv move at full width. Then, for all the non-pv moves, we search them with a window only 1 unit wide. This is a huge win if we always guess right. It is a terrible blow if we guess wrong, because we will have to start over with a full-width search. So for PVS also, we must guess the move order correctly most of the time. An additional large savings comes from null move pruning. We simply investigate less fully those moves which look worse than not moving at all. I don't have specific numbers for the reductions in nodes for various techniques, but it seems like an excellent study. Thanks for suggesting it.
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.