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. DL
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
