Author: Vincent Diepeveen
Date: 15:19:27 08/11/99
Go up one level in this thread
Another thing Bob,
Use a simple Swapoff evaluation like junior has,
that saves another few ply for the material searcher.
That's what we were talking about when i said 30 ply.
Then go replace lastply nullmove by last plies pruning:
if( eval >= beta
(depthleft <= 1
|| (depthleft <= 3 !morethan1attacktopieces)) <== so not pawns
return(eval);
That *really* speeds up for last 3 ply, instead of the weird
crafty-icc-blitz razoring.
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...
>
>
>
>>
>>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 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.