I don't have any quantitative data to show, but at some point I tried to see what dimwit would do if I let it think for an hour on an early-game 9x9 position. The result was that the search was ridiculously narrow, with exceedingly long lines whose moves weren't particularly good, and it would just never change its mind about what move to play, just keep digging deeper (to first order, of course). I played around with the exploration/exploitation balance, and I got to the conclusion that it was hard to get UCT to do a reasonable job at all timescales. This was probably a large obstacle for scalability.
I think when you have explored a node enough times, there is no point in considering the score of the node to be the average of all the tries, but it should really be just the score of the best child (i.e., the minimax rule). UCT does converge to that value, but it does so by reducing exploration of inferior moves, which results in the long-lines behavior I just described. Perhaps there is a role for alpha-beta near the root of the tree when we have enough CPU, and that might scale better. Anyway, I am with Don here. Perhaps the current crop of programs doesn't make good use of huge CPU resources for which they were not designed, but as those CPU resources become commonplace, we'll see programs taking advantage of them. I would be extremely surprised if we hit a wall before getting to world-champion level. It will probably be just a very very long hill. Álvaro. On Mon, Jun 20, 2011 at 1:35 PM, Don Dailey <[email protected]> wrote: > First of all, I never purchase papers of unknown quality. If I know a > paper is great or that it comes highly recommended by someone I trust I will > purchase it although the idea of purchasing papers in general is distasteful > to me. > The scalability issue as you summarize has to do with the number of cores - > I am not surprised that more cores bring less improvement and that is true > in ALL games. That's not the issue I am talking about here although it's > certain a legitimate practical issue. > To better understand the issue, forget about the specific machine it's on > and substitute the phrase "scale with time." > There is no scaling issue with reasonably written programs that can be > tested with current hardware. Showing that it's difficult to parallelize > an algorithm that is basically serial does not prove anything here. > I have explained why people believe MCTS may have limits and why they are > wrong. All such "evidence" that we have hit some wall is anecdotal. > Unless of course you know of someone who has run a few thousands games at 1 > day per move on a single core machine (or equivalent.) > Don > > > On Mon, Jun 20, 2011 at 1:12 PM, René van de Veerdonk > <[email protected]> wrote: >> >> On Mon, Jun 20, 2011 at 8:27 AM, Don Dailey <[email protected]> wrote: >>> >>> On Mon, Jun 20, 2011 at 10:09 AM, terry mcintyre >>> <[email protected]> wrote: >>>> >>>> Any particular instance of a program will probably fail to scale - >>>> especially against humans who share the lessons of experience. >>> >>> That is complete nonsense. How are you backing this up? What proof do >>> you have that computers don't play better on better hardware? Why are the >>> top programs being run on clusters and multi-core computers? Are the >>> authors just complete idiots? >>> Every bit of evidence we have says they are scaling very well against >>> humans. That has also been our experience in game after game, not just >>> in Go. >>> I apologize for being so harsh on this, but you are too smart to be >>> saying such dumb things. >> >> >> Please read (from Darren Cook): >>> >>> Richard Segal (who operates Blue Fuego) has a paper on the upper limit >>> for scaling: >>> http://www.springerlink.com/content/b8p81h40129116kl/ >>> (Sorry, I couldn't find an author's download link for the paper; Richard >>> is on the Fuego list but I'm not sure he is even a lurker here.) >> >> Another paper that mentions the topic (also Fuego specific) is here: >> http://webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf >> The short conclusion of these papers is that it was not worth it to scale >> Fuego to a IBM/BlueGene machine (original purpose of the work), as it didn't >> get any better anymore, i.e., performance didn't (appreciably) scale beyond >> 512 or so cores. Obviously, that's still a big improvement from a desktop >> pc, but far from the capacity of the supercomputer available. >> Zen also has a similar issue according to its co-author Kideko Kato. >> That's evidence enough for me to indicate that there indeed is an issue with >> the current breed of programs. >> It appears that current specific implementations have a scaling ceiling. I >> expect, as expressed by multiple people here, that once that ceiling gets >> close enough to become a limitation, people will change their algorithms >> accordingly and scaling will continue. But it will only happen once you can >> comfortably test the program in that resource regime. >> René >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > > > _______________________________________________ > Computer-go mailing list > [email protected] > http://dvandva.org/cgi-bin/mailman/listinfo/computer-go > _______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
