Re: [Computer-go] Congratulations to AlphaGo (Statistical significance of results)
don't use asymptotic normality with a sample size 5, use Fisher's exact test the p-value for the rejection of "P(alpha-Go wins a given game against Lee Sedol)<.5" might be something like 3/16 (under the "independent coin" assumption!) this is not 0.05, but still quite an impressive result :-) with 5-0 it would have been <0.05. On Wed, Mar 30, 2016 at 6:59 PM, Ryan Hayward <hayw...@ualberta.ca> wrote: > Hey Simon, > > I only now remembered: > > we actually experimented on the effect > of making 1 blunder (random move instead of learned/searched move) > in Go and Hex > > "Blunder Cost in Go and Hex" > > so this might be a starting point for your question > of measuring player strength by measuring > all move strengths... > > https://webdocs.cs.ualberta.ca/~hayward/papers/blunder.pdf > > On Wed, Mar 30, 2016 at 5:29 AM, Lucas, Simon M <s...@essex.ac.uk> wrote: > >> In my original post I put a link to >> the relevant section of the MacKay >> book that shows exactly how to calculate >> the probability of superiority >> assuming the game outcome is modelled as >> a biased coin toss: >> >> http://www.inference.phy.cam.ac.uk/itila/ >> >> >> I was making the point that for this >> >> and for other outcomes of skill-based games >> we can do so much more (and as humans we intuitively >> DO do so much more) than just look at the event >> outcome - and maybe as a community we should do that more >> routinely and more quantitatively (e.g. >> by analysing the quality of each move / action) >> >> Best wishes, >> >> Simon >> >> >> >> On 30/03/2016, 11:57, "Computer-go on behalf of djhbrown ." < >> computer-go-boun...@computer-go.org on behalf of djhbr...@gmail.com> >> wrote: >> >> >Simon wrote: "I was discussing the results with a colleague outside >> >of the Game AI area the other day when he raised >> >the question (which applies to nearly all sporting events, >> >given the small sample size involved) >> >of statistical significance - suggesting that on another week >> >the result might have been 4-1 to Lee Sedol." >> > >> >call me naive, but perhaps you could ask your colleague to calculate >> >the probability one of side winning 4 games out of 5, and then say >> >whether that is within 2 standard deviations of the norm. >> > >> >his suggestion is complete nonsense, regardless of the small sample >> >size. perhaps you could ask a statistician next time. >> > >> >-- >> >patient: "whenever i open my mouth, i get a shooting pain in my foot" >> >doctor: "fire!" >> >http://sites.google.com/site/djhbrown2/home >> >https://www.youtube.com/user/djhbrown >> >___ >> >Computer-go mailing list >> >Computer-go@computer-go.org >> >http://computer-go.org/mailman/listinfo/computer-go >> ___ >> Computer-go mailing list >> Computer-go@computer-go.org >> http://computer-go.org/mailman/listinfo/computer-go >> > > > > -- > Ryan B Hayward > Professor and Director (Outreach+Diversity) > Computing Science, UAlberta > > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > -- = Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ. Paris-Sud), bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Game 4: a rare insight
Should we understand that AlphaGo had not understood that O10 was dead ? (sorry for Go beginner question :-) ) On Sun, Mar 13, 2016 at 1:42 PM, Detlef Schmicker <d...@physik.de> wrote: > -BEGIN PGP SIGNED MESSAGE- > Hash: SHA1 > > You are right, but from fig 2 of the paper can see, that mc and value > network should give similar results: > > 70% value network should be comparable to 60-65% MC winrate from this > paper, usually expected around move 140 in a "human expert game" (what > ever this means in this figure :) > > Am 13.03.2016 um 12:48 schrieb Seo Sanghyeon: > > 2016-03-13 17:54 GMT+09:00 Darren Cook <dar...@dcook.org>: > >> From Demis Hassabis: When I say 'thought' and 'realisation' I > >> just mean the output of #AlphaGo value net. It was around 70% at > >> move 79 and then dived on move 87 > >> > >> https://twitter.com/demishassabis/status/708934687926804482 > >> > >> Assuming that is an MCTS estimate of winning probability, that > >> 70% sounds high (i.e. very confident); > > > > That tweet says 70% is from value net, not from MCTS estimate. > > > -BEGIN PGP SIGNATURE- > Version: GnuPG v2.0.22 (GNU/Linux) > > iQIcBAEBAgAGBQJW5WAmAAoJEInWdHg+Znf4HSAQAI1e9iyGlSrJ0QdsmheuGDiz > 09vK+mWGHZ+QAcIEkJEQ7wciKYc2IuRejAZrF6lQTQcV9GsAcVKVoqTmuJ7BnFTI > ZEZzN8nk1DKilTGs6P9BALwk0V3zvCI0Mo9AdMpequ6LV+D7vbY9gjkJgKU6O9td > zXrQhP9tdK8M/BEy5caz6uzsbP+5ESorK4X9Xt84bgv3p7aSIaCwVrkTjOPSQAZw > smErgmxAkOIvGABtexkcfgxyYXtYSfHoMsM80d9APoK9fY32TkGYSHvSvHCZks6x > LUcVnEBu7WHHekV6genv6GS2cbM+La8ghIRQrJwuN2lS+q1YEYy8lHbNmEEY0A2s > FeYIIVA9i8HmMJmw6g0XYVt1ODsOl8sJfMzxUxcG9qgppica/Xbkrq/yFe7ktm2l > lD2WxbRlny9s/ZJSUtoM12OvYmXRmvoFRMRooJ1eydI25Weld2dpHNvT6L3BMLlt > E5HyE46QU+lzFLCrpOQTHGRoWyx1ShmfNuBat3XWm0nHMg+SARJ95795agSjGbNt > tO0kaXqK5GkY2HtOSZcMistLIqiOBde8iDNXWJqQ5kKndguBQ7mXArEG0t10AT6g > yQQ6/6ffi5WM92HEUy5R/wPzNaLUCsAzzSu7hrRxlg//vj7oKf93DlhTnHaigdFj > /u+/r+j6IuJboAQtAYcf > =ZdLw > -END PGP SIGNATURE- > ___________ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > -- = Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ. Paris-Sud), bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Congratulations to AlphaGo
And please tell us how many stones AlphaGo can give to Aja or to other strong players :-) (well, I understand you have the two last games to take care of :-) ) On Sat, Mar 12, 2016 at 12:07 PM, Erik van der Werf < erikvanderw...@gmail.com> wrote: > Congratulations Aja & Deepmind team! > > Now that the victory is clear, perhaps you can say a bit more on the > latest developments? Any major scientific breakthroughs beyond what we > already know from the Nature paper? > > Enjoy the moments! > > Erik > > > On Sat, Mar 12, 2016 at 9:53 AM, Aja Huang <ajahu...@google.com> wrote: > >> Thanks all. AlphaGo has won the match against Lee Sedol. But there are >> still 2 games to play. >> >> Aja >> >> On Sat, Mar 12, 2016 at 5:49 PM, Jim O'Flaherty < >> jim.oflaherty...@gmail.com> wrote: >> >>> It was exhilerating to witness history being made! Awesome! >>> >>> On Sat, Mar 12, 2016 at 2:17 AM, David Fotland <fotl...@smart-games.com> >>> wrote: >>> >>>> Tremendous games by AlphaGo. Congratulations! >>>> >>>> >>>> >>>> *From:* Computer-go [mailto:computer-go-boun...@computer-go.org] *On >>>> Behalf Of *Lukas van de Wiel >>>> *Sent:* Saturday, March 12, 2016 12:14 AM >>>> *To:* computer-go@computer-go.org >>>> *Subject:* [Computer-go] Congratulations to AlphaGo >>>> >>>> >>>> >>>> Whoa, what a fight! Well fought, and well won! >>>> >>>> Lukas >>>> >>>> ___ >>>> Computer-go mailing list >>>> Computer-go@computer-go.org >>>> http://computer-go.org/mailman/listinfo/computer-go >>>> >>> >>> >>> ___ >>> Computer-go mailing list >>> Computer-go@computer-go.org >>> http://computer-go.org/mailman/listinfo/computer-go >>> >> >> >> ___ >> Computer-go mailing list >> Computer-go@computer-go.org >> http://computer-go.org/mailman/listinfo/computer-go >> > > > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > -- = Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ. Paris-Sud), bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo won the second game!
The most surprising fact, to me, is that it's possible to apply "reinforce" on such a large scale. Reinforce is not new, but even with millions of cores I did not expect this to be possible. I would have assumed that reinforce would just produce random noise when applied at such a scale :-) On Thu, Mar 10, 2016 at 9:29 PM, Petr Baudis <pa...@ucw.cz> wrote: > On Thu, Mar 10, 2016 at 07:20:11PM +, Josef Moudrik wrote: > > Yes, but they are not some random cherry picking third party; have a look > > on the top authors of the paper - David Silver, Aja Huang, Chris > Maddison.. > > Also, they aren't merely wrapping engineering around existing science > and putting existing things together, but invented several new methods > too. So, of course they are standing on the shoulders of giants, and > the massive computational resources of Google had been a lot of help, > but I'd say there is a fair amount of originality in the AlphaGo > research, scientifically. > > Petr Baudis > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > -- = Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ. Paris-Sud), bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo won first game!
Congratulations to AlphaGo people! Are there strong humans who have an opinion, on whether this advantage at move 26 is real ? In pro games, does it happen often that there is a clear advantage at move 26 ? -- = "I will never sign a document with logos in black & white." A. Einstein Olivier Teytaud, olivier.teyt...@inria.fr, http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Mastering the Game of Go with Deep Neural Networks and Tree Search
> > If AlphaGo had lost at least one game, I'd understand how people can have >> an upper bound on its level, but with 5-0 (except for Blitz) it's hard to >> have an upper bound on his level. After all, AlphaGo might just have played >> well enough for crushing Fan Hui, and a weak move while the position is >> still in favor of AlphaGo is not really a weak move (at least in a >> game-theoretic point of view...). >> > > I just want to point that according to Myungwan Kim 9p (video referenced > in this thread) on the first game, Alpha Go did some mistake early in the > game and was behind during nearly the whole game so some of his moves > should be weak in game-theoric point of view. > Thanks, this point is interesting - that's really an argument limiting the strength of AlphaGo. On the other hand, they have super strong people in the team (at the pro level, maybe ? if Aja has pro level...), and one of the guys said he is "quietly confident", which suggests they have strong reasons for believing they have a big chance :-) Good luck AlphaGo :-) I'm grateful because since this happened many more doors are opened for people working with these tools, even if they don't touch games, and this is really useful for the world :-) -- = "I will never sign a document with logos in black & white." A. Einstein Olivier Teytaud, olivier.teyt...@inria.fr, http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Mastering the Game of Go with Deep Neural Networks and Tree Search
> Without clarity, progress is delayed. Every professor at university will > confirm this to you. > IMHO, Petr contributed enough to academic research for not needing a discussion with a professor at university for learning how to do/clarify research :-) -- = "I will never sign a document with logos in black & white." A. Einstein Olivier Teytaud, olivier.teyt...@inria.fr, http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism
> > > I am pretty sure that such an implicit expression exists: it is << the >> number of etc etc >> > > We do not speak of just the definition of what kind of number to find, but > of the construction of finding the number (or already of a compression of > its explicit digits). It's hard to come up with a formal definition of "implicit expression" which excludes the definition itself :-) maybe something like a fast algorithm for computing a given digit (this exists for pi https://www.math.hmc.edu/funfacts/ffiles/20010.5.shtml ). (Well, it's fun, but I would not spend days on this :-) ) ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] AlphaGo and the Standard Mistake in Research and Journalism
> > > How do you know that an implicit expression (of length smaller than 10^80) > of the number does not exist? :) > I am pretty sure that such an implicit expression exists: it is << the number of etc etc >> (formalized for your favorite set of rules :-) ). -- ============= Olivier Teytaud, INRIA TAO Research Fellow --- http://www.slideshare.net/teytaud "Please stop quoting me on internet."___ Albert Einstein ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Mastering the Game of Go with Deep Neural Networks and Tree Search
If AlphaGo had lost at least one game, I'd understand how people can have an upper bound on its level, but with 5-0 (except for Blitz) it's hard to have an upper bound on his level. After all, AlphaGo might just have played well enough for crushing Fan Hui, and a weak move while the position is still in favor of AlphaGo is not really a weak move (at least in a game-theoretic point of view...). On Mon, Feb 1, 2016 at 12:12 PM, Petr Baudis <pa...@ucw.cz> wrote: > Hi! > > On Mon, Feb 01, 2016 at 09:19:56AM +, Darren Cook wrote: > > > 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. > > > > It seems [1] the smart money might be on Lee Sedol: > > > > 1. Ke Jie (world champ) – limited strength…but still amazing… Less than > > 5% chance against Lee Sedol now. But as it can go stronger, who knows > > its future… > > 2. Mi Yuting (world champ) – appears to be a ‘chong-duan-shao-nian (kids > > on the path to pros)’, ~high-level amateur. > > 3, Li Jie (former national team player) – appears to be pro-level. one > > of the games is almost perfect (for AlphaGo) > > > > > > On the other hand, AlphaGo got its jump in level very quickly (*), so it > > is hard to know if they just got lucky (i.e. with ideas things working > > first time) or if there is still some significant tweaking possible in > > these 5 months of extra development (October 2015 to March 2016). > > AlphaGo's achievement is impressive, but I'll bet on Lee Sedol > any time if he gets some people to explain the weaknesses of computers > and does some serious research. > > AlphaGo didn't seem to solve the fundamental reading problems of > MCTS, just compensated with great intuition that can also remember > things like corner life shapes. But if Lee Sedol gets the game to > a confusing fight with a long semeai or multiple unusual life > shapes, I'd say based on what I know on AlphaGo that it'll collapse just > as current programs would. And, well, Lee Sedol is rather famous for > his fighting style. :) > > Unless of course AlphaGo did achieve yet another fundamental > breakthrough since October, but I suspect it'll be a long process yet. > For the same reason, I think strong players that'd play against AlphaGo > would "learn to beat it" just as you see with weaker players+bots on > KGS. > > I wonder how AlphaGo would react to an unexpected deviation from a > joseki that involves a corner semeai. > > > [1]: Comment by xli199 at > > > http://gooften.net/2016/01/28/the-future-is-here-a-professional-level-go-ai/ > > > > [2]: When did DeepMind start working on go? I suspect it might only > > after have been after the video games project started to wound down, > > which would've Feb 2015? If so, that is only 6-8 months (albeit with a > > fairly large team). > > Remember the two first authors of the paper: > > * David Silver - his most cited paper is "Combining online and offline > knowledge in UCT", the 2007 paper that introduced RAVE > > * Aja Huang - the author of Erica, among many other things > > So this isn't a blue sky research at all, and I think they had Go in > crosshairs for most of the company's existence. I don't know the > details of how DeepMind operates, but I'd imagine the company works > on multiple things at once. :-) > > -- > Petr Baudis > If you have good ideas, good data and fast computers, > you can do almost anything. -- Geoffrey Hinton > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go > -- = Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ. Paris-Sud), bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Mastering the Game of Go with Deep Neural Networks and Tree Search
Ok, it's not blitz according to http://senseis.xmp.net/?BlitzGames (limit at 10s/move for Blitz). But really shorter time settings. I've seen (as you all) many posts guessing that AlphaGo will lose, but I find that hard to know. If Fan Hui had won one game, I would say that AlphaGo is not ready for Lee Sedol, but with 5-0... (incidentally, there is one great piece of news for machine learning people: people in industry are much more interested than before for letting us try our deep learning algorithms on their data and that's good for the world :-) ) ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Number of Go positions computed at last (John Tromp)
Hi; maybe, for the rules, you would like the Chinese rules, and in particular the "TROMP-TAYLOR CONCISE RULES OF GO" at https://www.cs.cmu.edu/~wjh/go/tmp/rules/TrompTaylor.html If you like maths, you might check Robson's result, which shows that with Japanese rules the game is Exptime-hard (exptime-completeness depends on the exact formalization of Japanese rules, which are too blurry...) (see at the end of this message). The complexity for Chinese rules is somewhere between Pspace and Expspace (this was discussed earlier in this mailing list, I guess... sorry for not remembering who pointed out first that the common belief that Go with Chinese rules is in Exptime has never been formally proved and is in fact not trivial). Interestingy, for Japanese rules, even for a subset of positions for which Robson's result is applied, the decidability of phantom-Go (in the sense: is there a move with winning probability >= 50% ?) is not proved (the undecidability is not proved, also :-) ); and for Chinese rules, the decidability is obvious, but the upper complexity bounds are just huge. = Nb: Robson's paper is discussed here https://docs.google.com/document/d/1Oq4Vk4oEDZQEbB3hql8nCDUK69pmyJrG0rs9LvsG_WM/edit; I have scanned the original report and, as Michael agrees for it, I will put this on the web soon (for the moment only rare people have access to the document in paper format :-) ). On Mon, Jan 25, 2016 at 9:11 AM, Mark Goldfain <markgoldf...@comcast.net> wrote: > Well, although Dr. Tromp seems rather modest about this result, I haven't > heard of anyone else doing similarly interesting work on the theoretical > foundations of the game. This set of results is fascinating and > newsworthy. > Congratulations on carrying this out, all the way up to 19x19 ! > > I have a couple of questions, if these comments are being seen by Dr. > Tromp. > > 1. So, as you go up the chart, what is the percentage of all possible > positions that are legal? > Isn't that a trivially-quick corollary from your results? [ (Tromp > result) / (3 **(n*n)) ] > And isn't that an interesting sequence? Perhaps more intuitively > useful to a go-programmer > than the raw numbers themselves? Does this set of ratios make any > intuitive sense to you > ... or should I rephrase that as -- can you rationalize these results > of the ratios? > > 2. One of the most frustrating things about writing a program to play go > is that the rules are > a bit blurry. Far too blurry to really satisfy a computer > programmer. I think some of the > work you've done over the years is in creating a rigorous and > computable set of rules. > Is this correct, or have I heard wrong on this count? Do you have a > set of rules that > could be profitably used for the basis of a go-playing program, that > you like today? > Is there a link to such a rule set somewhere? > > Thanks, > -- Mark Goldfain > > ___ > Computer-go mailing list > Computer-go@computer-go.org > http://computer-go.org/mailman/listinfo/computer-go -- = Olivier Teytaud, olivier.teyt...@inria.fr, TAO, LRI, UMR 8623(CNRS - Univ. Paris-Sud), bat 490 Univ. Paris-Sud F-91405 Orsay Cedex France http://www.slideshare.net/teytaud ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [Computer-go] Fast pick from a probability list
In case the question is more on the computational part, you might use a binary tree, so that you do the selection in time O(log(number of moves)) instead of O(number of moves). The update is also in logarithmic time for some probability update rules (to be discussed, depends on how you modify your probabilities - well, if you modify them :-) ). ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
[Computer-go] cgos 9x9
Hello; we would like to come back to Computer-Go, starting with the small 9x9 board; is there any such Cgos running somewhere ? Thanks to people currently running the 13x13. Or maybe we should run a 9x9 server ourselves if nobody has this in his/her agenda ? Best regards, Olivier ___ Computer-go mailing list Computer-go@computer-go.org http://computer-go.org/mailman/listinfo/computer-go
Re: [SPAM] Re: [SPAM] [computer-go] Paper about Mogo's Opening Strategy
I'm sure many people are curious - MoGo(TW?) doesn't participate much in computer tournaments nowadays, are you working on some new exciting things or is the project mostly asleep right now? :-) Competitions are very boring and time consuming. Other people from the mogo-team can participate in tournaments if they want to, but for me I prefer to work on improvements, and in particular I prefer to try big changes (which fail 97% of the time) than small changes which provide negligible improvements. When there are computations every 2 months, the small improvements often take all the place. There are works in progress around MoGo: - We'd like to have an almost solving of 9x9 Go, by working in particular on a huge opening book. Nonetheless, there's still a lot of work on that. For example, MoGoTW can play very stupid move if the opponent makes a stupid opening move, and removing this would be great. - As many people, we would really like to have learning from one branch of the tree to another. We have some things which provide a few percents improvements, but we are a bit tired of this kind of small improvements, and I'd like a big change. - Also, we have many applications in progress in other fields, from classical artificial intelligence tasks (like expensive optimization or active learning) or for completely industrial tasks (like my favorite application, namely power management) - We also try to automatize the building and validation of patterns or UCT formula - something which is important far beyond Go. However, for Go, this is clearly not very important - mogo and all strong programs are by far too optimized for improving a lot by empirical tuning. For partially observable games, things are very different I think - as pointed out in some nice papers tuning becomes the main thing in very difficult frameworks like partially observable games, making them quite interesting as a benchmark. I guess some of these goals are shared by many people in this mailing list, so I'm sorry for this long email with probably nothing very original in it :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Paper about Mogo's Opening Strategy
Apparently an opening book cannot be used with a stronger or weaker Go player as-is, but I wonder how useful it would be as a seed? If we follows the fictitious play algorithm, maybe we should accept a modification of the opening book only after comparison with *all* previous versions of the OB. However it is quite time consuming... may be there's nothing faster than that... ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [SPAM] [computer-go] Paper about Mogo's Opening Strategy
This is very interesting, do you have pointers to any papers or presentations concerning MCTS applications like this in any detail? If not yet, I'm sure many people on this list will be interested to hear about any publications in this area too when you finish some of the applications. 1) Application to fundamental AI tasks: Application to noisy non-linear optimization (Algorithmica 2009): http://hal.inria.fr/inria-00369788 (personnally, this work convinced me that UCT was really a great algorithm - for noisy applications, UCT really brings an improvement over many forms of MCTS, and as I've spent a long time trying to solve the same thing with other tools without success, I've been very surprised of succeeding at the first trial with UCT) Application to non-linear optimization: http://hal.inria.fr/inria-00374910/fr/ Application to active learning (ECML 2009) http://hal.inria.fr/inria-00433866 2) Benchmarks on problems not too far from industry: - Guillaume Chaslot et al published something around stock management - Martin Müller et al published something around planning 3) Directly real-world or industrial applications Application to library tuning (ICML 2009) http://hal.inria.fr/inria-00379523/ The application to energy management is a big concern to me - it's in progress. These problems have a huge ecological and economical importance, it would really be great if computer-Go had an impact on this, and the specificities of the problem are perfect - withing the partially observable nature of the problem :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] Paper about Mogo's Opening Strategy
I recommend the paper http://hal.inria.fr/docs/00/36/97/83/PDF/ouvertures9x9.pdf by the Mogo team, which describes how to use a grid to compute Mogo's opening book using coevolution. I must precise that you often find bad moves in the opponing book. Doing this grid-based opening-book building is much better than nothing, but interacting with humans is quite efficient. We now have a similar process, but with interactions with humans in the loop. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Reference Montecarlo TreeDecision Bot.
I've found that AMAF gives very little boost with light playouts, Thanks for this interesting comment. I would (erroneously) have believed that AMAF gives better results with non-optimized implementation (e.g. in Havannah with no expertise Amaf provides huge improvements). In particular, I believed it was moderately efficient in 19x19 due to the patterns which already provide relevant informations - but I could never test it (testing properly this assumption requires the tuning of the version without Rave, which would be time consuming and boring :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Simple gogui problem
• record results for all visited nodes___ Where do you record the results? In each node, you keep the statistics of simulations in this node. Many informations can be useless in each node: rave values (the gellysilver paper I've emailed to you) criticality (to be found on Rémi Coulom's web page), but for a first implementation the main thing is the number of won simulations and the number of lost simulations (among those which go through this node). Possibly, you use a hashtable so that if two nodes are identical (up to the history reaching the node, which might nonetheless matter in case of superko) you can share the information. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Mathematical Go
You can see and hear Elwyn Berlekamp delivering a 2006 talk about Mathematics and Go (culminating in a discussion of coupon go) at: http://www.youtube.com/view_play_list?p=005B561126D6A51E . Thanks a lot for pointing out this very interesting video. Seemingly, the nice historical discussion is not in the book ? (not sure of that, I just did not find it on the google-books version) For an overview of the book, google-books provides the introduction and overview (just google-books berlekamp wolfe). Someone knows a written reference with contents similar to this video and in particular the historical aspects ? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Live broadcasting at UEC Cup
Wow! This is quite surprising to me: 1 KCC Igo 2 Katsunari 3 Zen 4 Shikousakugo 5 Many Faces of Go 6 Erica 7 Kiseki 8 Galileo (upset Crazy Stone, due to a Chinese/Japanese rules mismatch) 9 Crazy Stone 10 Aya There are so many programs stronger than Zen, ManyFaces, CrazyStone and Aya ? There was, as sometimes in the past, a trouble with the communication time or something like that, or there are really so many very strong bots now ? Best regards, Olivier 2009/11/29 Ian Osgood i...@quirkster.com Thanks for the early report! (I was sorry not to see Fudo Go in the tournament. Were you involved with any of the other teams?) Here are the second day knockout tournament unofficial results. Any mistakes are my own. Thanks to the organizers for the live screencast! 1 KCC Igo 2 Katsunari 3 Zen 4 Shikousakugo 5 Many Faces of Go 6 Erica 7 Kiseki 8 Galileo (upset Crazy Stone, due to a Chinese/Japanese rules mismatch) 9 Crazy Stone 10 Aya 11 GOGATAKI 12 Rock 13 Nomitan 14 Kinoa Igo 15 Boon 16 Kerebos Also, several exhibition matches were held (Zen beat Crazy Stone, and MFGO beat Aya). I did not stay up for the two professional exhibition games. Ian On Nov 28, 2009, at 5:42 AM, Hideki Kato wrote: You can watch some interesting games and exhibition games on the second day of the third UEC Cup at http://jsb.cs.uec.ac.jp/~igo/eng/broadcast.htmlhttp://jsb.cs.uec.ac.jp/%7Eigo/eng/broadcast.html . Schedule: http://jsb.cs.uec.ac.jp/~igo/eng/schedule.htmlhttp://jsb.cs.uec.ac.jp/%7Eigo/eng/schedule.html Unofficial quick results of the first day: pos program win-lose-draw 1 Zen 6-0-0 2 Nomitan 5-1-0 3 KCC Igo 5-1-0 4 Kinoa Igo 5-1-0 5 GOGATAKI 4-1-1 6 Shikosakugo 4-2-0 7 Erica 4-2-0 8 Aya 4-2-0 9 Kiseki4-2-0 10 Rock 4-2-0 11 boon 3-2-1 12 Kerberos 3-3-0 13 Galileo 3-3-0 --- cut line to the second day --- 14 Island 3-3-0 15 caren3-3-0 16 PerStone 3-3-0 17 Tombo3-3-0 18 Sango alpha 3-3-0 19 Igoppi 2-4-0 20 Boozer 2-4-0 21 Kasumi 2-4-0 22 ME_arc 2-4-0 23 Mayoigo 2-4-0 24 Martha 2-4-0 25 Njarahojara 1-5-0 26 kudok1-5-0 27 Gekishin 0-6-0 28 Sanshine 0-6-0 Solkoff and SB are omitted. Seeded programs to the second day: 1 Crazy Stone 2 Many Faces of Go 3 Katsunari The Third UEC Cup: http://jsb.cs.uec.ac.jp/~igo/eng/index.htmlhttp://jsb.cs.uec.ac.jp/%7Eigo/eng/index.html Short random comments: Aya was unlucky, lost two games against Erica and KCC. Erica gets much stronger by implementing Remi's larger patterns; lost two games by a communication trouble and waisting time by a sleeping laptop. Zen vs. KCC was a close game. Zen uses 512 cores. Hideki -- g...@nue.ci.i.u-tokyo.ac.jp (Kato) ___ 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/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [computer-go] Re: A cluster version of Zen is running on cgos 19x19
In your (or Sylvain's?) recent paper, you wrote less than one second interval was useless. I've observed similar. I'm now evaluating the performance with 0.2, 0.4, 1 and 4 second intervals for 5 second per move setting on 19x19 board on 32 nodes of HA8000 cluster. Yes, one second is fine for 5 seconds per move. Maybe you can check if you have a linear speed-up if you artificially simulate a zero communication time ? My guess is that the communication time should not be a trouble, but if you don't use MPI, maybe there's something in your implementation of communications ? By the way, a cluster parallelization in MPI can be developped very quickly and MPI is efficient - mpi_all_reduce has a computational cost logarithmic in the number of nodes. Good luck, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [SPAM] Re: [computer-go] Re: A cluster version of Zen is running on cgos 19x19
Even if the sum-up is done in a logarithmic time (with binary tree style), the collecting time of all infomation from all nodes is proportional to the number of nodes if the master node has few communication ports, isn't it? No (unless I misunderstood what you mean, sorry in that case!) ! Use a tree of nodes, to agregate informations, and everything is logarithmic. This is implicitly done in MPI. If you have 8 nodes A, B, C, D, E, F, G, H, then (i) first layer A and B send information to B C and D send information to D E and F send information to F G and H send information to H (ii) second layer B and D send information to D F and H send information to H (iii) third layer D and H send information to H then do the same in the reverse order so that the cumulated information is sent back to all nodes. By the way, have you experimented not averaging but just adding sceme? When I tested that my code had some bugs and no success. Yes, we have tested. Surprisingly, no significant difference. But I don't know if this would still hold today, as we have some pattern-based exploration. For a code with a score almost only depending on percentages, it's not surprising that averaging and summing are equivalent. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [SPAM] Re: [SPAM] Re: [computer-go] Re: A cluster version of Zen is running on cgos 19x19
Interesting, surely the order is almost logarithmic. But how long it takes a packet to pass through a layer. I'm afraid the actual delay time may increase. With gigabit ethernet my humble opinion is that you should have no problem. But, testing what happens if you artificially cancel the time of the messages might confirm/infirm this. If you have troubles due to the communication time, I'm sure you can optimize it. MPI provides plenty of well done primitives for encoding communications. Except if you need very precise optimization, it's not worth working directly with sockets. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Re: A cluster version of Zen is running on cgos 19x19
The performance gap is perhaps due to the algorithms. Almost all cluster versions of current strong programs (MoGo, MFG, Fuego and Zen) use root parallel while shared memory computers allow us to use thread parallelism, which gives better performance. I think you should not have troubles with your networks, at least with the number of machines you are considering. Perhaps you should increase a little the time between two communications ? With something like mpi_all_reduce for averaging the statistics over all the tree at each communication, more than 3 or 4 communications per second is useless. Averaging statistics in nodes with less than 5% of the total number of simulations might be useless also. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] [computer-go] MoGo and Fuego question.
How to activate patterns? Why they are not on on default? They are the default, but they are removed if they are not in the path when running (it can be seen on the stderr - the number of patterns read must be 0). In 19x19 there is a big impact. (In the release, there's no pattern) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Joseki Book
There is a paper about that in http://hal.inria.fr/inria-00369783/en/ and Tristan Cazenave published something around that also. (these two works are about the automatic building of opening book in self-play) See also the references in the PDF above. Best regards, Olivier Only papers I can recall are from seventies (assuming you mean academic papers) from Wilcoxx. I may have electrical copies. Not sure though. I managed to find some of them from ACM site. That paper described position based approach where each and every stage was stored into datastructure, kinda like huge pattern matching library. Was called lenses if I remember correctly. More common way is store joseki moves as a tree. Biggest issue is always hos key in all those variations. Petri 2009/11/9 Jessica Mullins jmull...@lclark.edu Hi, I am wondering what is the best way to build a Joseki Book? I am a student at Lewis Clark College and am working with Professor Peter Drake to build a Joseki Book for the program Orego.sed aproach i.e each state of joske Right now I am extracting moves from professor players and saving those into a database. Then if during game play a position is contained in the database, play the response move like the professional. I am just wondering what other people have done to build a Joseki Book, or if anyone knows of any papers that might be helpful. Thank you, Jessica Mullins Lewis Clark College '10 ___ 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/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] Citation on zero exploration?
http://computer-go.org/pipermail/computer-go/2009-June/018773.html As I've often said something related to that (e.g. in http://hal.inria.fr/inria-00369786/fr/ ) I'd like to be more precise. What follows is for binary deterministic games, and I precise at the beginning that this is not intended to make programs much stronger. UCT (with exploration) is consistent, in the sense that asymptotically it will find an optimal move, if any winning move exists. With no exploration, this is no more true, even with rave: there are cases in which rave will only focus on one move and will simulate only this one, in spite of a poor winning rate. However, a simple trick recovers consistency: use (nbWins+K)/(nbSimulations+2K) for example, or other regularization tricks, if the weight of Rave decreases to 0 when the number of simulations goes to infinity. However, if you have patterns with negative weights and the score is biased by these patterns (possibly until a negative value), then you loose consistency whenever the weight of the patterns decrease to 0 when the number of simulations of the corresponding move goes to 0. Then, we might feel that we need more than consistency: we want consistency, and we do not want to simulate all the tree infinitely often. This can be done with some specific rules, and in mogo we have added a simple patch which, roughly, consists in simulating randomly the children nodes when the success rate of a node is very low (below 30%). This ensures that the following rules are enough for ensuring consistency: score(move) - winRate(move) -- 0 as nbSims(move) -- infinity as we optimize automatically patterns and parameters, the advantage is that we can do it without any risk of loosing consistency. More precisely, http://www.lri.fr/~teytaud/consistency.pdf (submitted; not a lot of numerical experiments, it's for theory mainly - yet, for 500 000 simulations per move, there is a significant difference, and for a specific position, it works well - there was absolutely no tuning for this). I don't claim this will make a big change in Monte-Carlo Tree Search - just a bit of theoretical understanding, and the pleasure of asymptotic consistency - maybe it will make a real difference for very long thinking time for which we can't use tuning due to the computational cost :-) and it's the first time I have more than 50% for a modification derived by theoretical ideas :-) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [computer-go] Citation on zero exploration?
I don't know if a post in the computer-go mailing list is a report, but you can find numbers in this post: http://computer-go.org/pipermail/computer-go/2008-May/014854.html From the numbers I would say that it shows that all sufficiently small constants are equivalent - maybe more experiments would be interesting. Olivier I'm actually looking for something weaker than what Olivier has offered: a published report of the empirical finding that (for some programs, at least) an exploration coefficient of zero works best. Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ On Nov 9, 2009, at 10:15 AM, Olivier Teytaud wrote: Hi; I'd like to answer your post but I must admit I've not clearly understood. My PDF file is essentially a mathematical analysis, proving that we can have consistency with some rules, without having infinitely many visits of the whole tree. UCT has the first property (consistency), but not the second (UCT visits all the tree infinitely often). This is proved under clearly stated assumptions on the problem; including deterministic two-player zero-sum games, and therefore including Go. Best regards, Olivier By result, do you mean this observation or a quest for an explanation? If you merely wish to say that many/most current UCT programs have no need for an exploration term, then that is a context-specific (e.g. not for the E-E in Go paper) heuristic or experimental statement, not a formal one. A source for such a statement has to be more than a paper that simply notices a similar effect for their own application. One would have to reference a larger body of experimentalists or a general consensus. Just my humble opinion, Cenny Wenner On 11/9/09, Peter Drake dr...@lclark.edu wrote: Many of us have concluded that, with RAVE, there is no need for a UCT exploration term: http://computer-go.org/pipermail/computer-go/2009-June/018773.html Is there a published source on this result that I could cite? Thanks, Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ ___ 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/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ 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/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [computer-go] Re: First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Thanks a lot for this information. This is really very interesting and not widely known. Maybe chess is less closed than I would have believed :-) Olivier Arno Nickel played three games with Hydra over a few months in 2005. He won 2.5-0.5 http://en.wikipedia.org/wiki/Arno_Nickel I doubt much have changed since 2005. Also note that, while certainly among top players, Arno Nickel was never a correspondence chess champion. -- Seo Sanghyeon ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Re: First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Some elements around blitz: - My feeling that blitz games are harder for computers is based on our games against humans: we always lost games with short time settings. Even in 9x9, Motoki Noguchi or Pierre Audouard could win plenty of fast games, whilst playing strange openings for fun. This is for sure on a small sample. - The newspapers don't take into account or even report the difference between blitz games and standard games on the 29th of october, and they use the not very relevant complexity comparisons based on the number of possible boards or games. But they have nice photos for promoting computer-go :-) Best regards, Olivier Dear all (in particular for your question, Hideki!), please find enclosed some newspapers about the games played on October 29th. Most of them are in chinese. I don't read chinese, if some people can extract some elements... I'll try to have some translations here with our chinese students. Best regards, Olivier -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Yes, this group does not have a consensus at all on this. On the one hand we hear that MCTS has reached a dead end and there is no benefit from extra CPU power, and on the other hand we have these developers hustling around for the biggest machines they can muster in order to play matches with humans! And Olivier claims that computers benefit more from additional thinking time than humans! Thanks for this comment. I agree that something is strange here :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Just curious, who actually claimed that and what was it based on? I don't know who claimed it first, and who agreed for it, but I agree with it :-) More precisely, I think that increasing time and computational power makes computers stronger, but not for some particular things like long-term life-and-death in corners, or semeai situations. This makes a big limitation on what is possible with MCTS algorithms, in particular against humans. We made a lot of efforts for online learning of Monte-Carlo simulations, in order to improve this, but there's no significant improvement around that. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
But is it shown that the score is well done for these properties to hold in case of RAVE-guided exploration? Since it massively perpetuates any kind of MC bias... This only matters for the fact that we don't visit all the tree. For the consistency (the fact that asymptotically we will find the best possible decision), there's no problem. If score ~ success rate for n-- infinity (which holds for most usual rules, including rave rules) we also have that, for binary games, we have some good properties on the part of the tree which is visited. Please not that I do not claim that major improvements are possible in computer-go thanks to this. We only observed a very small improvement on success rates, and a good behavior on the situation which appeared during the game against Fan Hui. It might be interesting to know, for people who have similar problems in their bot (a situation in which, even with huge computation time, the good estimate is not found), they solve it with this. We use a stupid method, i.e. the success rate. The pattenrs are bigger than 3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are used for distributing the computational effort among the tested patterns. Thank you for pointing me to more study material. :-) The following paper is great for Bernstein races: http://icml2008.cs.helsinki.fi/papers/523.pdf Please note, however, that we had only very small improvements with races. Maybe our code has had too many tuning steps in the past for being strongly improved by random generation of patterns and bernstein races for validating them. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
If there are people interested in a ph.D. or a post-doc around Monte-Carlo Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not necessarily / not only computer-go). Excuse me, but what press conference and where to ask? People interested in a ph.D. or a post doc can contact me. This was during a press conference at Taipei around a French-Taiwanese grant for joint research. but I can find no links even with Google. I'll ask to the taiwanese people if there is something on the web about the press conference. I was only there through a video. I don't know if there is something on the web. This is essentially for the launching of a France/Taiwan collaboration around Monte-Carlo Tree Search, I guess there are not thousards of journalists from tenths of countries interested in it :-) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Could you give us at least a general picture of improvements compared to what was last published as www.lri.fr/~teytaud/eg.pdfhttp://www.lri.fr/%7Eteytaud/eg.pdf? Is it just further tuning and small tweaks or are you trying out some exciting new things? ;-) There is one important improvement, for which I must check with coauthors if they agree for me to explain it. Below the other recent improvements in 9x9. We have also recently encoded some (very simple) tricks against bad cases as we had against Fan Hui (i.e. cases in which the only good move is not simulated). Roughly, is the value of the node is very bad, then simulate randomly among the sons. We can show (mathematically) that with such tricks, we have the consistency (as UCT), plus some frugality (i.e. we do not simulate all the tree, even with infinite computation time whereas UCT simulates all the tree AND simulates all the tree infinitely often). It gives very little improvement in self-play, but it understands better at least the situation seen in the game with Fan Hui. What I like in this improvement is that it's the first time there is something which was mathematically developped for mogo and which leads to a positive result. Well, maybe this changes only 1% of games, but maybe it makes mogo more robust for complicated ko fights which do not occur in self-play. Finally, there was a GP-based development of new patterns. However, this is quite minor I guess - I like the fact that this GP-based module works in a somehow stable manner, but maybe it would only be worth using it on an implementation which is not yet optimized. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
AIUI, once upon N simulations in a node you take let's say the node with the lowest value, pick one son of it at random within the tree and start a simulation? I'll try to write it clearly (for binary deterministic games, extensions can be shown but they are too long and out of topic in this mailing list I guess :-) ): If (average value of father threshold ) then randomly pick up one son else pick up the son with maximum score end If the score is asymptotically equivalent to the success rate, and if the threshold is 0 and 1, then this ensures consistency (convergence to optimal move). If the score is well done, then this is consistent without visiting all the tree. UCT (with non-zero constant) visits all the tree, and does so infinitely often. UCT (with zero constant) does not visit all the tree, but it is not necessarily consistent. Wow - one of my planned little projects was genetic development of the 3x3 patterns... To evaluate patterns, do you use tournaments or some smarter method? I feared one generation would take awfully long... We use a stupid method, i.e. the success rate. The pattenrs are bigger than 3x3, with jokers in them. Bandits (Bernstein races, slightly modified) are used for distributing the computational effort among the tested patterns. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Dear all, some comments by my Taiwanese colleagues about the game played by MoGo against the 9p pro: 1) mogoTW finally ran on the 16*8 system on Oct. 26, 2009. 2) Contributors for which I did not know their real name: Hsien-Der Huang and Cheng-Wei Chou (sorry for them!) 3) Some comments by the pro, translated by people from Taiwan: === He told the jounalists that he made a mistake on move 26, which is a move that it is hard to find such kind an error (move 26) even for a professional Go player. However, he was so surprised that MoGoTW found this mistake that he made during the game. That means the level of MoGoTW in 9x9 game has made an improvement than last time (08/2009). In addition, he also told the journalists that MoGoTW made a good move at Move 29. He thought that the main reason that MoGoTW won the game was Move 29 and MoGoTW didn't make any mistake after Move 29. == ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
I forgot the most important thing around this win against a pro: this press conference was for the starting of a project, and in this project we have funding for ph.D. or postdocs. If there are people interested in a ph.D. or a post-doc around Monte-Carlo Tree Search, candidates are welcome (Monte-Carlo Tree Search, and not necessarily / not only computer-go). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] MoGo Zones
(Sylvain et al. 2006) describes the use of CFG-based zones in random simulations to simulate only the local position and tune the score based on few thousands of simulations of outside of the zone. It doesn't seem the idea is too practical (especially with RAVE, but there seem to be more problems), but I'm wondering if MoGo or anyone is still using it, perhaps in a modified form? Not like that in Mogo. We have some local tool for heavy playouts which use local simulations, but for the moment this version is weaker than the light playout - even with fixed number of simulations. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] First ever win of a computer against a pro 9P as black (game of Go, 9x9).
Dear all, For information, our Taiwanese partners(**) for a ANR grant have organized public demonstration games between MoGoTW (based on MoGo 4.86.Soissons + the TW modifications developped jointly with our Taiwanese colleagues) and C.-H. Chou 9P, top pro player winner of the LG Cup 2007. This was during a press conference at Taipei around a French-Taiwanese grant for joint research. Details: a) MoGoTW was running on 32 quad-cores(*) in Taiwan. b) There were two blitz games (15 minutes per side), won by the pro. c) There was one non-blitz game (45 minutes per side). MoGo was unlucky as it was black, but it nonetheless won the game. This game is enclosed. All games can be found on KGS (account nutngo) Remarks: a) Fuego won as white against a 9P a few months ago. Therefore computers have won both as white and black against top players :-) We now should win on a complete game like 4 out of 7 games and the job would be completly done for 9x9 Go :-) b) MoGo already won a game as black, against Catalin Taranu, but I guess the pro, at that time, had played an original opening somehow for fun (I'm not sure of that, however). c) My feeling is that blitz games are not favorable to computers... Statistics are in accordance with this I guess. Humans are stronger for short time settings. d) If I understand well, MoGo won a final semeai in the upper right part. But, nearly everybody on this mailing (except you, Sylvain, maybe, if you still read this mailing-list :-) ?) reads go games better than me, so don't trust this comment :-) e) The game was longer than most important games I've seen (59 moves). All comments welcome. Best regards Olivier (*) mogoTW was supposed to run on this 32x4 system, but other platforms were prepared in case of trouble on this cluster. I'll publish a correction if I see that the game was not played on this machine. (**) contributors include all the mogo-people, plus Mei-Hui Wang, Chang-Shing Lee, Shi-Jim Yen, and people that I only know by their nicknames (Coldmilk, TomTom...) - sorry for the people I've forgotten, names in Chinese are difficult for me :-) 20091026-1-Zhou vs. MoGoTW9X9.sgf Description: application/go-sgf ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] Software for a supercomputer?
We tested mogo on several Linux clusters, and if MPI is available everything is fine. If you want the code, I can send you a .tar.gz and a README on how to make it run. Real time discussion with gmail-talk or something like that is a good tool also. My humble opinion on the relevance of supercomputers in computer Go is that supercomputers might matter for 19x19, but no so much as there are strong limitations which are the same for a quad-core and a supercomputer; and in 9x9 the difference is big in self-play, but not so big in games against humans. If you choose 9x9 we can use mogoTW instead of MoGo. But you might use Fuego or ManyFaces as well :-) Or we can run each bot once if you have time for it :-) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Progressive widening vs unpruning
What's your general approach? My understanding from your previous posts is that it's something like: Your understanding is right. By the way, all the current strong programs are really very similar... Perhaps Fuego has something different in 19x19 (no big database of patterns ?). I'm not at all sure of this conjecture on Fuego. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] Progressive widening vs unpruning
hi; I don't know to which extent my terminology is commonly used, but it seems to be close to the distinction by Dave (but not exactly equal). For me I use progressive widening when we add moves, progressively, to the pool of moves which are to be considered; whereas I use progressive unpruning when a score is computed for all moves, with a weight depending on the number of simulations; typically, I consider the Rave formula in GellySilver as a progressive unpruning (with, for prior value, the Rave value). Progressive unpruning is better in MoGo, in spite of the fact that: * with progressive widening, if you apply pure UCB values, you are definitely consistent and explore (asymptotically) all the tree; * with progressive unpruning, if your prior is bad, you might have situations in which the score of the only good move is 0, whereas all bad moves have values going to 0 but 0 and therefore the good move is never simulated (this can, however, easily be patched by a lower bound on the value given by the prior) Progressive unpruning, if you use the same terminology as me, has the advantage that the number of moves to be considered is adapted depending on the score; if you have three reasonnable moves and 300 bad moves, with progressive unpruning you'll visit all moves, whereas progressive unpruning will stay on the three reasonnable moves as long as they provide a better score than the prior score for the 300 bad moves. (The difference with Dave's terminology is that I do not necessarily use a sum of a prior number of simulations and a number of real simulations; I use a weighted sum with weight depending on the number of simulations in a complicated manner - I think this was not the case in the first paper by Chaslot et al about progressive un pruning (well, I believe this is the first paper about progressive unpruning)) Best regards, Oliveir ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [computer-go] Progressive widening vs unpruning
I guess I'm not really appreciating the difference between node value prior and progressive bias - adding a fixed small number of wins or diminishing heuristic value seems very similar to me in practice. Is the difference noticeable? It just means that the weight of the prior does not necessarily decrease linearly. For example, for Rave, you might prefer to have a weight which depends on both the number of Rave simulations and on the number of real simulations. The formula designed by Sylvain for Rave, for example, can't be recovered without this generalization. For the current mogo, as we have several terms (one for the empirical success rate, one for Rave, one for patterns, one for expert rules...), some of them with used at different places in the code (there is a prior expressed in terms of rave simulations, and a prior expressed as real simulations), it would be complicated to come back to something much simpler ... but perhaps it's possible. Such a clarification might be useful, I have no clear idea of the impact of Rave values now in mogo, in particular for long time settings, and it's not so easy to clarify this point - too many dependencies between the many terms we have. I think someone pointed out a long time ago on this mailing list that initializing the prior in terms of Rave simulations was far less efficient than initializing the prior in terms of real simulations, at least if you have classical rave formulas - at least, we had an improvement when adding a prior in the real simulations, but we had also an improvement when adding one more term, which is not linear. Sorry for forgetting who :-( Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] IEEE T-CIAIG Special Issue on Monte Carlo Techniques and Computer Go
IEEE Transactions on Computational Intelligence and AI in Games Special Issue on Monte Carlo Techniques and Computer Go Special-issue editors: Chang-Shing Lee, Martin Müller, Olivier Teytaud In the last few years Monte Carlo Tree Search (MCTS) has revolutionised Computer Go, with MCTS programs such as MoGo, Crazy Stone, Fuego, Many Faces of Go, and Zen achieving a level of play that seemed unthinkable only a decade ago. These programs are now competitive at a professional level for 9x9 Go, and with an 8 stone handicap for 19x19 Go. The purpose of this special issue is to publish high quality papers reporting the latest research covering the theory and practice of these and other methods applied to Go, and also in applying MCTS to other games. MCTS can play very well even with little knowledge about the game as evidenced by its success in General Game Playing. However, it does not work well for all games, which poses some interesting questions. When and why does it succeed and fail? How can it be extended to new applications where it does not work yet? How best may it be combined with other approaches such as classical minimax search and knowledge-based methods? Topics include but are not limited to: l Emergent Technologies for Computer Go l Variants of Go (phantom Go, Go Siege) l Knowledge Representation Models for Computer Go l MCTS and Reinforcement Learning l MCTS for Video Games l Approximation Methods for MCTS l MCTS for General Game Playing l Hybrid MCTS Approaches l Evolving MCTS Players Authors should follow normal T-CIAIG guidelines for their submissions, but clearly identify their papers for this special issue during the submission process. See http://www.ieee-cis.org/pubs/tciaig/ for author information. Extended versions of previously published conference papers are welcome providing the journal paper provides a significant extension of the conference paper, and is accompanied by a covering letter explaining the additional contribution. Schedule · Deadline for submissions: March 15, 2010 · Notification of Acceptance: June 15, 2010 · Final copy due: October 20, 2010 · Publication: December 2010 or March 2011 ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] RE: [computer-go] IEEE T-CIAIG Special Issue on Monte Carlo Techniques and Computer Go
Before monte carlo I spent a couple of years writing and tuning an alpha-beta searcher. It's still in there and I ship it to provide the lower playing levels. Alpha-beta with limited time makes much prettier moves than monte carlo. Would there be interest in a paper that compares the same knowledge and engine used in an alpha-beta and monte carlo framework? In my humble opinion, definitely yes; I'll be an interested reader of this. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] KGS bot tournament
As always, all players, however weak, are welcome. There are in fact some strong entrants for this event, but they will not mind at all having some weaker opponents - the more the better, particularly in this fast tournament with 15 rounds. Instructions for entering are at http://www.weddslist.com/kgs/how/index.html I hope you did not consider us as a strong entrant; this is the first participation of our new bot and main parts change everyday (even this morning :-) ). A long time ago it was said that weak or uncertain entrants are welcome and we participate in this spirit. (I have precised that some parts are common with mogo and therefore according to the rules versions of mogo existing in various other locations can't participate - how I precise that this would not be a trouble for us.) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] Re: KGS bot tournament
Independently of you own view I consider MoGoBot to be a very interesting participant in the tournament. It's really a trial for MoGoTw :-) the name is mogobot1 because I've kept the same KGS account, but mogotw is not mogo. In my eyes, besides MoGo, MFoG, and Zen only Fuego and Valkyria are missing from the top league. There's CrazyStone at least, also. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] Re: [SPAM] RE: [SPAM] [computer-go] Conflicting RAVE formulae
We added (MoGo's original) patterns and RAVE at about the same time. Both helped a great deal, and using both was best of all. You mean mogo's 3x3 patterns I guess; the discussion here is about pattern databases for biasing the research in the tree (patterns with size until 19x19) and how they cumulate with Rave in 19x19. Essentially, MoGo, Mango, Zen, CrazyStone use a automatically built pattern database, whereas ManyFaces use a mix between an automatically built pattern database and a handcrafted pattern database. Mogo, ManyFaces, CrazyStone use Rave values; I don't know for Mango and Zen. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] RE: [SPAM] [computer-go] Conflicting RAVE formulae
Hi David, Thanks for these information. Your patterns are not automatically extracted; I don't know to which extent we would benefit from patterns like yours in MoGo, or to which extent you would benefit from automatically extracted patterns as ours, and to which extent it is nearly equivalent or redundant. I don’t think of Many Faces as having a big database of patterns since there is so much code, and only 1900 general patterns, but I think in comparison with other strong programs you might consider it to have a large pattern database. Sure! it's different in the way you generate it, but it's also a large pattern database. That's nearly what I meant by writing that you have a huge part of go expertise (in my mind I separated automatically extracted patterns and handcrafted rules for biasing the tree search - sorry for my unclear email). For us, we had a big improvement in mogo when adding patterns _after_ RAVE, and I don't know clearly if we should try to remove rave (and then tuning the formula - this is a tedious work and that's why I've not tested it yet). If you have added rave _after_ patterns, and also had a great improvement, this might indicate that both are necessary for optimal performance. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] rave and patterns
Thanks for sharing all this information, David. It would be easy to turn off rave and run some tests to do the win rate. Would take about a day to get significant results. I think RAVE still helps a lot. I agree that it's easy to turn off rave, but I think that for a fair comparison you would have to tune the formula for using patterns. For sure, just removing RAVE will make the code much weaker, but removing Rave + re-tuning the formula without rave is something else. All win rates are on 9x9 vs gnugo 3.7.20 level 10 with 5000 playouts. After this I switched to testing 19x19, and stopped tuning for 9x9. Just a point around that: tuning in 9x9 and 19x19 is very different (at least for us), but also tuning for short time settings and tuning for long time settings is very different. We always check that the improvement remains significant for real numbers of simulations. Some of the best improvements in MoGo (in particular the fill board) were of no use for small numbers of simulations (by the way, I hope you'll have improvements with this as well as us, it would be nice for this rule if it was more general than only efficient in MoGo :-) ). I think many faces’ patterns help much more on 19x19 than on 9x9. For us, in MoGo, the database of patterns has a very little effect in 9x9. But we made no effort for designing patterns specifically for 9x9. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [SPAM] [computer-go] Conflicting RAVE formulae
Just a small comment: adding one more term taking into account big patterns (big = more than 3x3) provide a huge improvement in 19x19. In my humble opinion there is more to win with adding such a term than by modifying the formula. Of course, it implies collecting a database of SGF files and extracting from it a database of patterns with their values :-) In 19x19, databases of big patterns (as in CrazyStone, Mango, Zen, I think, and for sure in MoGo) are really great. I don't know to which extent RAVE is still useful when you have patterns in 19x19. In 9x9, I'm sure that we have no database of patterns which replaces RAVE values, but perhaps it's because we have no database of patterns specialized for 9x9. Or perhaps big patterns in 9x9 don't work :-) Also I don't know to which extent go expertise can replace big databases of patterns; I guess that in manyFaces there's no such big database of patterns (I'm not sure of that), but much more Go expertise. Perhaps Zen has both ? MoGo has RAVE+patterns+go expertise, but the go expertise is probably smaller than in ManyFaces and Zen. In Fuego, I guess there's go expertise and rave values, but no database of patterns ? Sorry for people working on Fuego, Zen, Mango, CrazyStone, ManyFaces if I have made mistakes about their programs :-) Best regards, Olivier Gelly and Silver (Combining Online and Offline Knowledge in UCT, section 6) give this formula for the weight given to RAVE values (as opposed to the direct MC values): sqrt(k / (3*n(s) + k)) Here, k is a constant and n(s) is the number of playouts through state s. Clearly, as the number of playouts increases, this approaches zero. Hembold and Parker-Wood (All-Moves-As-First Heuristics in Monte-Carlo Go) site the Gelly and Silver paper, but give a different formula! Adjusting for notation, they use: (k - n(s)) / k, or 0 if this expression is negative This also converges toward (and then sticks at) zero, but it it not the same formula. Why are they different? Does it matter? Is there an explanation anywhere for Gelly and Silver's more elaborate formula? Is there anything wrong with k / (n(s) + k)? On a related note, in a message on this list, David Silver gives a newer formula: http://computer-go.org/pipermail/computer-go/2009-May/018251.html Was this ever published? (Orego is using this newer formula, and it appears to work well.) Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] fill board not effective in Many Faces
If none, fill_board: pick a random empty point. If it is not on the 1st or 2nd line and there are no stones in 8 adjacent points, play it We repeat this several times, but this does not explain why it does not work for just a single time. The main weakness in your experimental setup is that you consider a small number of simulations per move, 10k, for which in our publication we have shown that there was no improvement - the improvement is for large numbers: 78.4% for 200 000 simulations per move. I hope it will be better now :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] fill board not effective in Many Faces
Hmm. It will take quite a while to run a few thousand games with 200K playouts, and I might need a stronger opponent, but I’m trying it now. Yes, I know it takes time :-) by the way it was already significantly efficient at 100 000 sims / move. I don't know the result for 50 000 but perhaps this is a good compromise and would already provide an improvement. I recall that in MoGo we test several locations (details http://www.lri.fr/~teytaud/eg.pdf). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
. Pebbles has a Mogo playout design, where you check for patterns only around the last move (or two). In MoGo, it's not only around the last move (at least with some probability and when there are empty spaces in the board); this is the fill board modification. (this provides a big improvement in 19x19 with big numbers of simulations, see http://www.lri.fr/~rimmel/publi/EK_explo.pdf , Fig 3 page 8 - not only quantitative improvement, but also, according to players, a qualitative improvement in the way mogo plays) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Monte-Carlo Simulation Balancing
Just to clarify: I was not saying that Mogo's policy consisted *solely* of looking for patterns around the last move. Merely that it does not look for patterns around *every* point, which other playout policies (e.g., CrazyStone, if I understand Remi's papers correctly) appear to do. The RL paper seems to require that playout design. Fine! BTW, FillBoard seems to help Pebbles, too. A few percent better on 9x9 games. No testing on larger boards. YMMV, and like everything about computer go: all predictions are guaranteed to be wrong, or your money back. For us the improvement is essential in 19x19 - I'll find that for the generality of fillboard if it helps also for you :-) the loss of diversity due to patterns is really clear in some situations, so the problem solved by fillboard is understandable, so I believe it should work also for you - but, as you say, all predictions in computer-go are almost guaranteed to be wrong :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MoGo and passing
On http://www.lri.fr/~gelly/MoGo_Download.htmhttp://www.lri.fr/%7Egelly/MoGo_Download.htm, under the FAQ section, I found the bullet point: MoGo continues playing after the game is over?: MoGo never consider a pass unless you pass first. If you think the game is over, simply pass. Is this still true? If so, how does MoGo deal with situations where the best move is to pass (e.g. seki). When passing is necessary, mogo passes. So this sentence is not exactly true; mogo can pass first in extremal cases (very rare cases, against humans). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Zero exploration?
There has been some talk here of using a zero exploration coefficient. Does this literally mean using the win ratio (with one dummy win per node) to decide paths through the MC tree? It seems that the best move could easily be eliminated by a couple of bad runs. Does this only work when using RAVE/AMAF? I can at least explain how is this exploration in MoGo. For the case with Rave/Amaf, we have 0 in front of the UCB-like term sqrt(log(...)/...). For a long time, the exploration was a linear compromise between the Amaf-winRate and the standard winRate, without other term, and in particular no optimistic term. However: - the winRates are regularized, i.e. it is for example (nbWins+K)/(nbLosses+2K), or something like that which avoids bad luck. This simple trick is, I think, central in avoiding bad luck. - since we have patterns, we added a third term; in early versions, this term was a coefficient between 0 and 1, and the linear combination between the three terms was weighted so that the sum was equal to 1 - there was still something which was an estimate of success rate, without optimism in front of uncertainty. - then, we had a real improvement by adding an optimistic exploration term, using the pattern value: +mangoPatternValue/log(nbSimulationsForThisMove+2). This decreases very slowly (logarithmically), with a small initial value - it's nearly a small systematic bias. By the way, the conditions for consistency in Astar, which is quite related to Monte-Carlo Tree Search in my humble opinion, imply optimism in the sense that the value must be overestimated. UCT/MCTS is really similar to Astar without so-called close set. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
In my humble opinion, we need a change in the algorithm. The numbers are misleading - 95% of win of MoGo on 32 nodes against MoGo on 1 node (this is a real number for 19x19) certainly means that the parallel version is stronger than the sequential version, but not much better, far less than what suggests this 95%. MCTS algorithms adapt the beginning of simulations only, and for many cases we have to deal with predictions on the end of simulations: something like if the opponent plays X, I'll reply Y. The bias on semeais is, in my humble opinion, equivalent to this fact that we learn only the beginning of the simulations (the tree part) and not the end. I don't know if the good word is to say that it's a wall or a mountain, but I think the idea is that we need something really different - perhaps heavy playouts that solve some tactical elements, or perhaps some statistical trick for modifying the playouts depending on the simulations - I'd like to solve this with supervised learning like when I reply X to move Y then I win with higher probability. It would be a nice solution, efficient beyond the game of Go. Well, as I've spent a lot of time on this idea without finding an implementation which works better than the baseline, perhaps my ideas are not very interesting :-) Regarding Moore's Law, I'd love to hear the Mogo team's perspective on this; they have probably had more opportunity to test their algorithms extensively on big-n-count computers than any of us. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] US Go Congress
Hi; What is sure is that MoGo is available. We can also let the opportunity to other programs which have had less opportunities of games against pro. We have only small progresses in 19x19. From what I saw in previous games, I guess many programs have nearly the same limit and nearly the same architecture: patterns in the tree and monte-carlo tree search are necessary for good performance, sequence-like Monte-Carlo is also mandatory. I guess (but I'm not sure) that Rave is not absolutely required. As programs improve, my humble opinion is that computational power becomes less and less efficient as now the main trouble is the systematic bias for some positions (semeais or too complicated life-and-death situations) - parallelization is not required. In 19x19, the best performance so far was a win against a pro with handicap 6, or against a top pro (9P Zhou Junxun) with handicap 7 - this is a bad piece of news for 19x19 games, as I guess it will be really very difficult to do better than that. I prefer 9x9 games for that, as I guess it's possible to do better than previous best results so far (in particular computers might win in complete games), but I know that Kim is not interested in 9x9. Best regards, Olivier Will Mogo be available? Mogo team, do you feel that Mogo has improved since the previous demonstration? Which is the strongest computer go program nowadays? Terry McIntyre terrymcint...@yahoo.com “We hang the petty thieves and appoint the great ones to public office.” -- Aesop -- *From:* David Doshay ddos...@mac.com *To:* computer-go computer-go@computer-go.org *Sent:* Tuesday, June 9, 2009 10:56:30 AM *Subject:* Re: [computer-go] US Go Congress Because of my health problems I will not be able to attend this year either, so neither of the two people who ran last year's event in Portland will be able to do it this year. Any other volunteers? It would be nice if this became a regular event again. Cheers, David On 9, Jun 2009, at 9:27 AM, Peter Drake wrote: Due to other commitments, I will NOT be attending the US Go Congress in Fairfax, Virginia, August 1-9. As a result, if there is to be any computer Go event there (e.g., computer-computer tournament, computer-professional match), someone else will have to organize it. Peter Drake http://www.lclark.edu/~drake/ http://www.lclark.edu/%7Edrake/ ___ 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/ -- = Olivier Teytaud (TAO-inria) olivier.teyt...@inria.fr Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France (one of the 56.5 % of french who did not vote for Sarkozy in 2007) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] MCTS, 19x19, hitting a wall?
But, while that may be the case, perhaps we can say that they are hitting a wall in their observable playing strength against non-MCTS players (such as humans) at higher levels. In [2] I touched upon how the nature of the game changes at higher levels, and how scaling results obtained between weaker players may not apply at those higher levels. I was talking about pure random playouts in that article, but the systematic bias Olivier mentions can lead to the same problems as no bias at all... I completly agree with this. It's like a Monte-Carlo evaluation (in a non-MCTS framework). Parallelization reduces the variance, but not the bias. You still get improvements, and you can believe that parallelization brings a lot, but in fact it does not. We spent a lot of energy trying to remove bias by various statistical tricks (combining MCTS with tactical search or with reweighting according to macroscopie informations on simulations such as the size of captures) but nothing works yet in the case of Go (for some other games we have positive results, but as I'm not the main author I won't give too much informations on this - I hope we'll find a similar solution for Go, but for the moment in spite of many trials it does not work and I'm not far of being tired of trying plenty of different implementations of these ideas :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go + code + environment
Perhaps I'm mistaken in my reading, but isn't Mogo a clusterized and highly tuned version of gnugo? Things like that made me want to make this post. As I find the Go programming community more open to sharing ideas and code than my chess world counter part. Will gladly stand corrected w/ Mogo if i'm wrong. Though curious to hear everyones input. As already pointed out by other people, MoGo is absolutely not a development based on Gnugo's code. Perhaps it should, as Gnugo is probably more clean :-) Some related points: - MoGo's early developments were based on CrazyStone. Without looking at the code of CrazyStone, but with many help from Rémi Coulom. The main initial difference, I guess, was the patterns introduced by Yizao Wang, and then the RAVE values by Sylvain and David. - Some inclusion of other software inside MoGo was tested, but none of these inclusions was kept, neither used in official games - these inclusions were never beneficial. The only exception is the use of code from Mango (done by me and the author of Mango together), but Mango was never participating the same competition as MoGo. - Even if nobody has included code from Gnugo, I guess that all of us have used Gnugo intensively for testing and tuning. From this point of view, the authors of Gnugo are indirectly the authors of MoGo, and probably also CrazyStone, ManyFaces, Zen, etc. I guess the binaries of MoGo have been used a lot also, even if only early versions are freely available. I guess binaries are much more used that codes and therefore MoGo has been used as much as Gnugo even if the source code is only given on request and not as open source. - Also, we used the Tsumego provided by Yamato and others on this mailing list, as well as e.g. the comments by David Fotland around nakade. The scaling study by Don and others was also helpful. The Rave values were influenced by early papers on Amaf values. I've forgotten many helpful hints from many people - the fact that it's so long to list all contributors probably means that computer-go is friendly and collaborative :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Match: MoGo vs Taranu on 9x9
http://www.gokgs.com/gameArchives.jsp?user=mogoRennes Taranu won the first three games and lost the final one. So, the score was 3-1 for him. Thanks for the report. As far as I know (not completly sure) it's the first win (in 9x9 game komi 7.5) of a computer against a human as black. I point this out in order to have at least a positive conclusion , as essentially the result is that Catalin won 3 games out of 4 :-) In game 1 mogo lost in the very early moves if I understood well the comments from strong players; in games 2 and 3 mogo lost quite late with some stupid very fast moves - this suggests that perhaps we should save up time in the beginning. Well, it's a conclusion based on a sample of 2 games :-) (by the way we corrected a bug in the time management betweent the 3rd and the 4th game... one day mogo will be bug free :-) ) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Match: MoGo vs Taranu on 9x9
Did you verify that Mogo would have played those stupid fast moves correctly without having to add too much time? No, I've not checked. But the moves were really fast and the comments of humans were in that direction. I agree that we must have more (much more) time for early move. But for the three first games it was really very, very, very slow in the beginning and very, very, very fast in the end - a stupid bug :-/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo on supercomputer
When Mogo runs on the supercomputer with long-ish time limits, how big does the search tree get? Plotting the depth/number of nodes as a function of the thinking time might be a good idea... No idea :-( I just remember that changing the number of visits before adding a new node in the tree changes the length of the simulated variations without having a strong impact on the level. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Justification for c==0
Theorem: In a finite game tree with no cycles, with binary rewards, the UCT algorithm with c==0 converges (in the absence of computational limitations) to the game theoretic optimal policy. This is also tree with RAVE instead of UCT, if you ensure that RAVE values are never below some positive constant (this was posted in discussions between Sylvain and me a long time ago in this mailing list, but never published I guess). By the way: - I guess there are several codes in which c=0, or c0 but with no significant improvement over c=0. If you want to publish scientific papers, claim that c0; UCT is so widely accepted that your paper is more likely to be accepted with c0 :-) - even withou parallelization, mogo is better with constant 0. - on the other hand, and in particular for stochastic games with one player (which is industrially quite relevant), I find UCT quite good. Also, progressive widening as published by Rémi is efficient in this one-player setting (but with different constants). I'm definitely convinced that UCT provides a very great improvement, e.g. in front of Bellman's dynamic programming, in many cases. - Another point is that with the pattern-based exploration term (not UCT-like), we have an exploration term; but not at all UCT-like (something like Heuristic(move)/log(2+numberOfSimulations) ). A somewhat philosophical point related to the fact that UCT is not so efficient for Go, is that clear sound algorithms are probably not the main elements in Go; plenty of parameters (the coefficients of patterns, the choice of Monte-Carlo player) are necessary and do not follow short and sound rules. If you want to publish scientific papers, do not say that - you should preferably hide the details, and show only a small and well chosen part of your results, so that people can believe that a small sound idea is the explanation for the fact that the program works. But, in the particular case of Go, and somewhat disappointingly, I'm not sure that reality is like that. I prefer nonlinear optimization or applications of UCT in one-player games or applications for this point of view - there, sound ideas usually work and outperform dirty tricks :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Any newer version of Mogo beyond version 3...
Hi. For your email about newer versions of MoGo; technically, the main differences with version 3 are: - use of MPI (useless unless you have a cluster); - opening books in 9x9; - more go-expertise - better exploration term (not UCT-like) - much stronger handling of patterns in the tree part - better handling of Nakade - a specific bandit for the root of the tree; - better MC player (more randomization) and I am sorry for all the improvements I have forgotten The new version has the drawback that I don't know if it works under windows. Also the command line is not exactly the same (but almost). I think I also published a newer version on this mailing list a long time ago for 64 bits. Please send a private email if you want a Linux binary. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 19x19: MoGo (handicap 7) vs Jun-Xun Zhou (9p)
The game can be found here http://www.lri.fr/~teytaud/H7.sgf or on KGS, for user mogo. I'm posting these results, but I must precise that I was not operating myself - Arpad Rimmel did operate, and Guillaume Chaslot was also very involved in the preparation. MoGo was running on Huygens (in Amsterdam) as usual. The lag is probably conservatively estimated (it's better to be too much conservative than not enough conservative :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Well, empirically, when I set the exploration component to zero it starts to play a lot worse. Like I wrote: the winning percentage drops to 24% vs. the same program with the exploration component, which is a huge difference. So if you have a different experience, you must have something else that overcomes this hurdle that's not part of a simple MCTS-RAVE implementation. I'd be very interested to learn what that is. Sylvain didn't take the bait ;-) Here, we have a non-zero initialization of the number of wins, of the numbere of simulations, of the number of Rave-wins, of the number of Rave-losses. We have then a 0 constant for exploration, but also an exploratory term which is very different, and for which I am not the main author - therefore I let the main author give an explanation if he wants to :-) I point out that even before this exploratory term, the best UCB-like exploration-constant was 0 - as soon as the initializations of numbers of wins, of losses, of Rave-wins, of Rave-losses are heuristic values. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
I'd like to make sure I understand what you mean exactly. You use some heuristics to intialize all the moves (or maybe some of the moves) with a certain win-loss and rave-win-loss ratios? Not only ratios, but also numbers of simulations. Thanks to patterns, expert rules. To a certain extent I suppose these could come from the reading of the previous move? I think I slowly start to make sense of things... We have (almost) no warm start from the values of previous moves. This should be improved, as very clearly there is some time lost here (e.g. patterns should not be checked from scratch). A+ Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Of course you can do put much more clever prior if you are a player and know the subtleties of the game. E.g. patterns extracted from databases - but it's not enough, carefully tune the coefficients for empty triangles (important!) and various other importants patterns/rules (don't just keep the empirical probabilities from datasets as coefficients). I'm afraid the coefficients are very implementation-dependent unless the bandit and the random player are specified with a lot of details. You can put an exploration term, but the cases where it is needed are rare. I did a lot of experiments on that, and even at long thinking time, no exploration term was always better (statistically). Well, now mogo has an exploration term - but not at all UCB-like. As said previously, I'm not the main author of this modification and I'll not explain it myself. Also, for the main node (the root), the bandit in mogo is different from the bandit elsewhere in the tree. More diversification is useful. But it's not a very important improvement, a few percents. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] How to properly implement RAVE?
Well, now mogo has an exploration term - but not at all UCB-like. I was talking about times where I was still there ... ages ago :) Good old times :-) you've been helpful several times even from far away :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Black/White winning rates with random playout?
I don't know the answer, but it's not too surprising - with random play the komi should be something like 2 or 3, so white with 7.5 komi has a pretty good advantage. This advantage disappears (or almost disappears) if the games are well played, but in your case they are not. I think that the advantage increases when the games are well played, and I believe some people with other programs have the same results. In particular with good openings, white becomes very strong. Also, high level human players also have this feeling (I think). Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] 9x9 MoGo vs human
In the computer-Go event of Clermont-Ferrand, MoGo played four 9x9 games, plus blitz games, against Motoki Noguchi (chinese rules, komi 7.5); the result is a draw - the games are presented and discussed in http://www.lri.fr/~teytaud/crClermont/cr.pdf Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 MoGo vs human
Thank you for writing this very interesting report. But it's a 40Mb pdf file, my Internet Explorer can't handle it at all, and my FireFox only with difficulty. A more accessible version, perhaps without the high-resolution pictures, might reach more readers. Sorry for that :-) http://www.lri.fr/~teytaud/crClermont/cr.pdf is much easier to download now (10 times smaller). Thanks to Terry for comments. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo MCTS is not UCT ?
I think it's now well known that Mogo doesn't use UCT. I realize that i have no idea at all what Mogo do use for it's MCTS. A complicated formula mixing (i) patterns (ii) rules (iii) rave values (iv) online statistics Also we have a little learning (i.e. late parts of simulations are evolved based on online statistics and not only the early parts). I really wonder if there was an article describing the new MCTS of mogo somewhere that i missed. How is it better than UCT ? http://www.lri.fr/~teytaud/eg.pdf contains most of the information (many other things have been tried and kept as they provided small improvements, but essentially the ideas are in this version) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
Is there any theoretical reasons for the Mogo Opening being built out of self play, rather than by spending time increasing the number of simulations at the root, and after a time, keeping what seems to be the best ? There are practical reasons: our approach can be used with humans or other programs as opponent as well; we can benefit from games launched for other purposes than opening-building; and we can easily parallelize the algorithm on grids. No other reason, at least for me - but these reasons are enough I guess. The alternate approach is nice, but is difficult to use for tenths of years of CPU - whereas using preemptable mode in grids, we can have access to a huge computational power. From a more technical point of view, I think that the idea of using results of games of strong versions of mogo is better for avoiding biases in the MC. But it's only a conjecture. Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Mogo Opening, Building Strategy ?
By conjecture, i suppose you mean that no experiments yet has been ran as to assess this hypothesis ? Yes. The other reasons were sufficient :-) I think Sylvain (and maybe just everyone else) has tried at some point to use a UCT decision bot, as a way to get the simulation done. Then using those high level simulations in an other UCT decision tree (or AMAF, or FirstMove wining stats) From what i recall, the results were disappointing. At least, it has been clearly established that replacing the random player by a stronger player does not imply the Monte-Carlo program built on top of the random player becomes stronger (even with fixed number of simulations) But, it is also clearly established that the building of the opening book by self-play clearly works, whereas it is roughly the same idea. I guess the reason is the difference of strength of the player - a MCTS (Monte-Carlo Tree Search - I don't write UCT here as it is not UCT in mogo) built on top of a perfect player should be a perfect player (this is formally obvious). So perhaps for huge computational power, this approach (building MCTS on top of MCTS) is consistent. For example, it is well known that Mogo-style decision (or crazy stone) lead to very poor understanding of seki (and/or semeai ?) Would'nt the use of high level game as simulation get to better understanding of those really nasty situations ? I hope so, at least for 9x9 and with really huge computational power. (by the way I'm afraid we have to patch semeai manually) Is it that that it is known it would consume to much time and resources ? I think it is really difficult to do that - you have to dump your results unless you have a machine for a huge time without any reboot, also if you want to have a huge computational effort you have to parallelize it - I think this is really hard. But perhaps trying mogo against mogo built on top of a mogo with e.g. 1s/move would be fine... this is easy to organize. Well, it requires some time, and time is always expensive :-) Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Skynet likes Go
It's only a matter of time before MoGo becomes self-aware and destroys us all. ;) By the way, during the IAGO 2008 (meeting between mogo and Catalin Taranu), a very angry guy came during the preliminary games against amateur players and shouted that we were mixing war and art, and plenty of other strange opinions about computers and games. I was very afraid of a big trouble because he came back during the game, but he just sat down and watched the game :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Re: Opportunity to promote ...
I think it was the surprisingly useful combination of UCT with Monte-Carlo that got the attention of the 'old school' Go programmers. I would say Monte-Carlo + Tree Search rather than Monte-Carlo + UCT. You can have a very strong program without UCT. You can't without the incremental tree + the Monte-Carlo search. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] light vs. heavy playouts in Many Faces
It's also possible that when David says lite playouts he means something heavier than what we think.I doubt even Mogo's heavy playout resembles strong play but is simply tuned with some knowledge that can be implemented in reasonable time. Our heaviest playouts are slower but not not much slower (some percents slower only I guess). I don't know if our heavier playouts are stronger (as a standalone player) than our light ones (we did not check that).. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Go with modified scores
You have to distinguish several scenarii when maximizing the playing strength/value of your Go program: (a) auto-play (or play between different versions of your prog) (a') play against other computer programs (b) play against humans (c) program as tool for human analysis of Go positions or of whole games (d) acceptance by humans By the way, there has been a game won by mogo against a high-level player in which, sure of winning by at least 0.5, mogo has given several points to his opponent. The human player was not offended, as he could of course understand that we are not responsible for this choice of mogo, but he pointed out that this is done in human games only - in a discrete manner, when you just want to win by a small amount, by politeness; in that case you do it in a discete manner, and it's fine; - in a very obvious way, when you want to point out that the opponent should definitely resign now. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations again to David Fotland !
My congratulations also to David :-) and good luck for both MoGo and Leela for the silver medal in 9x9 :-) Olivier Many Faces of Go has won also the 19x19 competition in the 13th International Computer Games Championships, with a 100 % score. The silver medal goes to MoGo (only loss against MFoG), Leela achieves Bronze (only two losses, against MFoG and MoGo). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Bad effect when tree node limit reached
Hi; the node limit is a hard limit on the number of nodes ? if yes, when you reach this limit, what do you do - you remove some nodes with small number of simulations ? Olivier My engine is basic UCT+MC. I've been letting it ponder on small empty boards with a certain komi to see if it begins to converge to the correct position value. It does as long as the tree is allowed to grow. But as soon as the tree reaches its node limit (with simulations continuing), the position value begins to go back toward 0.5 (where 0 represents a white win and 1 represents a black win). I would have expected the convergence to the correct value to continue at a slower rate or maybe just stay the same. Is this a bug or can this effect be explained? ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- = Olivier Teytaud (TAO-inria) [EMAIL PROTECTED] Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to David Fotland!
Mogo was allowed to use 800 cores, not more, and only for games against humans. We have no acces to so many cores for computer-computer games (if there were only three teams involved, we could :-) ). For some games Huygens was unaivalable at all, and mogo played with much weaker hardware (some quad-cores, however, it is not so bad :-) ). Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Congratulations to David Fotland!
For the use of fast networks: yes, fast networks improve the results, in particular for 9x9, in my humble opinion - however, you have already a good speed-up without that, in particular for 19x19, and in particular if you have multiple cores per node so that one core can take care of communications whereas the other nodes compute simulations. But for grids (instead of clusters), the communication will become much much bigger - I'd like to study that carefully one day, I have no clear idea of what is possible. A trouble is that on grids (at least the ones I've seen) there are often faults. We'll have to be fault tolerant I guess. I point out that it has been said that very long delays between communications are not a trouble - this is not the case in my experiments, but perhaps this is implementation dependent, or perhaps I am wrong :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 2008 World 9x9 Computer Go Championship in Taiwan
Dear all, the results of the 9x9 computer-go event in Taiwan (including a 9x9 competition and games between humans and computers) can be seen at http://go.nutn.edu.tw/eng/main_eng.htm (see news) These games were organized by the National University of Tainan and the Chang Jung Christian University (both in Taiwan). For convenience, I report the results below - this should be consistent with the news above, forgive me in case of errors. The very nice point in this event is that there has been a large number of games with high-level humans. Also, a nice point for us is that mogo won the 9x9 competition :-) Essentially, mogo has usually won against 6D with 5 stones, lost against 6D with 4 stones, and won against 5D with 4 stones, with something between 320 and 480 cores of Huygens (amateur dans). MoGo was using a varying number of cores, from 320 to 800, and was consistently more than 1D for arithmetics like humanLevel - handicap (choose your favorite formula :-) ). On the other hand, mogo has lost in a 19x19 game with H7 against a 9P player; by the way, Kim already won against MoGo in the same H7 configuration but with time settings more favorable to MoGo (longer time settings). By the way, that was my first trip to Taiwan, a colleague in my lab was in Taiwan in the same time, and we both consider that the Taiwanese tradition of hospitality is incredibly impressive :-) Best regards, Olivier == Two events at the intersection of computer-science and the game of Go were organized by the National University of Tainan (Taiwan) and Chang Jung Christian University (Taiwan): * a competition between machines (won by MoGo, youpi tralala) * some games against humans. On September 27, MOGO played with one 9-Dan professional GO player and two 6-Dan amateur GO players and the detailed results are below. (a)1st GO player basic information: He is Mr. Zhou Junxun (9-Dan professional, about 30 years old, won the LG-Cups 2007). MOGO lost three games (i)9x9 (ii)9x9 (iii)19x19 with 7 handicap stones. Note: The 19x19 game was competed through KGS platform with 800 cpus. (b)2nd GO player basic information: He is Mr. Chang (6-Dan amateur, about 55 years old). MOGO won the 19x19 game with 5 stones. Note: This game was competed through KGS platform with 480cpus. (c)3rd GO player basic information: He is Prof. Tsai (6-Dan amateur, about 50 years old). MOGO won the 19x19 game with 5 handicap stones. Note: This game was competed through KGS platform with 480cpus. On September 26, the championship (computer vs computer): MoGo won the computer-tournament with 5 wins and no defeat: Pos.ProgramWinsSOSSoDOS 1MoGo10France 2Go Intellect61618USA 3*Jimmy61612Taiwan 4*Erica61612Taiwan 5Fudo Go6166 Japan 6CPS610 Taiwan 7GoStar420China 8GoKing418 Taiwan 9HappyGo2 Taiwan 10ChangJung10 Taiwan Note that SOS and SoDOS are given only where needed to break ties. On September 25, MOGO played with one 5-Dan amateur GO player and one 6-Dan amateur GO players and the detailed game is below. (a)1st GO player basic information: he is retired Prof. Dong (5-Dan amateur, about 70 years old). MOGO won three games (i)19x19 with 4 handicap stones(ii)19x19 with 4 handicap stones (iii)19x19 with 4 handicap stones. Note: These three game were competed through R900 machine with 16cores. (b)2nd GO player basic information: he is a GO teacher, Mr. Luo (6-Dan amateur, about 50 years old). MOGO lost three games (i)9x9 (ii)9x9 (iii)19x19 with 4 handicap stones. Note: These three game were competed through KGS platform with 320cpus. On September 24, MOGO played with a retired Prof. Dong (5-Dan amateur, about 70 years old). MOGO won three games (i)19x19 with 6 handicap stones(ii)19x19 with 4 handicape stones (iii)19x19 with 4 handicape stones. Note: These three game were competed through R900 machine with 16cpus. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
- There had been a TV program of professional 9x9 Go for years (some member of this list have the records of the games played in this program). Takemiya 9p and Yuki 9p were the strongest. I'm afraid the answer is no, but: are these records free and available somewhere ? Thanks for your interesting informations around Go and 9x9 Go :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Yes. I use Sylvain's fpu and decrease it a little before starting a simulation, say, fpu *= 0.99. This is very simple and fast. Ok. Perhaps I'm wrong (I might misunderstand your solution and I might be wrong whenever I've understood :-) ); but - I think that this does not avoid redundancies in the tree, if I understand well. - also, even in a final node in a tree, it does not avoid redundancies for moves which have already been simulated. - finally, in a final node in a tree and for moves which have not yet been simulated, it only avoid redundancies if 0.99 is sufficiently small. Avoiding redundancies is very important in SMP parallelization. The limited speed-up of MPI parallelization in 9x9 is also probably due to redundancies, but for that we have no good solution - whereas in 19x19 (or even 13x13), the speed-up of the MPI parallelization is great (both in our results and other published papers), in 9x9 it is limited. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
Although I'm parallelizing in not SMP systems but a cluster of loosely coupled (small) computers connected through moderate speed networks using broadcasting positions, this may not change the vlaue of avoiding redundancies. I'll study more when implementing pre-knowledge or some. Thanks. Do you have the winning rate of your best parallel algorithm against the sequential version in 9x9 Go in such a setting without shared memory ? We stay below 80% for this form of parallelization (but this speed-up can be cumulated with SMP speed-up), whenever we use fast networks (infiniband). In 19x19, it's much better, but the MPI parallelization of 9x9 Go is challenging. Best regards, Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Goal-directedness of Monte-Carlo
MC is playing most goal-directed (zielgerichtet in German) when the position is balanced or when the side of MC is slightly behind. However, when MC is clearly ahead or clearly behind it is playing rather lazy. At some point we were investigating that here, but only on small sets of games (we have essentially games with no handicap between versions which are close to each other - for example, the conclusion according to which white has the advantage when using komi 7.5 in 9x9 is more documented than questions around handicap). I find the following elements interesting: 1) MoGo was seemingly weaker in handicap games (was because we did not have a look at that recently - perhaps it's always true). This was nearly established by comparing the success rate against people of level X with handicap n and people of level Y with handicap p. Of course, this was not very scientific - just an element. 2) MoGo has become stronger (and the difference is huge for long time settings) with more randomization; I guess this is because with more randomization, you are less likely to have a constant result as you increase the number of simulations. With more randomization you are more likely to see that the x50 % of probability of loosing becomes yx50% with a given move than if you have a too much deterministic simulations such that y=x because the few simulations in which the move introduces a difference occur with very very very samll probability in your too deterministic simulations. By the way, this reasonning is also intuitively satisfactory for explaining that in the MC simulations uniformity on reasonnable moves is often better than non-uniform probabilities - with uniform probabilities, the less likely event is more likely than with non-uniform probabilities. This reasonning is not mathematically sound, of course, it's not a theorem, but intuitively this looks reasonnable (at least for me :-) ). This strong improvement with randomization might be also an improvement in the case of handicap games, but I've not checked that. 3) By the way, we have positive results (small improvements, but improvements) by using different Monte-Carlo simulations for different cores. This is consistent with 2) above - by performing N simulations of type 1 and M simulations of type 2, you cover more markov models than with one Markov model - you can cover different scenarios. I'd like to extend this idea - for the moment we have only two Monte-Carlo simulators and the improvement is small, I hope we can define 3,4,5,etc Monte-Carlo simulators and have a strong improvement. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 to 19x19 scaling strangeness
I made a change over the weekend, which looks like it makes 9x9 150 ELO weaker and 19x19 over 200 ELO stronger. We have plenty of size-dependent parameters and plenty of if (boardsize==19) in MoGo for things like that :-) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] 9x9 to 19x19 scaling strangeness
Some main differences in mogo between 9x9 and 19x19: - we have no pattern database for the tree in 9x9 (because we have not done it yet, but perhaps it would be efficient), and go-expertise (rules used for introducing a bias in the tree) is nearly useless in 9x9. - I have read that Rave values are supposed to be especially efficient in 19x19, but I guess it is essentially efficient in 19x19 when you have no go-expertise - in my humble opinion, if you have patterns or go-expertise, it is in 9x9 that rave values are most efficient (I'm not sure of that, it's just a feeling when comparing our results) - the positive effect of randomization (if any) is much smaller in 9x9 - the thresholds for self-atari are different - the relative weight of amaf-values and standard values is different - the formulas for the bias depending on the distance to the last move are different - the formulas for the time per move are also different (more complicated in 19x19, it's not only parameters) I probably forget plenty of differences :-) Can you put crazystone back on 19x19 so I can see if it is just a fluke against fuego? I added locality to the light playouts - play near last or second to last move, and some code to handle long ladders in playouts. I don't think this is anything unusual. Both should help 19x19, but I don't know why 9x9 would be damaged. I also changed code around playing self atari in seki. Perhaps there is bug, since seki is more important in 9x9. The biggest problem that I have with monte carlo is the amount of testing. I made four or five changes and I'm testing them together now. To see the effect of each change independently would take a couple of weeks of testing, since it takes several days on 19x19 to get an accurate rating. Regards, David -Original Message- From: [EMAIL PROTECTED] [mailto:computer-go- [EMAIL PROTECTED] On Behalf Of Rémi Coulom Sent: Tuesday, September 09, 2008 9:20 AM To: computer-go Subject: Re: [computer-go] 9x9 to 19x19 scaling strangeness David Fotland wrote: I made a change over the weekend, which looks like it makes 9x9 150 ELO weaker and 19x19 over 200 ELO stronger. Very strange. David ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ Now you must tell us what the change was :-) Rémi ___ 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/ -- = Olivier Teytaud (TAO-inria) [EMAIL PROTECTED] Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
The bright side here is that 9x9 is not really important but just a test bed. If it works for 19x19, that's good. People moderately intested in Go could also claim that both 9x9 and 19x19 are just testbeds for power plant management :-) In my humble opinion, both are intesting, both as testbeds (9x9 is a good testbed for parallelization because it's more difficult) and as real targets (as there are players for both). But, I guess it's a controversial political issue :-) Olivier ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Lockless hash table and other parallel search ideas
By my recent experiments, 8~9 * (threads - 1) ELO is lost. This matches my earlier result well. Do you have tricks for avoiding redundancies between simulations ? I suggest simple tricks like do not go to node X if there is a thread currently in node X (simply by setting the score of the moves leading to node X to zero until you get out of the node). ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yet a mogo vs human game
Yes, and then 19x19 with handicap. On Aug 25, 2008, at 10:47 PM, Olivier Teytaud wrote: Just for information, mogo will play in a few minutes (on Kgs / computer-go) some games against high level humans. MogoTitan is playing 9x9 against nutngo ? Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- = Olivier Teytaud (TAO-inria) [EMAIL PROTECTED] Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] yet a mogo vs human game
More informations later, but we can already say that: - the opponent is 6D - MoGo was using 5% of Huygens (instead of 25% against Kim); - there were some software improvements - MoGo won 2 out of 3 games in 9x9 (even games) - MoGo won with handicap 5 in 19x19 against the 6D player - games can be found on KGS, see MoGoTiTan, games against nutngo - we will have next month a stronger hardware and a stronger software (some improvements have not been included because we did not find time for checking everything on Huygens before the games of this morning) We thank both the organizers and the player :-) Best regards, Olivier for the mogo-team Yes, and then 19x19 with handicap. On Aug 25, 2008, at 10:47 PM, Olivier Teytaud wrote: Just for information, mogo will play in a few minutes (on Kgs / computer-go) some games against high level humans. MogoTitan is playing 9x9 against nutngo ? Christoph ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ -- = Olivier Teytaud (TAO-inria) [EMAIL PROTECTED] Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France -- = Olivier Teytaud (TAO-inria) [EMAIL PROTECTED] Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] yet a mogo vs human game
Dear all, Just for information, mogo will play in a few minutes (on Kgs / computer-go) some games against high level humans. However, we point out that these runs will be on moderately big hardware - we will come back at the end of september for very big hardware (hopefully bigger than against Kim :-) ). Best regards, Olivier -- = Olivier Teytaud (TAO-inria) [EMAIL PROTECTED] Tel (33)169154231 / Fax (33)169156586 Equipe TAO (Inria-Futurs), LRI, UMR 8623(CNRS - Universite Paris-Sud), bat 490 Universite Paris-Sud 91405 Orsay Cedex France ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
