Computer Chess Club Archives

Messages

Subject: Re: PVS and MTD(f) branching factor

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.