Author: Robert Hyatt
Date: 14:27:52 09/20/98
Go up one level in this thread
On September 20, 1998 at 14:27:37, John Coffey wrote: >Let us say we are in a normal middle game position with about 30 leagal moves >per side. Years ago I heard that an alpha algorithm would expand the tree >about 30^N where N is the number of ply deep. I also heard that an alpha-beta >algorithm would expand the tree about 30*6^(n-1). More recently I have heard >that some algorithms improve upon this quite a bit. both are wrong. Minimax searched W^D nodes (W to the D power). Alpha/Beta reduces this to N=W^floor(D/2)+W^ceil(D/2), where floor = round down to int, ceil = round up to next int. For D even, this is simply N=2*W^(D/2) So, roughly, alpha/beta reduces the branching factor from W to sqrt(W). To drive it below that, requires unsafe tricks. IE null-move is one big winner here, because some nodes are searched less deeply than others, which can reduce the effective branching factor from sqrt(W) to something even less, approximately 2.5-3.0, roughly, in Crafty... > >One program claimed to be getting 2 to 3 raised to the N depth, but this I find >hard to believe. > >John Coffey It's actually right, and you can confirm this by picking a position, and using crafty to search it to a fixed depth (sd=N command). Try sd=1, then 2, etc... and write down the total nodes searched for each search... you can compute the nodes searched for ply=N by subtracting the nodes for ply=N-1 from ply=N. Then compute the branching factor by dividing nodes(n)/nodes(n-1) and watch the numbers... Bob
This page took 0.02 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.