Author: Vincent Diepeveen
Date: 10:04:02 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. > >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... > Bob, did you read what i wrote some msgs above this? I'm not talking about DIEP here. Of course i'm not gonna see DIEP get 30 ply soon. Needs already 24 hours to get near 18-20 ply. I was talking about the most dumb program on earth. First variation which is rather simple to make for everyone (doesn't need a qsearch namely, is the case where it returns 0. the second case is a case where it only returns material score. this one is harder to make as u need to sort in an inactive way to get those depths. See my msgs above. in both programs we talk about very good b.f. compared to normal chessprograms. As in normal chessprograms sorting is not near to what is optimal possible (and extensions!!!!!) Of course the overhead of the qsearch adds a factor to the material proggie, which got that 17 ply within seconds at my P100. Fact is that no program simply has the optimal branching factor as there is no model. Now david has written something down which i will study. If it's true what he writes then without extensions and not counting lineair overhead of qsearch with this model of David we see that 30 ply is just a billion nodes, which is about 250 seconds for such a dumbo proggie, so a little more than 4 minutes, where 22 ply as ialready wrote down is done instantly at nowadays hardware. So what we now need is also a term for minimal b.f. for extensions that happen every x-th position. > > >> >> >>>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.