Robert Waite skrev:
* > The MCTS technique appears to be extremely scalable. The theoretical
*> >* > papers about it claim that it scales up to perfect play in theory.
****
*>* > We agree here that this is not true of course.
*
No, I think we disagree this time my friend!
Monte Carlo of course by itself is not scalable. But when combined with
tree search such as UCT, it is equivalent to a mini-max search with a
high quality evaluation at leaf nodes. It's scalable because the
longer it searches, the more it acts like a proper mini-max search.
I am not really sure what you guys meant by the interchange above.. and I
will admit that I am not nearly as deep into the problem as probably anyone
on this list.. but it seems doubtful that they have proven some sort of
scalable algorithm that will continue to give moves closer and closer to
perfect play with higher and higher confidence. I could believe that they
have a proof that the algorithm is scalable in computing power... but not
necessarily that it is scalable against the problem of beating a human.
MC/UCT is provably scalable up to perfect play.
/Dan Andersson
Firstly.. I don't know if there is necessarily "perfect" play. If you mean
play good enough to beat all humans... I guess you could consider that
perfect in a sense.
It just seems that given the ridiculously large number of possible games...
and the relative weakness our our computation machines... we will be taking
an extremely small sample size with our current models of computing. There
may be some breakthrough... but it seems that as long as Moore's law
holds... we will continue to be taking a very small sample. There are some
heuristics being used to help whittle down the bad.. like checking the 8
spots around a stone... but is it really proven that this algorithm will
scale in a practical sense? As in... if we took Mogo in it's current form
and threw all the hardware that humanity can make in the next 20 years at
it... has that alone been shown to be enough to beat humans? Seems that we
don't understand all of the parameters of human play to answer a question
like that.
I am playing the Devil's advocate here.. because I do have a feeling that
the human computer with regards to go is not mystical and that we have a
weakness that can be exploited by computers. But I just feel that there is
no rigorous proof yet about the power of scalability of computation... vs.
the ability to beat a human in go.
On Sat, Aug 9, 2008 at 2:54 PM, Robert Waite <[EMAIL PROTECTED]> wrote:
I'm curious what you guys think about the scalability of monte carlo with
UCT. Let's say we took a cluster like that which was used for the Mogo vs.
Kim game. Then lets say we made 128 of these clusters and connected them
together efficiently. Putting aside implementation and latency issues...
what kind of stones-strength increase would you imagine?
Its a pretty arbitrary guess.. but do you think one stone improvement... or
that this would alone be enough to beat a pro even?
I am wondering because there could be a weakness or limit in MC w/ UCT. I
am only now learning about the UCT addition... but there are vast numbers of
possible games that are never visited during the monte carlo simulations.
The random stone simulations are pretty random aren't they? I am reading
some of the papers on the UCT addition... and that does seem to show certain
branches to be "better" and worth more time. Pro players may have a
counter-strategy that might come out as Mogo is tested at higher levels of
play. Perhaps there will be a need to combine MCwUCT with heuristics or more
knowledge based play. Going the route of heuristics seems unpleasant and the
promise of using a more computational method would be great. However... if
MC techniques alone have a diminishing return... the route of heuristics
might come back (or perhaps a whole new paradigm for game algorithms).
I am still secretly on the side of human go beating the machine.. but the
recent match really changed my view on topic and really showed the value of
statistical analysis. I am just wondering about what kind of roadblocks
might show up for the monte carlo techniques.
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
