Author: Dave Gomboc
Date: 10:47:53 06/19/00
Go up one level in this thread
On June 17, 2000 at 20:53:20, Robert Hyatt wrote: >On June 17, 2000 at 20:00:31, Ralf Elvsén wrote: > >>On June 17, 2000 at 19:08:35, Dave Gomboc wrote: >> >>>On June 17, 2000 at 04:09:59, Ralf Elvsén wrote: >>> >>>>On June 16, 2000 at 22:38:41, Robert Hyatt wrote: >>>> >>>>>On June 16, 2000 at 20:39:07, Ricardo Gibert wrote: >> >>>>>>Just out of curiousity, what would alpha/betas formula look like with random >>>>>>move ordering? >>>>> >>>>> >>>>>Difficult to say and it would have to have too many assumptions. IE do you >>>>>assume that for any fail-high node, there is only one move that will fail high? >>>>>Or could there be several different moves that would be good enough to cause >>>>>the fail-high? The formula is derivable, but probably isn't worth the effort. >>>> >>>>Dave Gomboc has given the formula W^(2D/3) (approximately) . >>>>I asked about the assumptions behind this but didn't get an answer. >>>>I once made an experiment and found it to be roughly in line with >>>>this formula. >>>> >>>>Ralf >>> >>>Hmm, maybe I missed your post, whenever that was. >> >>Some months ago, but that happens easily. >>> >>>I don't actually ever recall seeing a derivation of the result. This estimate >>>was discussed (in passing) in a Heuristic Search course that I took (professor: >>>Jonathan Schaeffer). >>> >>>Dave >> >>I have had a hard time getting anywhere. I figured a random number at the >>leafs, i.e. eval = Random(), distributed in some way, would be an >>assumption which would lead to a result, but the math became too ugly. >>The values of alpha and beta closer to the root >>becomes a probability distribution... >>Also I am not sure this is equivalent to the original problem. >> >>Another approach, which I think Bob was refering to, is to make assumptions >>about the number of fail-high moves at each node, but that seems to be >>such a crude model that I wouldn't feel very happy with a result (which >>I haven't got anyway). >> >>Maybe there is some subtle trick or it is just very hard. It's even harder >>when you don't know what to assume :) >> >>Ralf > > >Another approach, probably the one taken by Jonathan (I did something similar >for my PhD dissertation) would be to simply generate random numbers for the >eval, which has the same effect as random move ordering, and then try a suite >of test positions to that code. Do the same test with normal scoring. And >fit a curve of the form N=W^(f*D) to the observed random data. f might well >end up .66 as Jonathan mentioned. It might be bigger or smaller as well, >although it obviously has to be > .5, which is the alpha/beta F value with >optimal ordering. I went and asked Jonathan about where he got the estimate from. His reply was that Monty Newborn published the result a long time ago (most likely in the 1970s, and he is "pretty sure" it was co-authored). Also he mentioned that somebody told him later that there was a problem with the proof, but that he didn't know if the error substantially changed the result. I don't intend to bother him about it further, I'm sure he has more important things to do. Hopefully the Newborn tip helps Ralf out. 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.