Author: Robert Hyatt
Date: 11:21:30 08/12/99
Go up one level in this thread
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. 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. > >>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. > >>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.