[Computer-go] evaluating number of wins versus looses

Jason House jason.james.house at gmail.com
Mon Mar 30 06:11:52 PDT 2015

The complex formula at the end is for a lower confidence bound of a
Bernoulli distribution with independent trials (AKA biased coin flip) and
no prior knowledge. At a leaf of your search tree, that is the most correct
distribution. Higher up in a search tree, I'm not so sure that's the
correct distribution. For a sufficiently high number of samples, most
averaging processes converge to a Normal distribution (due to central limit
theorem). For a Bernoulli distribution with a mean near 50% the required
number of samples is ridiculously low.

I believe a lower confidence bound is probably best for final move
selection, but UCT uses an upper confidence bound for tree exploration. I
recommend reading the paper, but it uses a gradually increasing confidence
interval which was shown to be an optimal solution for the muli-armed
bandit problem. I don't think that's the best model for computer go, but
the success of the method cannot be denied.

The strongest programs have good "prior knowledge" to initialize wins and
losses. My understanding is that they use average win rate directly
(incorrect solution #2) instead of any kind of confidence bound.

TL;DR: Use UCT until your program natures
On Mar 30, 2015 8:06 AM, "folkert" <folkert at vanheusden.com> wrote:

> Hi,
> When performing a montecarlo search, we end up with a number of wins
> and number of looses for a position on the board.
> What is now the proven methology for comparing these values?
> I tried the method described here:
>         http://www.evanmiller.org/how-not-to-sort-by-average-rating.html
> ...which not only looks at how much more wins than looses there were
> for a position but also the total number for that position. So that a
> difference x with 10 playouts may be evaluated lower than a difference
> y with 11 playouts, even if x > y.
> This does not seem to give good results altough other factors may be in
> play here (my program is in it's infant stage).
> Folkert van Heusden
> --
> Finally want to win in the MegaMillions lottery? www.smartwinning.info
> ----------------------------------------------------------------------
> Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com
> _______________________________________________
> Computer-go mailing list
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20150330/21171a85/attachment.html>

More information about the Computer-go mailing list