It seems that there are at least three cases: 1: Choosing a random move from a uniform distribution 2: Choosing a random move from a nonuniform distribution (patterns etc.) 3: Choosing a move taking into account what has been chosen before
The concensus seems to be that numbers 1 and 2 are MC and 3 is QMC. Mogo uses QMC within the tree in memory and MC for the leaves, so which should it be called? And about reducing variance: In games you only care about estimating the goodness of the best moves (in order to select the best one). You don't care how bad a move is, if you are fairly certain that it is not the best one. You should thus reduce the variance of the best moves, that is, study them more often. This is exactly what UCT is about, reducing the variance of variables of interest. 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. To summarise, I agree that there are links to other MC research, and they should be explored. -- Tapani Raiko, <[EMAIL PROTECTED]>, +358 50 5225750 http://www.cis.hut.fi/praiko/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
