Author: Vincent Diepeveen
Date: 04:31:10 08/11/99
Go up one level in this thread
On August 11, 1999 at 06:29:22, David Blackman wrote: >Start with an ACTUAL branching factor B (ie number of legal moves in each >position). > >For depth N, minimax needs B ** N, apparent branching factor B. > >Plain alpha-beta with perfect move ordering needs k * B ** (N/2) where k is some >small constant. So apparent branching factor is SQRT(B). > >With alpha-beta, nullmove pruning factor R, assume perfect move ordering, and >every move that fails low gets cut by null move pruning, k * B ** (N/(R+2)) so >apparent branching factor is B ** ( 1/(R+2) ) . For R=3 that is fifth root of B. >With B=32 (probably a bit low for a midgame) that would be branching factor 2. B=32 is a bit high, see earlier posts of my: lots of pieces get of the board, and lots of transpositions. So B is a lot less than that. >I don't think you're going to get quite that good for most positions. First it >assumes perfect move ordering. There might be tricks to get close to that. But >also it assumes null move pruning works for almost all failing low moves, and i >don't think that is true. A tempo is often worth a lot. > >Working out a model for effect of transposition tables on branching factor makes >my head hurt. For now i'll just note that in practice it doesn't seem to help >much in the middlegame. So i think apparent branching factors in the range 2 to >4 will be the rule for the moment, for normal mid-game positions. > >If you could get down close to 2 that would make depths of 15 to 20 ply feasible >at normal tournament controls. I guess most of us aren't there yet.
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.