Author: Vincent Diepeveen
Date: 10:06:11 08/12/99
Go up one level in this thread
On August 12, 1999 at 09:44:32, Robert Hyatt wrote: [cut] >>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. We ARE changing W, as we have transpositions to positions. So in a position with say 30 possibilities, we strip on average a number of them, because they are getting a transposition next move. So we just waste 1 node on them (making the move getting transposition and back), instead of searching it full. >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 Transposition tables are not considered by Knuth. >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. i'm missing the transposition pruning. Effectively transposition prunes more when you search deeper. >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.