Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Missing a MODEL for the minum branching factor using R=3,hash,a-b

Author: David Blackman

Date: 03:29:22 08/11/99

Go up one level in this thread


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.

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.