Author: Ralf Elvsén
Date: 17:00:31 06/17/00
Go up one level in this thread
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
This page took 0.02 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.