Author: Bas Hamstra
Date: 19:27:09 08/11/99
Go up one level in this thread
On August 11, 1999 at 10:19:09, Robert Hyatt wrote: >On August 11, 1999 at 07:31:10, Vincent Diepeveen wrote: > >>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. > >No it isn't, and this is an easy hypothesis to test: > >search a few positions for an hour each, no null move, no hashing. > >Turn on hashing and see what that does to reach the same depth. > >Then turn on null-move and see what that does. > >Then you can compute exactly what the two things do to shrink the overall >tree. In my testing, I generally find null-move is worth 2 extra plies over >non-null move, using R=2. Stripping out my eval _might_ get another ply as >my eval is 50% of total search time. Stripping out move ordering will lose that >ply right back due to less efficient move ordering. No wait, that's too fast. If you do only material you get *much* more cutoffs. As long as no material can be won, all zero evals so moveordering is *perfect*. Just try Crafty with only material int the opening position. I do get to 18 ply too, in little time. However in other positions than the startposition the difference becomes smaller (though substantial and more than your 50% that is probably based on a profiler, not on testing). Reagars, Bas Hamstra. >22 plies ain't going to happen, much less 30. The math just isn't there. I >have seen _no_ program report depths > 12-14 in the middlegame, except for >Junior which reports depth in 1/2 ply increments. If they can't hit 18-19 >with everything included, they aren't going to hit >20 stripped down... > > > > >> >> >>>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 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.