Author: Dan Andersson
Date: 16:09:32 06/19/03
Go up one level in this thread
I think the difference is the outlook. I posit a fixed time limit or maximum search depth. However large. Let's look how that plays out. First with fixed time, then with depth as the variable: Any improvement in branching factor would have an exponential effect. But there is a limit to how small the branching factor can be and still have an exhaustive search. Thus d is a constant. And we derivate on P If we look at the quotient of terminal nodes in an optimal tree and one with less than perfect move ordering. We get EbF=(P+(1-P)momentOfMoves)^d and the derivative of this is EbF'=(1- MomentOfMoves)*d*(MomentOfMoves*(1 - x) + x)^(d-1) And that is hardly an exponential function. But we have to adress the case that the optimum tree searcher will get deeper. b^r=(P+(1-P)momentOfMoves)^d r=d*log(P+(1-P)momentOfMoves)/log(b) where the maximum will be r=d equaling a minimax search, and the minimum r=0. And in a highly ordered tree r will close in on zero. We can also look at it from the perspective of search depth. EbF' = (momentOfMoves(1-P)+P)^d log(momentOfMoves (1-P)+P) This is exponential for sure. But the variable d is on an exponential scale. For every increase in d is accompanied by an exponential increase in time. And normalized on a linear timescale the gain will have a logarimic relationship to time. Feel free to correct my reaoning, since I feel a bit rusty in my math and algorithmic complexity analysis. And may have made some mistake. MvH Dan Andersson
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.