Hi all, Just to introduce myself, I am a 5 dan amateur Go player from Singapore who has recently taken an interest in computer Go, programming and AI and a newbie to these forums. Been playing Go for many years (perhaps 20 years or so and represented Singapore in the past, winning 3rd place at the World Youth Amateur Go Tournament in Hawaii and 12th place at the World Amateur Go Tournament in Japan) though I have not competed for many years. The recent improvement in Go AI has rekindled my interest in this ancient game and also artificial intelligence. I am genuinely fascinated that Go AI has advanced so far --- when I first started out, the best Go AI was 30 kyu or so and nobody believed that they could even defeat a strong amateur Go player. Then came programs like ZenBS and CrazyStone , which surprised me because I could only win perhaps 50% of the time against these programs. The result of AlphaGo has shocked me to the core --- I don't know whether to feel happy or sad. A sudden impending sense of doom --- that mankind has been eclipsed. Just a few points I thought to raise here ...
Regarding the number of legal Go positions for a 19x19 board , it is ~2.082 x 10^170 (from the Sensei's website) Number of legal positions One number of interest for use in calculations of the number of possible games is the number of legal position <http://senseis.xmp.net/?Position>s. An upper bound of the number of positions on a 19x19 go board is not hard to calculate. Every intersection can be either black, white, or empty, so the number of possible positions is exactly 3^361, which is ~1.741 × 10^172. For this bound, symmetry is not accounted. However, many of these positions contain strings of stones without liberties and therefore are not legal. The exact number of legal positions has been calculated for square boards up to size 19×19 by Tromp <http://senseis.xmp.net/?JohnTromp> and others[1 <http://senseis.xmp.net/?NumberOfPossibleGoGames#1>][2 <http://senseis.xmp.net/?NumberOfPossibleGoGames#2>]. Some numbers: - 9×9 board: ~1.039 × 10^38 - 13×13 board: ~3.724 × 10^79 - 17×17 board: ~1.908 × 10^137 - 19×19 board: ~2.082 × 10^170 (i.e., a 2 followed by 170 zeroes) For the 19×19 board, the number of legal positions is about 1.196% of the possible positions[3 <http://senseis.xmp.net/?NumberOfPossibleGoGames#3>]. Regarding how significant the victory is , it is important to note that (no disrespect intended) : 1) Fan Hui is no longer in his prime competitive Go playing games 2) Fan Hui is not a top tier professional Go player ( far from it ) 3) There was no significant monetary incentive at stake It will be interesting to see how the program fares against Lee Sedol ... but then again Lee Sedol is no longer in his prime playing days , though there is a million dollar prize incentive. I think what they should do is pit the program against the reigning world Go champion when he or she is in the prime Go playing days (late teens to mid 20's) Regards, Cai Gengyang On Mon, Feb 1, 2016 at 3:28 AM, <computer-go-requ...@computer-go.org> wrote: > Send Computer-go mailing list submissions to > computer-go@computer-go.org > > To subscribe or unsubscribe via the World Wide Web, visit > http://computer-go.org/mailman/listinfo/computer-go > or, via email, send a message with subject or body 'help' to > computer-go-requ...@computer-go.org > > You can reach the person managing the list at > computer-go-ow...@computer-go.org > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Computer-go digest..." > > > Today's Topics: > > 1. AlphaGo MCTS & Reinforcement Learning? (Greg Schmidt) > 2. Re: AlphaGo MCTS & Reinforcement Learning? (Álvaro Begué) > 3. Re: AlphaGo and the Standard Mistake in Research and > Journalism (John Tromp) > 4. Re: AlphaGo MCTS & Reinforcement Learning? (Petr Baudis) > 5. Re: AlphaGo and the Standard Mistake in Research and > Journalism (Robert Jasiek) > 6. Re: AlphaGo and the Standard Mistake in Research and > Journalism (John Tromp) > 7. Re: Mastering the Game of Go with Deep Neural Networks and > Tree Search (Peter Drake) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Sun, 31 Jan 2016 15:20:16 +0000 (UTC) > From: Greg Schmidt <gschmidt...@yahoo.com> > To: <computer-go@computer-go.org> > Subject: [Computer-go] AlphaGo MCTS & Reinforcement Learning? > Message-ID: > <1189786442.2338592.1454253616372.javamail.ya...@mail.yahoo.com> > Content-Type: text/plain; charset=UTF-8 > > The articles I've read so far about AlphaGo mention both MCTS and > RL/Q-Learning. Since MCTS (and certainly UCT) keeps statistics on wins and > propagates that information up the tree, that in and of itself would seem > to constitute RL, so how does it make sense to have both? It seems > redundant to me. Any thoughts on that? > > > ------------------------------ > > Message: 2 > Date: Sun, 31 Jan 2016 11:13:45 -0500 > From: Álvaro Begué <alvaro.be...@gmail.com> > To: Greg Schmidt <gschmidt...@yahoo.com>, computer-go > <computer-go@computer-go.org> > Subject: Re: [Computer-go] AlphaGo MCTS & Reinforcement Learning? > Message-ID: > <CAF8dVMV+6waCSpgNvHuVChYR9TYFRWLih2c_k= > zpko9w6kx...@mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > How about you read the paper first? The conversation would make much more > sense if you actually spent some time trying to understand the details of > what they did. :) <-- (mandatory smiley to indicate I am not upset or > anything) > > > > On Sun, Jan 31, 2016 at 10:20 AM, Greg Schmidt <gschmidt...@yahoo.com> > wrote: > > > The articles I've read so far about AlphaGo mention both MCTS and > > RL/Q-Learning. Since MCTS (and certainly UCT) keeps statistics on wins > and > > propagates that information up the tree, that in and of itself would seem > > to constitute RL, so how does it make sense to have both? It seems > > redundant to me. Any thoughts on that? > > _______________________________________________ > > Computer-go mailing list > > Computer-go@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/20160131/a8dff920/attachment-0001.html > > > > ------------------------------ > > Message: 3 > Date: Sun, 31 Jan 2016 11:19:12 -0500 > From: John Tromp <john.tr...@gmail.com> > To: computer-go <computer-go@computer-go.org> > Subject: Re: [Computer-go] AlphaGo and the Standard Mistake in > Research and Journalism > Message-ID: > < > caou__fyxe3nxdihql6a-dbhadpu3qlsfrv5q6fgzi8i8hqa...@mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > dear Robert, > > > The number G19 of legal games under a given go ruleset is unknown. > > It will never be known since there's not enough space in the known > universe to write it down. We're talking about a number with over > 10^100 digits. > > > For positional > > superko (prohibition of recreation of the same position after > > completion of a move on the board), no passes, and no resignation, the > > number of possible games is smaller than N^P19 > > The no-pass restriction makes this rather uninteresting. > But actually, the same bound applies to games with passes, > stated as Theorem 7 in our paper. > > Besides this upper bound, I can think of only two other numbers > that are well defined and interesting, namely > > 1) the size of the smallest search tree that proves the perfect komi. > and > 2) same but for a full-width tree > > These are called the decision complexity and game tree complexity on > https://en.wikipedia.org/wiki/Game_complexity#Decision_complexity > > It is reasonable to expect the perfect komi does not depend on games > of more than 361 moves. Even with some ko fights, the ko recaptures > are likely bounded by the number of unplayed points. > The branching factor will be high though; let's put it at at most 200 > on (geometric) average. > > Then we estimate the decision complexity to be upper bounded by > 200^181 and the game tree complexity by 200^361. > > regards, > -John > > > ------------------------------ > > Message: 4 > Date: Sun, 31 Jan 2016 17:42:40 +0100 > From: Petr Baudis <pa...@ucw.cz> > To: Greg Schmidt <gschmidt...@yahoo.com>, computer-go@computer-go.org > Subject: Re: [Computer-go] AlphaGo MCTS & Reinforcement Learning? > Message-ID: <20160131164240.gg12...@machine.or.cz> > Content-Type: text/plain; charset=us-ascii > > On Sun, Jan 31, 2016 at 03:20:16PM +0000, Greg Schmidt wrote: > > The articles I've read so far about AlphaGo mention both MCTS and > RL/Q-Learning. Since MCTS (and certainly UCT) keeps statistics on wins and > propagates that information up the tree, that in and of itself would seem > to constitute RL, so how does it make sense to have both? It seems > redundant to me. Any thoughts on that? > > I agree with Alvaro's suggestion. :-) But since the general notion is > interesting and maybe worth re-iterating [1]: > > * MCTS can be concaptualized as *on-the fly machine learning* that > uses RL to learn which actions are how good in the current context > (or a wider class of contexts in case of AMAF). > > * AlphaGo uses machine learning also in a preparation stage where > reinforcement learning is used to find values of actions in fuzzy > defined contexts. This is then used as a prior for initializing the > action values as they are "tuned on-the-fly" during actual MCTS game > search. > > On context: in classic MCTS, the context is "this precise board > position", we are trying to figure out the action (move) value for > each context separately and independently. [2] However, this is pretty > wasteful, so we also use localized contexts (based on B-T patterns for > example, or trivial tactics like atari) in real engines as priors for > these action values. > > The value network provides another way to map context to action move > values, and can be thought of imho pretty accurately as a "smart cache" > for the playout-computed action values. It's "smart" because ANNs are > fuzzy computational engines that do not require a precisely matched > board position but will learn things like "in contexts with this corner > shape, this vital point move will have high action value". > > > [1] BTW, there has been a good influx of new mailing list > subscriptions in the last few days! > > [2] AMAF is then a common prefix context, but let's ignore it as > AlphaGo doesn't use it. > > -- > Petr Baudis > If you have good ideas, good data and fast computers, > you can do almost anything. -- Geoffrey Hinton > > > ------------------------------ > > Message: 5 > Date: Sun, 31 Jan 2016 19:41:15 +0100 > From: Robert Jasiek <jas...@snafu.de> > To: computer-go@computer-go.org > Subject: Re: [Computer-go] AlphaGo and the Standard Mistake in > Research and Journalism > Message-ID: <56ae554b.8080...@snafu.de> > Content-Type: text/plain; charset=UTF-8; format=flowed > > On 31.01.2016 17:19, John Tromp wrote: > > It will never be known since there's not enough space in the known > > universe to write it down. We're talking about a number with over > > 10^100 digits. > > How do you know that an implicit expression (of length smaller than > 10^80) of the number does not exist? :) > > > [interesting stuff deleted] > > It is reasonable to expect the perfect komi does not depend on games > > of more than 361 moves. > > I do not think we may make such a premature claim. > > > Even with some ko fights, the ko recaptures > > are likely bounded by the number of unplayed points. > > From experience as go players, yes. But... I have seen too many > surprising sequences and sacrifices to be sure. > > > Then we estimate the decision complexity to be upper bounded by > > 200^181 and the game tree complexity by 200^361. > > I won't believe such until proven:) > > -- > robert jasiek > > > ------------------------------ > > Message: 6 > Date: Sun, 31 Jan 2016 13:57:22 -0500 > From: John Tromp <john.tr...@gmail.com> > To: computer-go <computer-go@computer-go.org> > Subject: Re: [Computer-go] AlphaGo and the Standard Mistake in > Research and Journalism > Message-ID: > < > caou__fxh1kosbxpytgzuzbsy_2m+zlnhnip7zzzrom-eysd...@mail.gmail.com> > Content-Type: text/plain; charset=UTF-8 > > dear Robert, > > >> It will never be known since there's not enough space in the known > >> universe to write it down. We're talking about a number with over > >> 10^100 digits. > > > > How do you know that an implicit expression (of length smaller than > 10^80) > > of the number does not exist? :) > > Of course an implicit one exists. One can write a program to compute it, > and declare that's the number, in a highly compressed form:-) > > >> It is reasonable to expect the perfect komi does not depend on games > >> of more than 361 moves. > > > > I do not think we may make such a premature claim. > > I didn't say I'm sure; I only said it's reasonable, as in I would bet > evenly on it. > > Presumably ou think chances are better than even that it doesn't > depend on games of more than 450 moves, and worse than even that it > only depends on games of at most 300 moves. What is your best estimate > of > point where where chances are even? > > >> Even with some ko fights, the ko recaptures > >> are likely bounded by the number of unplayed points. > > > > From experience as go players, yes. But... I have seen too many > surprising > > sequences and sacrifices to be sure. > > > >> Then we estimate the decision complexity to be upper bounded by > >> 200^181 and the game tree complexity by 200^361. > > > > I won't believe such until proven:) > > This is not about proving. This is about what numbers the press could use > that are not too arbitrary. > > regards, > -John > > > ------------------------------ > > Message: 7 > Date: Sun, 31 Jan 2016 11:28:52 -0800 > From: Peter Drake <dr...@lclark.edu> > To: computer-go@computer-go.org > Subject: Re: [Computer-go] Mastering the Game of Go with Deep Neural > Networks and Tree Search > Message-ID: > <CALYOV=wxpPSR8-5d6OOgHuA0XSXqFGSgbd+VobBaFf_Xo+4B= > w...@mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > Let me add my congratulations to the chorus. Well done! > > I'm due for a sabbatical next year. I had been joking, "It sure would be > good timing if someone cracked Go right before that started. Then I'd have > plenty of time to pick a new research topic." It looks like AlphaGo has > provided. > > On Wed, Jan 27, 2016 at 10:46 AM, Aja Huang <ajahu...@google.com> wrote: > > > Hi all, > > > > We are very excited to announce that our Go program, AlphaGo, has beaten > a > > professional player for the first time. AlphaGo beat the European > champion > > Fan Hui by 5 games to 0. We hope you enjoy our paper, published in Nature > > today. The paper and all the games can be found here: > > > > http://www.deepmind.com/alpha-go.html > > > > AlphaGo will be competing in a match against Lee Sedol in Seoul, this > > March, to see whether we finally have a Go program that is stronger than > > any human! > > > > Aja > > > > PS I am very busy preparing AlphaGo for the match, so apologies in > advance > > if I cannot respond to all questions about AlphaGo. > > > > _______________________________________________ > > Computer-go mailing list > > Computer-go@computer-go.org > > http://computer-go.org/mailman/listinfo/computer-go > > > > > > -- > Peter Drake > https://sites.google.com/a/lclark.edu/drake/ > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: < > http://computer-go.org/pipermail/computer-go/attachments/20160131/b150bb67/attachment.html > > > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > > ------------------------------ > > End of Computer-go Digest, Vol 72, Issue 41 > ******************************************* >
_______________________________________________ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
