Author: Robert Hyatt
Date: 06:44:32 08/12/99
Go up one level in this thread
On August 12, 1999 at 06:32:59, Vincent Diepeveen wrote: >On August 11, 1999 at 20:46:32, Dave Gomboc wrote: > >>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? > >branching factor can be way smaller theoretical than most 'professors', >especially the ones that are outside computerchess, imagine, because of >posts and written down thoughts of the ones that see it wrong. > >Some years ago there was 'consensus' about: "it gotta be above the >square root of the number of possibilities, and the depth progs like >fritz3 got in those days were explained as: "they gotta use other forward >pruning than just nullmove". > >Now i argued against that, >but some years ago i was laughed for. > >Now all programs don't have a branching factor that's above the >square root of the number of possibilities (say 30 or so). Vincent, you are mixing apples and oranges in a terrible way. The 'branching factor' can _not_ get below roughly sqrt(w). The 'effective branching factor' can, because you aren't changing "w" in the equations given by Knuth/Moore: nodes = W ^ ceil(D / 2) + W ^ floor(D / 2) that is an immutable law of alpha/beta. In your case (and mine) we are not changing anything but D. When we say we are searching to D, we are really searching to D-n where n is the null-move- reduction. IE when you discuss this, please use rigorous mathematical definitions, not handwaving. No one would argue that if you go into the tree and reduce the depth by 3-4-5-6-... 20 plies, that the above formula still holds. It was written with the idea that _every_ path goes to depth D unless it is pruned away by alpha/beta. We aren't doing that. > >So then there is a big conference in Paderborn, and i see many >professors there and many scientists. I talked to several of >them (the japanese are nice people btw, but they gotta learn english >or german) about searching game trees. > >THEY STILL THINK IT'S THE SQUARE ROOT. because it _is_. > >Can you imagine? > >My god, those men are teaching thousands of students. thank goodness that they teach things that are theoretically sound, rather than semantically scrambled? > >So i post here an MSG with the most dumb program ever, and claiming >there is no model for the combination of > - PVS a-b search > - nullmove > - extensions > - hashtables > >In scientific areas the hashtable gets really underestimated in my >viewpoint. > >This formula of Blackman is already a lot better than knuths. >I still am missing however the influence of the hashtable. > the formula by Blackman is hopeless. Because you just left finite mathematics and dove into probability and statistics. It is possible to develop a mathematical model just as precise as Knuth/Moore, yet take the probability of an R-reduction in depth on some lines into consideration. Unfortunately the 'variance' would be so great as to render this worthless. >We can simply SEE the minimum model needed when returning always a zero. > >What Bob without knowing is trying to proof here is that no program >is near a good move ordering, and that extensions really limit big >a lot if we are having a very good move ordering. > >>Dave No... what Bob is trying to prove is that there is _no_ way to get anywhere near to perfect move ordering. Because if we could, we'd just use that at ply=1 and play perfect chess. Do you _really_ think there is a way to find the best move at a position without any search at all? I don't. the program with an eval of 0 is worthless. The one with an eval of only material score gives a probable best-case of what we can do in a real program. Because if we can't get captures ordered right, ordering the rest is hopeless.
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.