> > I could see a case where it is possible to reduce a variance of a single > > variable even in the 0-1 case. Let us say that black has about 5% chances of > > winning. If we could (exactly) double the chances of black winning by > > changing the nonuniform sampling somehow (say, enforce bad moves by white), > > we could sample from that and divide the estimated black's winning chance in > > the end by 2. This would of course be very difficult in practice. (A binary > > random variable gives more information when the chances are closer to > > 50-50.) This could be useful in practice in handicap games, by for instance > > enforcing a black pass with 1% chance every move. Sampling would be > > distorted towards white win, which is realistic since white is assumed to be > > a stronger player, anyway.
> I don't understand this line of reasoning. Let my try again using the handicap example. Let's say MC player is given a huge handicap. In the simulations, it is winning all of its games, so there is no information helping to select the next move. Using information theory, each play-out gives one bit of information if the chances are 50:50, but if the chances are unbalanced, the information content is lower. (see http://en.wikipedia.org/wiki/Binary_entropy_function ) In the extreme case, there is no information at all. Now, let us use distorted MC where we enforce black to pass with a few percent chance every move. White begins to win some of the simulations, so MC is useful again. How this is related to reducing the variance? Let us say that a black move leads to a white win with probability p very close to zero. Let us also assume that distorting the simulations doubles white's chances to 2p. Using normal MC, the variance of our estimate of p using N samples is p*(1-p)/N and using distroted MC, the variance of 2p is 2p*(1-2p)/N estimating p by using the estimate of 2p, the variance is divided by 4: p*(1-2p)/2N which is less than p*(1-p)/N. In practice, we cannot know that distorting would increase the chances exactly by doubling them, but if we use the same distortion to estimate all moves, we can still compare them. Tapani _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
