Author: Uri Blass
Date: 01:35:47 06/18/03
Go up one level in this thread
On June 17, 2003 at 20:08:17, Thomas Mayer wrote: >Hi Uri, > >>> With perfect move ordering, alpha-beta has a branching factor of the square >>> root of the min-max branching factor. > >>No >>It is wrong. >>I think that you forgot a lot of pruning and null move pruning together with >>other ideas reduce the branching factor. > >No, it is correct: A perfect alpha beta with perfect move ordering would need >SQRT(Nodes) compared to Mini-Max. In practice something like 5*SQRT(Nodes) is >true... branching Factor of pure mini-max is 40 if we say that a good guess for >approximately moves is 40... so the branching factor for perfect alpha beta >would be around 6... this is also true when the move ordering is not as perfect, >but the number of nodes per each iteration is higher... > >Nowadays modern chess programs have a branching factor of around 3 or better... >that is done by pruning, nullmove etc.... but as long alpha-beta does not >include any risk to oversee something with implementing forward pruning and >nullmove things can be overseen... thats the handicap... > >Greets, Thomas You need to assume also not using hash tables for pruning. There is an assumption that alpha beta includes no pruning by null move or by hash tables. I do not see a reason to make this assumption when most of the programs use pruning and(or) hash tables. The right sentence is: "With perfect move ordering, alpha-beta (with no pruning including not using the hash tables for pruning) has a branching factor of the square root of the min-max branching factor." Uri
This page took 0.01 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.