Author: martin fierz
Date: 00:46:04 03/30/04
Go up one level in this thread
On March 29, 2004 at 18:12:29, Dann Corbit wrote: >On March 29, 2004 at 18:06:22, martin fierz wrote: > >>On March 29, 2004 at 16:35:29, Dann Corbit wrote: >> >>>On March 29, 2004 at 16:22:21, martin fierz wrote: >>> >>>>On March 29, 2004 at 15:50:10, Dann Corbit wrote: >>>> >>>>>On March 29, 2004 at 10:17:18, martin fierz wrote: >>>>> >>>>>>aloha! >>>>>> >>>>>>i was discussing this somewhere in a thread, but thought i'd like to make this >>>>>>question more visible in the hope of getting a good answer: >>>>>> >>>>>>everybody knows that with plain alpha-beta, a fixed number of moves N per node, >>>>>>and perfect move ordering a search to depth D needs >>>>>> >>>>>>nodes(depth) = sqrt(N)^(D/2) nodes. >>>>>> >>>>>>with absolutely imperfect move ordering it needs >>>>>> >>>>>>nodes(depth) = N^(D) nodes. >>>>>> >>>>>>a typical chess program gets something like 90% move ordering in the sense that >>>>>>if a cutoff move exists, it will search it as first move in 90% of all cases. >>>>>>here's my question: >>>>>> >>>>>>can anybody give an estimate for nodes(depth) as function of this move ordering >>>>>>parameter? obviously, this would also depend on when you find the best move in >>>>>>those cases where you don't find it first. any kind of model is acceptable, e.g. >>>>>>you always find it on 2nd, always on sqrt(N)th, always last, at a random number, >>>>>>whatever. i'm just interested in the general behavior of nodes(depth) as a >>>>>>function of the cutoff-%age. >>>>>> >>>>>>i'd be extremely surprised if nobody ever estimated this, so: has any of you >>>>>>ever seen or calculated such numbers, and if yes, what do they look like? >>>>>> >>>>>>and is there any theory how this would apply to a modern chess program with >>>>>>nullmove and extensions instead of the plain A/B framework above? >>>>>> >>>>>>basically this question of course means: do you really gain anything tangible >>>>>>when improving your MO from say 90% to 92%? >>>>> >>>>>I have not done the math, but I am guessing no matter what king of move ordering >>>>>you have (purely randome or the pv move every time) you will get something like >>>>>this: >>>>> >>>>>nodes = some_constant * sqrt(mini_max_nodes) >>>>> >>>>>If you have random move ordering, then the constant will be very large. >>>>>If you have perfect move ordering, then the constant will be very small. >>>>> >>>>>You will never get worst case unless you try very hard to achieve it. >>>>>It might be possible to degenerate to mini-max (or very close to it) but you >>>>>will have to choose the worst possible move at every single turn except the >>>>>leaves. I doubt if anyone can do it. >>>>>;-) >>>> >>>>i disagree with your formula. it is definitely not some_constant. it is a >>>>constant between 1...sqrt(N) taken to the power of D/2. else there would be no >>>>point in improving move ordering, or at least, not as much as there is :-) >>> >>>What if the constant is one trillion? >> >>so it's one trillion, then what? >>let's try: >> >>i want to compute your nodes for A/B to depth 2. you say: >> >>>>>nodes = some_constant * sqrt(mini_max_nodes) >>and the constant is one trillion => >> >>nodes = 10^12*sqrt(35*35) >> minimax_nodes. >> >>do you see now why your formula is plain wrong? i mean, of course you can define >>your constant for every depth, but then it's not a constant :-) >> >>and the whole point is that this constant *does* scale with depth in a form in >>which you can give an analytic expression for it, so why not do so??? >> >>cheers >> martin >> >> >>>If you choose the node at random, you will still find the right one by random >>>chance on the first try 1/n times (where n is the number of moves) and on the >>>second try 1/(n-1) times, etc.. On average, we won't have to try more than half >>>of the nodes to find it (the best one). This will cause a huge reduction in >>>the number of nodes. >>> >>>As you can see, you would have to put forth a stupendous effort to cause minimax >>>behavior. > >It was a number from a hat. are your really not getting the point? you CANNOT produce a single constant that works for this equation, period. your constant depends on the depth you search. > >Look here: >http://www.brillianet.com/programming/artificial_intelligence/tutorials/tut1.pdf >at figures 3-6 > >You will see at a glance that every change from random node selection (Hash, >history, etc.) all resulted in linear speedups. > >So the study agrees with my wild guess. not at all. the speedup changes with depth.... meaning the "constant" changes with depth. oh well, i'm not going to pursue this further... cheers martin
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.