Exactly! Well said.
Weston Markham wrote:
(I typed the following up earlier today, before other people cast some
doubts about what "infinite scalability" means. Perhaps it is
helpful.)
I think that Alain was specifically referring to a property of UCT,
whereby given that a winning line of play exists, the probability that
the algorithm has discovered one such line & settled upon it
approaches 1 as time approaches infinity. I believe that this has
been proven. And no, this theoretical result does not represent any
intrinsic advantage over a calculation of the minimax value. (Someone
should feel free to correct me if there is a stronger theoretical
result that I am not aware of, though.)
I think it is important to understand that unless you restrict UCT
from exploring some correct lines of play, this "infinite scalability"
will still be true. And, it is true regardless of what moves have
been preferred/pruned/whatever within the MC playouts. (Or whatever
one does at the leaf nodes; it need not be MC at all, as long as the
UCT tree eventually gets expanded as the node is revisited.)
This is not to say that this particular property of UCT is sufficient
in order for us to claim that UCT is scalable in practice. My point
is rather that noone is claiming "infinite scalability of MC", but
rather scalability of UCT. When you combine that with the fact that
UCT has been very successful at 9x9 go, (and scalable across a wide
range of time limits) it seems to be reasonable to expect more of the
same in 19x19. (Which is what concerned the original poster.) Also,
one should expect that the UCT portion of MC-UCT will tend to
eventually "fix up" any systematic errors that are made by the MC
playouts.
I have one other point I'd like to make, in regard to "light" versus
"heavy" playouts: Even "light" playouts do not actually use a uniform
distribution, due to the quasi-eye rule that is generally used. I
think that there is every reason to expect that other "nonuniform"
playout policies further outperform "light" playouts in every
practical way. Granted, it is possible to introduce "severe
misconceptions" when one incorporates knowledge into one's playouts.
But even in that case, one can still fall back on the fact that UCT is
cleaning up after one's mistakes: the eventual behavior, given enough
time, is still perfect play. (And of course it is not as if people
blindly adjust the monte carlo policies without checking the revised
versions for "severe misconceptions".)
Weston
On 1/22/08, ivan dubois <[EMAIL PROTECTED]> wrote:
I think there is some missconception about this "infinite scalability of MC"
stuff.
Theory is only usefull when the model it is based on shares important aspects
with reality.
In theory, 19*19 Go is a finite game, wich can be analysed in a finite amount
of time. So ANY algorithm that solves the game at some point is, in theory,
infinitely scalable. For example, the folowing algorithm is infinitely scalable
:
Analyse the complete mini-max tree of the game. If enough time to finish,
returns the correct move, if not, return a random move.
Now, is this algorithm really scalable, in practive ? Of course not.
I support the idea that MC is infinitely scalable (in the reality) ONLY if the
play-out part does not have severe misconceptions. So i think that currently,
only MC based on uniform playouts is infinitely scalable.
It is well know that even Mogo has troubles with big eyes (he thinks a big eye
gives life, wich is false). This problem can not be solved with more computing
power (excep absurdly big, of course you can always mini-max to the end).
----- Message d'origine ----
De : Alain Baeckeroot <[EMAIL PROTECTED]>
À : computer-go <computer-go@computer-go.org>
Envoyé le : Mardi, 22 Janvier 2008, 22h13mn 26s
Objet : Re: [computer-go] Is MC-UCT really scalable ... is a troll
Le mardi 22 janvier 2008, David Fotland a écrit :
The UCT-MC programs do particularly well against traditional programs
because they expose the brittleness inherent in the pattern databases they
use. Strong humans are not so easily beaten by playing unconventional and
somewhat inferior moves.
I think Remi posted a game of CrazyStone on 19x19 commented by one pro
who said "this move is 2 dan level".
So far no go program got such analyse, and the also the huge novelty
provided by MC/UCT programs is they have a _real_ strenght with their
own style, like humans:
play solid when winning, and play hamete (tricky moves) when losing.
On kgs MC programs played hundreds (if not thousands) games against humans,
and no doubt they fully merit their rank, and no doubt they are improving.
Infinite scalability is a theoricaly proved property, so please
don't feed the troll :-)
Alain
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_____________________________________________________________________________
Ne gardez plus qu'une seule adresse mail ! Copiez vos mails vers Yahoo! Mail
http://mail.yahoo.fr
_______________________________________________
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/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
