Computer Chess Club Archives


Search

Terms

Messages

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

Author: Dave Gomboc

Date: 17:46:32 08/11/99

Go up one level in this thread


On August 11, 1999 at 19:09:20, Robert Hyatt wrote:

>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.

Maybe I missed something posted several days ago... I would like to ask exactly
what the point of trying to make a program with as stupid as possible components
(e.g. static eval) is?  What conclusions might be drawn from this that would
have real relevance to useful implementations?

Dave



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.