[Computer-go] Q about CG2006 MCTS paper

[Fuming Wang]

Hi Remi,

Thanks for the reply. If I understand correctly, for outcomes of 0 or 1, the
formula would become something like the following, right?

variance = u - u^2 + 1/S

Best regards,
Fuming


On Sat, Jan 1, 2011 at 2:30 AM, Rémi Coulom <Remi.Coulom at free.fr> wrote:

> Hi Fuming,
>
> Sigma is the sum of playout values. If you score 1 for a win, and 0 for a
> loss, then, yes, it is the number of wins. At the time of the paper, I was
> using territory, so it was not the number of wins. Sigma_2 is the sum of
> squares. If outcomes are either 0 or 1, then Sigma and Sigma_2 are equal.
>
> Rémi
>
> On 31 déc. 2010, at 18:15, Fuming Wang wrote:
>
> > Hi Remi,
> >
> > Thanks for the suggestions. Sorry for inaccuracies in my previous
> statements. Now I have read your paper more carefully, I find in the
> appendex many discussions related to improvements on playout move
> selections. On another note, I find that formula you gave on variance
> calculation very interesting. I am a little confused on the meaning of
> symble sigma in the formula, is it the number of wins of S trials? If that's
> the case, then the meaning of sigma_sup(2) can not be easily understood.
> >
> > Best regards,
> >
> > Fuming
> >
> > On Fri, Dec 31, 2010 at 8:31 PM, Rémi Coulom <Remi.Coulom at free.fr>
> wrote:
> > Hi,
> >
> > I'd like to advise against using the exact algorithm I described in my
> 2006 paper. I compared it to UCT at that time, and UCT performed better. I
> am sorry I don't have a reference to my data any more. I posted the results
> to the mailing list. It used to be archived at that link:
> > http://computer-go.org/pipermail/computer-go/2006-July/005737.html
> > I hope somebody kept an archive an can forward it to the list. The title
> of that message was "Experiments with UCT". It is too bad that the archive
> of that time is gone. Is it available anywhere? The google archive starts
> later.
> >
> > The biggest difference between the general MCTS idea I proposed and the
> UCT-like algorithms everybody is using today is that the backup operator was
> not the mean of playouts. I tried to consider selectivity and backup
> independently. I still believe it is a powerful idea. My feeling is that a
> good backup operator should be able to make a good decision independently of
> selectivity. That is to say, even if all the moves are explored uniformly,
> the backup operator should converge to min/max. Backing up the mean forces
> current programs to be extremely selective so that they rapidly converges to
> min/max.
> >
> > The only part of the tree where it is not important to converge rapidly
> to min/max is the root. I am aware of some experiments that indicate that
> being less selective at the root may improve strength. The efficiency of
> root parallelization may also be an indication that current algorithms are
> too selective at the root. So my vague intuition is that it may be worth
> trying to find a good backup operator that works with less selective search.
> >
> > Anyway, tweaking the MCTS formula you are using will never make your
> program very strong. Clever playouts are immensely more important,
> especially for 19x19.
> >
> > Rémi
> >
> > On 31 déc. 2010, at 07:02, Fuming Wang wrote:
> >
> > >
> > >
> > > ---------- Forwarded message ----------
> > > From: Fuming Wang <fumingw85 at gmail.com>
> > > Date: Fri, Dec 31, 2010 at 1:50 PM
> > > Subject: Re: [Computer-go] News on Tromp-Cook ?
> > > To: Aja <ajahuang at gmail.com>
> > >
> > >
> > > Hi Aja,
> > >
> > > Remi and S. Gelly's paper both come out in 2006,and I just checked that
> they did not reference each other. I just read Remi's paper again, and
> realized that CrazyStone's tree search approach is actually different from
> the popular UCT method. Similar to you, I haven't been able to get good
> results from the popular UCT method, so I might try CrazyStone's method for
> a change. In Remi's paper, CrazyStone is only having around 30% winning rate
> against Gnu Go 3.6, and now Erica is winning world competitions,this
> actually proves that high quality MC simulation (realized for the first time
> in MoGo) is more important than tree search algorithms.
> > >
> > > Best regards,
> > > Fuming
> > _______________________________________________
> > Computer-go mailing list
> > Computer-go at dvandva.org
> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
> >
> > _______________________________________________
> > Computer-go mailing list
> > Computer-go at dvandva.org
> > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20110101/534dc0b6/attachment.html>