Tapani Raiko wrote:
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?
Yes, programs will quickly diverge into many different "classifications"
so that is why in the end it probably doesn't mean much to distinguish
between just MC and QMC.
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 understand, but you must still correctly correlate good and bad moves
and doesn't this require a goodness factor? Running simulations is the
only way MC can begin to classify them and the only way for UCT to
decide to further study them. So better simulations will produce better
results. "One dimensional" simulations will probably not produce the
best results.
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.
To summarise, I agree that there are links to other MC research, and they
should be explored.
Yes, I agree.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
