The value of f can be found by collecting statistics of the playout. 1/f is the average ratio of the number of playout in the choosen thread to the total number of play out. Consider level one. Calculate the ratio of the bias of the move chosen to the total number of the playout. A ratio like this can be obtained for every level. Average them. It's 1/f. Suppose the threshold value is 20 and on average 100 moves are considered in each level. Then m=20*100=2000.
DL On Tue, Jun 15, 2010 at 3:31 PM, Álvaro Begué <[email protected]>wrote: > 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 >
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
