Author: Dieter Buerssner
Date: 12:16:11 06/18/03
Go up one level in this thread
On June 18, 2003 at 14:17:31, Dan Andersson wrote: > The gain is asymptotic to the minimal tree. So it won't be exponential. Simple >as that ;) I won't write the formula. You work it out for yourself. I am not so sure. First of all, already with random move ordering, one will get a much smaller tree than the minimax tree for all practical positions. There will be many positions, where any move is good enough for a beta cutoff. I remember a small test, where I got over 50% of beta cutoffs in the first move, in the cases where beta cutoff was possible (no HT was used) for random move ordering. I would expect (ignoring the odd/even problem) a constant branching factor for a search without extensions/pruning. So, perhaps with random move ordering one would get something like nodes ~ bfr^depth and with perfect move ordering nodes ~ bfp^depth bfp < bfr < N (number of moves/position). How would you call this speedup mathematically? Regards, Dieter
This page took 0.01 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.