Author: Vincent Diepeveen
Date: 03:32:59 08/12/99
Go up one level in this thread
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). 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. Can you imagine? My god, those men are teaching thousands of students. 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. 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
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.