Author: Robert Hyatt
Date: 16:09:20 08/11/99
Go up one level in this thread
On August 11, 1999 at 18:10:22, Vincent Diepeveen wrote: >On August 11, 1999 at 14:50:05, Robert Hyatt wrote: > >>On August 11, 1999 at 13:04:02, Vincent Diepeveen wrote: >> >>>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. >> >>Simple enough. I can make such a 'dumb' program easily... Data to follow >>in an hour or so. But before I go off to do this, I can _guarantee_ you that I >>won't get to 20 plies in reasonable time. I've done this before. > > >>> >>>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. >> >> >>I will test with eval doing nothing but a return(0), and no capture search >>of any kind. Trivial to test... >> >>Here are results: crafty with no evaluation (always assumes score=0) and >>no capture search of any kind, and no search extensions of any kind. >> >>First, normal crafty from the opening position, on my PII/300 notebook, >>gets to depth=10 in 60 seconds (finishes 10). >> >>This "broken" crafty gets to depth=22. Which is totally meaningless, because >>it is not only dumb, it is wrong, since it is not differentiating _any_ >>positions at all. >> >>I then did a more useful experiment using evaluation == Material Count only; >>and got to depth=18 in 60 seconds. This still using my null-move R=2/3 search, >>plus razoring, without any extensions at all. >> >>30 plies is impossible. _Totally_ impossible. >> >> >> >>> >>>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!!!!!) >> >>You will _never_ get as good a move ordering as an eval that always returns >>0, because that is _perfect_ move ordering, which is patently impossible. >> >> >>> >>>Of course the overhead of the qsearch adds a factor to the material >>>proggie, which got that 17 ply within seconds at my P100. >> >>your test was worthless, however, because an eval of 0 is meaningless. With >>such a search, you just pick the first move and make it as none will ever be >>any better. No 'search' is needed, and doing a search is worthless. >> >>But when you factor in material, you ain't going to get to 30 plies. >> >>Let's try the math. depth time >> 15 3.23 >> 16 6.79 >> 17 21.91 >> 18 32 >> >>extrapolated: >> 19 64 >> 20 128 >> >>and I am not going to multiply by 2 ten more times (which is roughly 1000 >>times as long to get 30 as to get 20. >> >> >> >> >>> >>>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. >> >>try again. With my test it wasn't instant for 22 plies at all. And you >>_must_ use some sort of eval... and with material only, which costs me >>nothing since I keep that incrementally, I can't get to 22 instantly. And >>I'm not slow... >> > >there is a major bug in your experiment. >getting to 22 plies with returning only a 0 >with 60, i repeat SIXTY seconds, is very little. > >You get around 4 million nodes a second, sorry crafty gets >probably more like 0.5M nodes a second at that hardware with eval=0, >as crafty datastructure is already 2 times slower, and secondly >you're doing all kind of unnecessary things. > >First of all: remove all internal deepening to get a better PVmove, >complete waste of nodes in dumb progs. was already disabled. > >Secondly SORT others. Your sorting is CAPTURE based. That's no >good. first try dumb moves like 1.a3. that slows it down, _not_ speeds it up. For the "really dumb" version I did no sorting at all, but for the material-only version, I just sorted captures first (in order of expected gain) just like always, followed by killers and so forth which _still_ work in a material-only program... > >When you're material up, don't try all kinds of captures first >on perhaps the other side of the board. KEEP IT SIMPLE &quick! > >Use next order: first killermoves, then captures. what would that help? captures are better 'killer' moves than killer moves are. :) > >the trick in these stupid programs is the SORTING. >With a million nodes a second 22 ply should be a few seconds. > I can only say that in every program I have written, ordering makes the thing go _faster_ and not slower. > > >>>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.