On Tue, Jun 15, 2010 at 4:02 PM, Petr Baudis <[email protected]> wrote: > On Sun, Jun 13, 2010 at 08:55:16PM -0500, Daniel Liu wrote: >> This post is to propose a metric that measures the effectiveness of a >> playout policy >> in a MC tree search. It could give some idea as how the playing strength >> varies with >> the total playout number. >> >> Let N be the total playout number. The effectve search depth is defined as >> >> Depth = (log with base f) (N/m), >> where m is related to factors such as the threshold value used, etc. f is >> the more >> interestng number characterizing a playout policy. A playout that selects >> moves >> randomly gives the largest value of f. I thnk it could be 2 or bigger. For >> the most >> effective search policy available today, such as those used by the most >> strong Go programs >> at present is about 1.5. >> >> So what can above calculation tell us? According to above calculation it >> could estimate >> that the effective search depth of the today's strong Go programs are about >> 11, if the playout >> number is one million and assume m=600, f=1.5. If an effective search depth >> of 50 >> is requied to reach high dan level. Then the playout number needs to >> increase by a >> factor of 1.5^39, about 7.4 milliom times. That is 7.4 trillion playouts s >> neeeded. > > Hi! > > Frankly, I'm a bit puzzled here. You present a completely > arbitrary-looking formula and completely arbitrary-looking values of > some mysterious constants and then try to conjecture something from > that. > > What does the logarithm express? Exactly how is m constructed and what > is its meaning? How to determine f, why would it be the values you say > it is? Does node selection policy (e.g. RAVE) matter to your formula?
In a traditional alpha-beta search, it is the case that nodes_searched = some_constant * pow(effective_branching_factor, depth) Since the only thing we know is the nodes_searched, you can derive the depth using a logarithm. So my guess is that he is trying to recover some notion of depth by assigning an arbitrary value to effective_branching_factor. The `m' in his formula is the same as the `some_constant' in mine. I fail to see what the point of this whole exercise is. Álvaro. _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
