Author: Vincent Diepeveen
Date: 12:16:54 08/12/99
Go up one level in this thread
On August 12, 1999 at 14:21:30, Robert Hyatt wrote: >On August 12, 1999 at 13:06:11, Vincent Diepeveen wrote: > >>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. >> > >Vincent, you are _wrong_ here. W is the number of moves at each level in >the tree. Hashing does _not_ affect that whatsoever. It affects D only, >because it prevents that particular branch from going deeper. D is not the >same thing as W. That's a way to see it of course, though there is something else to consider too. The deeper you search, the more positions you see with less pieces on it than in the root. So the deeper the search, the near to pawn ending, with a very small W. So the deeper a search from the middlegame (and that's the only interesting thing as we all already search deep enough in the endgame) gets into real small W's, therefore i think it's tough to use this definition. >W is a constant that depends on the position, not on anything else you can >do in the search (forward pruning or whatever). >>So we just waste 1 node on them (making the move getting transposition >>and back), instead of searching it full. >Still has _nothing_ to do with "W". >> >>>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. > > >It is impossible to consider them in a closed-form equation. Because the >formula would end up with some sort of probabilistic behavior since there >is no direct way to express hashing hits as a function. Well it makes no sense to use a formula that's dead wrong in advance! >> >>>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. > > > >I agree there. But that doesn't invalidate what Knuth/Moore did. We have >just moved beyond the specific alpha/beta implementation they studied, by >adding null moves, razoring, quiescence searching, transposition tables, >three-fold repetition, 50 move draws, tablebase hits, and the like. Knuth didn't have to deal with the same problems as we do, that's correct. Knuths model is not wrong for the implementation in which he studied it, but it's wrong to use that model and apply it to the modern programs! > > > >> >>>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.