60 ms·

Google achieves AI 'breakthrough' by beating Go champion

• Inufu 11y ago
  Our paper: http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html http://www.nature.com/nature/journal/v529/n7587/full/nature1... Video from Nature: https://www.youtube.com/watch?v=g-dKXOlsf98&feature=youtu.be https://www.youtube.com/watch?v=g-dKXOlsf98&feature=youtu.be Video from us at DeepMind: https://www.youtube.com/watch?v=SUbqykXVx0A https://www.youtube.com/watch?v=SUbqykXVx0A edit: For those saying it's still a long way to beat the strongest player - we are playing Lee Sedol, probably the strongest Go player, in March: http://deepmind.com/alpha-go.html http://deepmind.com/alpha-go.html. That site also has a link to the paper, scroll down to "Read about AlphaGo here". If you want to view the sgfs in a browser, they are in my blog: http://www.furidamu.org/blog/2016/01/26/mastering-the-game-of-go-with-deep-neural-networks-and-tree-search/ http://www.furidamu.org/blog/2016/01/26/mastering-the-game-o...
  • radicality 11y ago
    Can I read the paper somewhere without a Nature subscription?
    • jimfleming 11y ago
      DeepMind/Google has a hosted copy: https://storage.googleapis.com/deepmind-data/assets/papers/deepmind-mastering-go.pdf https://storage.googleapis.com/deepmind-data/assets/papers/d...
  • deleted 11y ago
    [deleted]
  • deleted 11y ago
    [deleted]
  • fitzwatermellow 11y ago
    Official Google Blog post also has some background info: AlphaGo: using machine learning to master the ancient game of Go https://googleblog.blogspot.com/2016/01/alphago-machine-learning-game-go.html https://googleblog.blogspot.com/2016/01/alphago-machine-lear... Interesting that DeepMind was using Google Cloud for compute. I imagine that the MCTS expansion can become massive. Any chance DeepMind may publish some of the internals about how many instances were used, how computation was distributed, any packages or frameworks used, etc. And congrats on achieving this impressive AI milestone!
    • cfcef 11y ago
      > Any chance DeepMind may publish some of the internals about how many instances were used, how computation was distributed The computation requirements for training and running are given in the paper in both the body and the appendix details.
      • fitzwatermellow 11y ago
        Thanks, cfcef! Implementation details are in the "Methods" section. Have started experimenting with small GPU ML cloud jobs and the costs do add up. Wanted to get a sense what a large job looked like and indeed, AlphaGo is gargantuan. 50 GPUs approx train time one month for the policy/value network. So, a Google R&D size budget would be a prerequisite ;)
  • tetraodonpuffer 11y ago
    was it easy to convince the players to have a match with AlphaGo? or was there some reluctance especially now when losing is becoming more of a possibility at even strength?
    • eru 11y ago
      I don't know about Go professionals, but this might be the last time a human can win against computers. (Or the first time computers will win all the time.) It's a strange honour in either case.
  • ewanmcteagle 11y ago
    When can we hope to see some form that will allow the public to play against this even if it is pay to play for each game or a weaker PC version? I hope the system does not end up being put away like Deep Blue was. Also, what kind of hardware results in this level of play and how is hardware correlated with strength here?
    • rpearl 11y ago
      Deep Blue was only innovative in that it was specialized hardware for this type of search. The algorithms it used were well-established, and as there was no way to play it as a piece of hardware without great expense, there wasn't really a reason to keep it around. Chess engines you can run today, for free, on your own laptop, are far and away better than Deep Blue (and any human), and I believe still don't reach Deep Blue's raw speed.
      • karussell 11y ago
        I'm curious: is there a Chess league for software? And if yes, how far are they already better (in ELOs) than humans if run on commodity server hardware?
        • tetraodonpuffer 11y ago
          I think that would be https://icga.leidenuniv.nl/ https://icga.leidenuniv.nl/ I can't find the claimed ELO for Jonny (current champ) but Junior (previous champ) is listed at 3200+, Magnus' top rating, the highest ELO rating ever, is 2882 for reference
          • bluecalm 11y ago
            This is not a serious competiton. For serious stuff, see for example: 1)http://tcec.chessdom.com/ http://tcec.chessdom.com/ 2)http://www.computerchess.org.uk/ccrl/4040/ http://www.computerchess.org.uk/ccrl/4040/ There is a lot of politics in chess programming but the bottom line is that Komodo is currently the strongest program followed by Stockfish (which is distributed under GPL).
  • sawwit 11y ago
    Great achievement. To summarize, I believe what they do is roughly this: First, they take a large collection of Go moves from expert players and learn a mapping from position to moves (a policy) using a convolutional neural network that simply takes the 19 x 19 board as input. Then they refine a copy of this mapping using reinforcement learning by letting the program play against other instances of the same program: For that they additionally train a mapping from the position to a probability of how how likely it will result in winning the game (the value of that state). With these two networks they navigate through state-space: First they produce a couple of learned expert moves given the current state of the board with the first neural network. Then they check the values of these moves and branch out over the best ones (among other heuristics). When some termination criterion is met, they pick the first move of the best branch and then it's the other player's turn.
    • sillysaurus3 11y ago
      they also train a mapping from the board state to a probability of how how likely it is a particular move will result in winning the game (the value of a particular move). How is this calculated? When some termination criterion is met Were these criterion learned automatically, or coded/tweaked manually?
      • sawwit 11y ago
        1. The value network is trained with gradient descent to minimize the difference between predicted outcome of a certain board position and the final outcome of the game. Actually they use the refined policy network for this training; but the original policy turns out to perform better during simulation (they conjecture it is because it contains more creative moves which are kind of averaged out in the refined one). I'm wondering why the value network can be better trained with the refined policy network. 2. They just run a certain number of simulations, i.e. they compute n different branches all the way to the end of the game with various heuristics.
    • someotheridiot 11y ago
      If their learning material is based on expert human games, how can it ever get better than that?
  • Florin_Andrei 11y ago
    Wow, this is stunning. You guys beat a professional 2-dan player. That happened a lot sooner than expected. There's some kind of exponential evolution going on with AI these days. Is AlphaGo being made available to the public? I'm a mediocre player, but I'd like to try a few games against it. Current synthetic players don't quite play the same as humans do, and it's a bit jarring. I wonder if the Google AI is more human-like in its style. Anyway, here's the news from the p.o.v. of AGA: http://www.usgo.org/news/2016/01/alphago-beats-pro-5-0-in-major-ai-advance/ http://www.usgo.org/news/2016/01/alphago-beats-pro-5-0-in-ma...
  • dorianm 11y ago
    Direct link to the paper: https://storage.googleapis.com/deepmind-data/assets/papers/deepmind-mastering-go.pdf https://storage.googleapis.com/deepmind-data/assets/papers/d...
  • cfcef 11y ago
    When in March is the match? Will it be broadcast live?
    • Inufu 11y ago
      There will be a live broadcast on our YouTube channel, I think the date will be announced soon.
      • mjmaher 11y ago
        What is your YouTube channel?
        • fastturtle 11y ago
          https://www.youtube.com/channel/UCP7jMXSY2xbc3KCAE0MHQ-A https://www.youtube.com/channel/UCP7jMXSY2xbc3KCAE0MHQ-A
  • jermaink 11y ago
    Shannon numbers: Chess: ~ 10^123. Go 19x19: ~ 10^360. Source: https://en.wikipedia.org/wiki/Game_complexity https://en.wikipedia.org/wiki/Game_complexity As a non-expert, may I ask (as the term does not appear in the paper): How valuable is the Shannon number in order to evaluate "complexity" in your context?
    • shas3 11y ago
      Since both numbers are out of the realm of brute-forcing, the bigger achievement is because of the more fluid and strategic nature of Go compared to chess. Chess is more rigid than Go, and playing Go employs more 'human' intelligence than chess. Quoting from the OP paper: "During the match against Fan Hui, AlphaGo evaluated thousands of times fewer positions than Deep Blue did in its chess match against Kasparov; compensating by selecting those positions more intelligently, using the policy network, and evaluating them more precisely, using the value network—an approach that is perhaps closer to how humans play. Furthermore, while Deep Blue relied on a handcrafted evaluation function, the neural networks of AlphaGo are trained directly from gameplay purely through general-purpose supervised and reinforcement learning methods." "Go is exemplary in many ways of the difficulties faced by artificial intelligence: a challenging decision-making task, an intractable search space, and an optimal solution so complex it appears infeasible to directly approximate using a policy or value function. The previous major breakthrough in computer Go, the introduction of MCTS, led to corresponding advances in many other domains; for example, general game-playing, classical planning, partially observed planning, scheduling, and constraint satisfaction. By combining tree search with policy and value networks, AlphaGo has finally reached a professional level in Go, providing hope that human-level performance can now be achieved in other seemingly intractable artificial intelligence domains."
      • mikekchar 11y ago
        I will admit to not following AI at all for about 20 years, so perhaps this is old hat now, but having separate policy networks and value networks is quite ingenious. I wonder how successful this would be at natural language generation. It reminds me of Krashen's theories of language acquisition where there is a "monitor" that gives you fuzzy matches on whether your sentences are correct or not. One of these days I'll have to read their paper.
  • tzs 11y ago
    This is a great advancement, and will be even more so if you can beat Lee Sedol. There are two interesting areas in computer game playing that I have not seem much research on. I'm curious if your group or anyone you know have looked into either of these. 1. How to play well at a level below full strength. In chess, for instance, it is no fun for most humans to play Stockfish or Komodo (the two strongest chess programs), because those programs will completely stomp them. It is most fun for a human to play someone around their own level. Most chess programs intended for playing (as opposed to just for analysis) let you set what level you want to play, but the results feel unnatural. What I mean by unnatural is that when a human who is around, say, a 1800 USCF rating asks a program to play at such a level, what typically happens is that the program plays most moves as if it were a super-GM, with a few terrible moves tossed in. A real 1800 will be more steady. He won't make any super-GM moves, but also won't make a lot of terrible moves. 2. How to explain to humans why a move is good. When I have Stockfish analyze a chess game, it can tell me that one move is better than another, but I often cannot figure out why. For instance, suppose it says that I should trade a knight for an enemy bishop. A human GM who tells me that is the right move would be able to tell me that it is because that leaves me with the two bishops, and tell me that because of the pawn structure we have in this specific game they will be very strong, and knights not so much. The GM could put it all in terms of various strategic considerations and goals, and from him I could learn things that let me figure out in the future such moves on my own. All Stockfish tells me is that it looked freaking far into the future and it makes any other move the opponent can force it into lines that won't come out as well. That gives me no insight into why that is better. With a lot of experimenting, trying out alternative lines and ideas against Stockfish, you can sometimes tease out what the strategic considerations and features of the position are that make it so that is the right move.
    • Cyph0n 11y ago
      The first point is a good one. As for the second point, I think that will be achieved only when we're close to realizing a general AI.
      • jegutman 11y ago
        This is actually a problem I've given a decent amount of though on (although not necessarily reaching a good conclusion), but I think these problems are actually related and not impossible for this simple case. It comes to an issue of what parts of the analysis and at what depth did a best move come to vision? Was it bad when it was sorted for 8 ply but good at 16? Maybe that won't "tell" a person why a move was good, but it gives a lot of tools to help try to understand them (which can be exceedingly difficult right now if a line is not part of the principal variation, but ultimately affects the evaluation by an existing "refutation". But I think the other "difficulty" is that 1800 players play badly in lots of different ways, 2200s play badly in lots of different ways and even Grandmasters play badly in lots of different ways, but very strong chess engines play badly only in a few sometimes limited ways.
  • fspeech 11y ago
    Are games against Fan played by the distributed or single machine version of AlphaGo?
    • fspeech 11y ago
      Found the answer to my question in the paper. It was the distributed version, as one would expect.
  • conanbatt 11y ago
    Hey Inufu. I just replayed the games and have to say that the first game the bot shows very high quality plays. The next two games, it seems like Fan Hui did not perform as well as the first (as opposed to the computer being clearly better than him). Where the games played in a row? Regardless, I'm looking forward to the games with Lee Sedol. I studied in his school in Korea, and personally know how hard it is to get to that level. My assessment is that the bot from those games will NOT beat Lee Sedol. So train it hard for march :)
    • Inufu 11y ago
      The games were all played on separate days. As Fan Hui mentioned in the video, he changed his strategy after the first game to fight more, so that may explain why it seems his performance changed.
    • igravious 11y ago
      I've just replayed them as well. You can see that in the first game the bot played really solidly without risk-taking and didn't want to lose even a few stones. You could say that it played very conservatively but solidly. It won by a tiny margin (2.5) so Fan Hui probably concluded that the bot would win every game by a similar small margin if he didn't change the style of play. I'm sure that in the first game Fan Hui was sounding the bot out for strengths and weaknesses, seeing if it knew all the tesujis and josekis and whatnot. So from then on you see Fan Hui trying to mix it up and play more aggressively and what is very interesting is that he got outplayed in every game, even to the point of losing a big group and resigning. So - if you play conservatively and tentatively and solidly it'll beat you by a sliver, if you try to out-think it it'll nail you. At least at the 2dan pro level. I'd be hesitant for calling a Lee Sedol victory ahead of time. We know that in chess Kasparov beat IBM's bot initially but then IBM tweaked and within a couple of years the bot was too strong. Even though go is much harder than chess I predict that if Google lose this time and if they don't lose by much they'll win the time after that.
      • pmoriarty 11y ago
        Kasparov claimed that when IBM's team won against him they cheated.
  • z0r 11y ago
    I believe that Lee Sedol would sweep all the games if he were to play Fan Hui under the same conditions, which makes the wait until the official match tantalizing. It's fair to say that AlphaGo has mastered Go, but there is a very large difference between a professional who has moved to the west and professional players who are competing at the highest level in regular matches. It's fair to represent Fan Hui as a master of the game, but misleading to represent him as equivalent to currently competing professionals. It is great that we'll get to see a match up against a player who is unquestionably one of the best of all time.
  • beefman 11y ago
    Ke Jie is the strongest go player. Sedol is the 5th strongest. http://www.goratings.org http://www.goratings.org The difference is 100 Elo, which is substantial. Edit: Ke Jie has 700 Elo on Fan Hui. About the same as the gap between Magnus Carlsen and the strongest player at my local chess club.
    • apetresc 11y ago
      In the recent 5-game match between Jie and Sedol a few weeks ago, it was decided in Ke Jie's favour by less than a single point in the fifth game. It literally would have come out differently if they'd used a subtly different (commonly used) scoring ruleset. It's not at all clear who's stronger at their peak.
      • beefman 11y ago
        No, but it's clear who's stronger on average.
      • Rylinks 11y ago
        Wasn't the margin in the 5th game b+1.5?
      • DavidSJ 11y ago
        Keep in mind that professionals are counting throughout the game, and are playing to win, not to win by a lot. So a 0.5 point victory may simply mean the victor was confident in their position and chose not to take unnecessary risks.
        • hyperpape 11y ago
          I follow professional go. It's true that you play safely when you're ahead, which narrows the margin, but .5 is still considered tightly fought.
      • iopq 11y ago
        That's not true, because Ke Jie would not have played the dame points if Japanese scoring would be used.
  • thomasahle 11y ago
    In the game against Lee Sedol, what hardware will AlphaGo be running on? Will it be a cluster or something consumer level? Also, will AlphaGo have access to Lee's previous games? Will Lee have access to AlphaGo's games for preparation?
  • nopinsight 11y ago
    Japanese 9-dan pros and former Japanese cup holders who played against CrazyStone beat it less than 80% of the time [1], while AlphaGo's win rate against it is 80%, according to a comment below by inufu, an engineer at Google DeepMind. If transivity applies then AlphaGo is likely stronger than the average of those former Japanese champions, including Norimoto Yoda, who is currently ranked at 187th (about 300 Elo rating below Lee Sedol and 300 above Fan Hui) [2]. There's a saying in Go circles that there is a substantial gap in playing style or intuition between pros and even top-level amateurs. Whether that is true or not, AlphaGo has definitely crossed the threshold to pro-level play in Go. By March 2016, Google DeepMind would have improved AlphaGo somewhat at least through self-playing and perhaps more processing power. The game with Lee Sedol will be an interesting one to watch! [1] http://www.computer-go.info/h-c/ http://www.computer-go.info/h-c/ [2] http://www.goratings.org/ http://www.goratings.org/
    • dfan 11y ago
      Just to clarify your comment so people aren't confused by the apparently low winning percentages, those are all 4-stone handicap games. (It's still an apples-to-apples comparison.)
    • sehugg 11y ago
      I think the 80% win rate against CrazyStone is for the single-machine version. The distributed version won 100% of the time against CrazyStone and 80% of the time against the single-machine version.
    • devy 11y ago
      FYI, Fan Hui, is ONLY a 2nd Dan Go player. [1] [1]: https://fr.wikipedia.org/wiki/Fan_Hui https://fr.wikipedia.org/wiki/Fan_Hui
      • cardmagic 11y ago
        2 dan pro is a much stronger strength than 2 dan amateur. The difference between a 2 dan pro and a 9 dan pro is usually just one stone handicap whereas the difference between a 2 dan amateur and a 9 dan amateur would be around 7 stones.
  • fspeech 11y ago
    This is an impressive achievement. However there are many subtleties involved when humans play against computers. I think only time can tell how big a breakthrough this really is. It is telling that AlphaGo only won 3:2 for the informal games. As a computer doesn't know the difference between formal and informal this seems to indicate that Alpha isn't truly above Fan Hui in strength. Also the formal games were played with fast game rules, which may be particularly advantageous to computers. Unlike chess go accumulates pieces on board throughout the game. Towards the end there are many stones on board and it is easy for human to err while the search space (possible moves) actually gets smaller for the computer and there is no doubt that computer has stronger book keeping capabilities. So to fairly evaluate human vs computer we may need new time rules different from human vs human games. The paper does not disclose whether the trained program displays true understanding of game rules. Humans don't just use pattern recognition, they also use logic to evaluate game state. While this could be addressed by the search part of the algorithm the paper doesn't appear to give any indication on whether this was studied. For example, the board position strictly speaking does not determine the game state due to ko rules (so the premise of the paper that there is a valuation function v(s), where s is the board position, that determines game outcome is incorrect). It would be particularly interesting to see how the algorithm fares when there are multiple kos going on at the same time. Also it would be interesting to see how well the algorithm understands long range phenomenons such as ladder and liveness. With a million dollar challenge in the plan it is understandable the Google team may not want to disclose weaknesses of the algorithm but in the long run we will get to know how robust it really is. From my experience playing against conv nets I would say if you treat your computer opponent as a human it would be like playing against the hive mind of a group of experts with infallible memory and it is not to your advantage. So one would be better off trying "cheat" moves that human experts do not use on each other and see how well the computer generalizes. Without search and with neural nets alone it is clear that computers do not generalize that well. So it would be interesting to see how well search and neural nets work together and if someone could find the algorithm's weak spots.
    • omphalos 11y ago
      Yeah, MCTS is traditionally terrible with ko. It would be interesting to learn how AlphaGo addresses or doesn't address this.
  • cowpig 11y ago
    Can you please please stop publishing in Nature (and behind paywalls in general)? I don't attend an expensive university but I like to learn things.
    • pas 11y ago
      Someone else linked the paper directly: https://storage.googleapis.com/deepmind-data/assets/papers/deepmind-mastering-go.pdf https://storage.googleapis.com/deepmind-data/assets/papers/d...
  • shpx 11y ago
    Where'd you guys get the 30 million Go games, and is there any chance that the rest of us can get that data to train our own nets?
    • SonOfLilit 11y ago
      30 million moves. I'm pretty sure you can download that many from Go game databases listed here: http://senseis.xmp.net/?GoDatabases http://senseis.xmp.net/?GoDatabases
  • thomasahle 11y ago
    In the paper you estimate that Distributed Alpha Go has ELO around 3200 (if I read the plot correctly.) According to goratings.org, Fan Hui is rated 2900 and Lee Sedol is rated 3515. Doesn't that mean you still have work to do before beating Lee Sedol?
    • jibalt 11y ago
      Of course they do, as they have said.
  • tuxguy 11y ago
    amazing stuff Julian & congrats !!! is there any way to access the nature paper without a paywall(for academic, non-commerical use) ?
• arcanus 11y ago
  Remarkable achievement, much more impressive than Chess, imo.
  • BookmarkSaver 11y ago
    Not just in your opinion, Go is objectively much more difficult for computers than Chess.
    • _yosefk 11y ago
      Until it isn't. Once humans are handily beaten in both games, it's kinda hard to tell which game is harder (I guess you could compare the amount of computations needed to beat the top human player, but that does not let you distinguish if it's harder for computers or conversely easier for humans.)
    • taneq 11y ago
      I think being difficult "for computers" is a misleading concept. Go is more difficult for our current algorithms than chess, at least in part because we've focused on chess for much longer. Sooner or later we may discover some new algorithm (this deep-neural-net-based approach may be it) which will reduce Go to be as tractable as chess, or even more so.
      • xcombelle 11y ago
        It was more difficult for computer programmers to program an ai which reach a human top level, and for this level you have to throw much more hardware in it.
  • gnarbarian 11y ago
    Not just in your opinion. The search space is exponentially larger in go because you can place a piece on any unoccupied square. "The search space for Go's game tree is both wider and deeper than that of chess. It has been estimated to be as big as 10^170 compared to 10^50 for chess, making the normal brute-force game tree search algorithms much less effective. " http://ai-depot.com/LogicGames/Go-Complexity.html http://ai-depot.com/LogicGames/Go-Complexity.html To provide a little more perspective. The estimated number of atoms in the observable universe is about 4*10^80. So we have no hope of ever being capable of "solving" go by mapping out every possible game state AKA "brute forcing" the game. https://en.m.wikipedia.org/wiki/Shannon_number https://en.m.wikipedia.org/wiki/Shannon_number
• onra87 11y ago
  Nice timing ! :) A few hours ago, Zuckerberg said: The ancient Chinese game of Go is one of the last games where the best human players can still beat the best artificial intelligence players. Last year, the Facebook AI Research team started creating an AI that can learn to play Go. Scientists have been trying to teach computers to win at Go for 20 years. We're getting close, and in the past six months we've built an AI that can make moves in as fast as 0.1 seconds and still be as good as previous systems that took years to build. https://www.facebook.com/zuck/posts/10102619979696481 https://www.facebook.com/zuck/posts/10102619979696481
  • deleted 11y ago
    [deleted]
  • oxplot 11y ago
    Note that the game won by AlphaGo against the human player took place in October last year.
  • marvel_boy 11y ago
    So Facebook versus Google is the next sound thing.
    • guelo 11y ago
      I can imagine Google and Facebook having competing armies in the coming robot wars.
      • ph0rque 11y ago
        Speaking of which, what would a robot war look like? I imagine a large portion of the effort would be to hack/otherwise persuade the enemy robots to switch sides.
        • pgeorgi 11y ago
          If their intelligence is worth anything, they'll meet, setup a common picnic, no humans allowed.
• bitcointicker 11y ago
  This is a good place as any to ask this. Do hackernews readers think that computers will eventually have a "mind" and "consciousness" ? Or will it just be simulated? As described in the chinese room thought experiment: https://en.wikipedia.org/wiki/Chinese_room https://en.wikipedia.org/wiki/Chinese_room
  • derrickdirge 11y ago
    I struggle to draw distinctions between a simulated consciousness and a "real" one.
    • bitcointicker 11y ago
      So you don't believe there is any distinction between being "alive" and running software? Providing of course the software is complex enough to display human traits such as thought, emotions, creativity and so forth? Just to be clear, I hold no solid viewpoint on this, I'm just interested as to what other folk here think.
      • kazinator 11y ago
        "Alive" doesn't require human traits. Bacteria and plants are alive. I'm with you though: consciousness and sense of "self" are just matters of complexity of the brain.
      • closed 11y ago
        I think making that distinction would be similar to saying that a computer is not running software because it was built inside minecraft. Although, it's possible that creating something that does what humans do requires the same materials humans are made of (but seems unlikely, or at least I think other materials will allow a close approximation).
      • njharman 11y ago
        "alive", life has deferent meaning (and defined requirements e.g self-reproduction) than "consciousness", "sentience" or "mind". Unless you belief in a mystical soul component (I do not), there is nothing else "there" but machine. A very complex, biological machine. But there is no reason to believe that that a sufficiently powerful software/hardware can not replicate the functionality of that machine exactly. Then what possible difference could there be between the two duplicate machines? But, we will have systems that exhibit a many aspects of "thought" and sentience long before we are able to code up homo sapien sapien.
• xianshou 11y ago
  Here is Nature's video, which also explains how AlphaGo works: https://www.youtube.com/watch?v=g-dKXOlsf98 https://www.youtube.com/watch?v=g-dKXOlsf98 A few neural nets, a lot of MCTS, and a little touch of ingenuity.
  • pmarreck 11y ago
    MCTS = Monte Carlo Tree Search?
    • mlindner 11y ago
      Yes.
• alexandercrohde 11y ago
  Incredibly misleading title (by BBC). Specifically "Champion" referring to a regional champion who isn't at professional level but rather amateur dan.
  • tgb 11y ago
    That's not right: http://senseis.xmp.net/?FanHui http://senseis.xmp.net/?FanHui
  • 1024core 11y ago
    He's the European Champion: https://www.facebook.com/egc2015cz/posts/906549689415462 https://www.facebook.com/egc2015cz/posts/906549689415462
  • alexandercrohde 11y ago
    Okay, I misread that piece, what I read was that the software is ranked as Amateur dan. My point stands: If your title says "beats champion" and you don't qualify champion, that's major link bait. The european champion is only 2p, versus the best players being all 9p ranked.
• tgb 11y ago
  So the team beat Fan Hui, a rank 2 dan professional player. To put that in perspective, the highest ranked professionals are 9 dan corresponding to many hundreds higher score in ELO. Still a long way to go to topple the world champion!
  • tel 11y ago
    I'm not sure if that's always the best way of looking at it since I think most professional dan titles are accomplishment based instead of a measurement of comparative skill. That said, Europe is not the top of the world in Go playing, so while it's notable that Fan Hui represents professional play above beating 9ds on KGS, it may still be a long slog before it can approach Chinese, Korean, or Japanese professionals.
  • karussell 11y ago
    I wonder how much they paid him as I'm not sure if this looks good in the carrier to be the first professional Go player loosing against an AI (?)
    • Vraxx 11y ago
      I don't see how it should affect the perception of his skill. Presumably AlphaGo could beat any player ranked at his skill level or lower, in which case AlphaGo beating him says no more about his skill level than his ranking does.
• pavpanchekha 11y ago
  Very impressive work. When the neural nets for go paper came out a year ago I played around and implemented it (but never got good results), and was very inspired by using neural networks for Go. As an amateur fan of the game, I was particularly intrigued by the neural network's more human-like understanding of the game (if you look at earlier layers, you see patterns that make sense to a Go player). That said, Fan Hui, who Google just beat, is a 2p player, which while incredibly strong is still far away from Lee Sedol or Gu Li. But given the pace of NN progress in recent years, and the incredible resources Google has been devoting to it, I wouldn't give them more than a decade or two.
• julianozen 11y ago
  relevant xkcd - https://www.explainxkcd.com/wiki/index.php/1002:_Game_AIs https://www.explainxkcd.com/wiki/index.php/1002:_Game_AIs
  • waqf 11y ago
    Now that you mention it, Google should work on an AI to play championship-standard Seven Minutes In Heaven.
• race2tb 11y ago
  Clever, but nothing to do with general intelligence.
  • umanwizard 11y ago
    What makes you think so? Developing intuition through pattern recognition has a lot to do with human-like general intelligence. This is way different from chess programs, which work in a way that's much closer to brute force than human-like pattern recognition.
    • argonaut 11y ago
      Brute force statistical inference over millions of examples is an advance, but it is an advance that falls within the same paradigm of machine learning that we've had for decades. IMO, it will really take a paradigm shift to move into general intelligence.
  • arcanus 11y ago
    Do you play go? It has incredibly broad strokes and requires great strategy. I find this a significant accomplishment.
  • Almaviva 11y ago
    Obviously accomplishments like this are interesting for their own sake. But the really interesting question for me is, is there anything here, that is new, that can be used outside of tree-based games of complete information? (A much weaker question, is there anything new here that can be used in other games?) Let's take the ability to match the best humans at various tasks. If we put doing long multiplication better than the best human at "1", and passing the Turing Test at "10", where is a Go playing engine? I'd say less than "2", but still higher than chess. Much higher (but still short of general intelligence, obviously) would be beating the best humans at language translation, proving math theorems, or answering factual questions phrased in natural language. Then, if and when computers can write novels which you'd prefer to read over the best human author, now we're talking. So I think, we don't need to worry about our humanity here yet, and we're not remotely close. Over less than a century we've gone from outperforming humans in arithmetic to outperforming us in things that are a little less like arithmetic but still discrete games modeled by trees and precise searches.
• cobaltblue 11y ago
  Oh man overblown article. Fan Hui is 2p, so very skilled, but the ranking system goes up to 9p. To give a sense of how large a gap that is, there is and has only ever been one Westerner to achieve that rank, Michael Redmond. The article states they plan to face off against Lee Sedol 9p, and if they beat him in a no-handicap game, that will be as impressive as Deep Blue against Kasparov. You'll want to watch this year's Computer Go UEC Cup[0] in March, with Zen and CrazyStone being the typical victors. (CrazyStone in particular has sustained a 6d rating on KGS, a popular Go server, but lately has been at 5d. In the past it has beaten a 9p with a 4 stone handicap, which is impressive, but that handicap is huge and it hasn't yet won with 3 stones.) Of interest this year is that Facebook is competing, and AFAIK they seem to take a similar approach as Google by training the AI using deep learning techniques and then strengthening it further with MCTS. In their public disclosures they claim to beat Pachi pretty often, which puts their bot around 4d-6d, it'll be interesting to see how it fairs against Zen and CrazyStone in the Cup and if it wins against a 9p. [0] http://jsb.cs.uec.ac.jp/~igo/eng/ http://jsb.cs.uec.ac.jp/~igo/eng/
  • Inufu 11y ago
    The version of AlphaGo used in the paper beats CrazyStone about 99% of the time. Even if we give CrazyStone 4 stones handicap, AlphaGo still beats it 80% of the time.
    • cobaltblue 11y ago
      Very nice. How come you guys didn't enter the UEC Cup? (Edit: rereading this it kind of sounds snarky, not meant that way. Really impressive if you can kick CrazyStone's teeth in...)
    • thomasahle 11y ago
      Is that with 1200CPU's?
      • mlindner 11y ago
        From the paper, no that's with "single machine AlphaGo" which is 48 CPUs and 8 GPUs. Distributed AlphaGo beats Single Machine AlphaGo 77% of the time. (Distributed AlphaGo being 1202 CPUs and 176 GPUs.)
• ilyanep 11y ago
  Related question: Has anyone ever experimented with taking a really strong engine for one of these games and then simulating the sort of mistakes that humans make (overlooking certain positions, looking ahead fewer steps, etc) to try and simulate different skill levels of opponents? I don't play Go, but I dabbled a little bit in Chess, and it seems like the engines with "difficulty settings" don't really make the sort of mistakes that humans make. They can, of course, just over-prune the look-ahead tree, but that's not how the human brain works.
  • Laaw 11y ago
    Yeah, IIRC most engines just blunder every once in a while depending on the difficulty setting. rather than playing consistently less strong moves, or something like that.
  • noir_lord 11y ago
    TheKing (the engine behind Chessmaster) had the most human seeming play to me and I played most of the engines over the years. Most of them are more "play like God then hang their queen". The engines now are so strong I can't beat them with Queen and Rook odds so even that doesn't really help.
  • bazzargh 11y ago
    I recall in ~1990 I read a paper which described exactly this (attempt to make the same mistakes as humans). The argument for doing so in the paper was, IIRC that computers beating humans at chess was just a matter of time, but no longer interesting for AI research. It seems quite likely that the book that paper was in was Computers, Chess, and Cognition https://www.springer.com/us/book/9781461390824 https://www.springer.com/us/book/9781461390824 (revised contributions from the WCCC 1989 Workshop New Directions in Game-Tree Search, May 29-30, 1989)...and was probably the one by John McCarthy (yes, that McCarthy) Edited to add: Found it! The paper I recall reading was 'Artifical Stupidity' by William Hartson, in Advances in Computer Chess 4 (1986) https://chessprogramming.wikispaces.com/Advances+in+Computer+Chess+4 https://chessprogramming.wikispaces.com/Advances+in+Computer... ... perhaps nothing concrete came of this though - Hartson was a player and author, not an AI researcher.
  • 11y ago
• hyperpape 11y ago
  This is a more than 200 point ELO jump relative to previous results (see Fan Hui and Franz-Josef Dickhut http://europeangodatabase.eu/EGD/createalleuro3.php?country=**&dgob=false http://europeangodatabase.eu/EGD/createalleuro3.php?country=...). We don't know how big it is, because they beat Fan 5-0, so that only places a lower bound on how good the bot is.
• Noughmad 11y ago
  Sadly, the article doesn't mention what language the software is written is.
  • cfcef 11y ago
    DeepMind does about everything in Torch, which is Lua. Although I'm not sure about Torch's distributed support, so the use of 50 GPUs and Distbelief may mean another language?
  • deleted 11y ago
    [deleted]
    • karussell 11y ago
      Go for it!
  • Inufu 11y ago
    C++ and Lua.
    • Noughmad 11y ago
      Thanks. I was hoping for the "Go" response, but since I'm working with Torch I'm genuinely interested as well.
• tzs 11y ago
  I understand that training this thing requires massive amount of computation, so has to be done on a massive cluster to do in reasonable time. Once they have it trained, though, what are the computational requirements like? Would it be feasible to run it on an ordinary PC? Speaking of Go programs and computation requirements, one of the best performance hacks ever was done by Dave Fotland, the author of the program "Many Faces of Go", which was one of the top computer go programs from the '80s through at least around 2010. He donated code from MFoG to SPEC, which incorporated it into the SPECInt benchmark. So, the better a given processor was at running Fotland's go code, the better it scored on SPECInt. Since SPEC was one of the most widely reported benchmarks, Intel and AMD and the other processor makers put a lot of effort into making their processors run these benchmarks as fast as they code. Net result, Fotland had the processor makers working hard to make their processors run his code faster!
  • mappingbabeljc 11y ago
    Hiya. Reporter here. On the press briefing call Hassabis said that the single node version won 494 out of 495 games against an array of closed- and open-source Go programs. The distributed version was used in the match against the human and will be used in March. Distributed alphago used in the October match was about 170GPUs and 1200CPUs, he said.
    • cakeface 11y ago
      How much did that cost? If you price on AWS or GCC the equivalent and multiply by the length of the match was it like $20k?
• nsxwolf 11y ago
  Does it bother anyone that humans will eventually no longer be good at anything compared to a computer? That can't be good for the human psyche.
  • ygra 11y ago
    Humans still devised and implemented the algorithms those computers are using. I'd count that as a win for the meat side. Then there are things like http://www.sscaitournament.com/ http://www.sscaitournament.com/ going on. The bots there are still quite bad compared to competent human players. There is still hope :)
  • danharaj 11y ago
    Only those human psyches that insist on being at the top of some hierarchy.
    • nsxwolf 11y ago
      This comment seems dismissive. I will never be good at chess or go, let alone the best at either. That in itself doesn't bother me. I'm fine with that. But to have your entire species demoted to second place? That has to have a negative psychological effect, and not just on the individuals with raging egos.
      • danharaj 11y ago
        i don't think it has to be a raging ego. Everyone's like this to a degree: we're trained to think this way from birth. Why can't one enjoy their virtues without comparing them to others? i study mathematics for fun; i was half as good as the kids who ended up going to grad school in my class; only a few of them will end up professors. The fact that professors of mathematics completely outclass me does not impact my enjoyment of my own mathematical ability at all. In fact, i am thrilled when i get to talk to an expert in the fields i'm interested in. Being second place in a cooperative system is not bad. People don't mind that. Being second place in a competitive system is bad. People are scared that machine intelligence will be in competition with them; i think it's better to just reframe the relationship.
• TulliusCicero 11y ago
  I'd be really interested to see DeepMind tackle a strategy game with a more fluid state space like Starcraft. It may be much more difficult to plot out decisions when they're not bucketed into discrete turns, and you can potentially move everything at once.
  • mortehu 11y ago
    One problem with an AI StarCraft player is that it would have a tremendous APM[1] advantage. 1. http://starcraft.wikia.com/wiki/Actions_per_minute http://starcraft.wikia.com/wiki/Actions_per_minute
    • Eridrus 11y ago
      It should be possible to cap the APM of an AI if there is a desire to make it play more like a human, but I would find an uncapped version interesting to see what tactics work well when control is not an issue.
    • ygra 11y ago
      APM mostly means that bots can have perfect micro-management of units (within reason; a bunch of goliaths or dragoons in a chokepoint simply cannot really be managed ;)). This translates to slightly higher income in the beginning [1] (and thus certain strategies can be a bit faster. For ground armies in open fields this can mean a large advantage, although humans are quite good at this as well. APM doesn't really help in creatively coming up with a good strategy to counter a certain build. Just today I watched a game between two Protoss bots, one of which went carriers, the other zealot/reaver. That's ... not really an optimal decision. Tactical manoeuvres like flanking or attacking at different places at the same time are also mostly absent for now (although APM can help there, of course). [1]: http://www.teamliquid.net/forum/brood-war/484849-improving-mineral-gathering-rate-in-brood-war http://www.teamliquid.net/forum/brood-war/484849-improving-m...
    • TulliusCicero 11y ago
      True, but as it stands, current non-cheating AIs in Starcraft 2 and Brood War still stand little chance against experienced players.
• gene-h 11y ago
  Now the question is, how applicable are the approaches developed for AlphaGo to other tree search problems? The beating a professional Go player with less evaluations than it took Deep Blue to beat Kasparov is certainly very exciting.
• jofer 11y ago
  Wow! As a casual (and very bad) go player, this is astounding! Winning 5 games in a row at even strength against a 2-dan professional really is huge. This is not something that I was under the impression would be technically achievable for many years.
• wyldfire 11y ago
  I'd used minimax before but not heard of Monte Carlo tree search. It sounds interesting. From [1]: > Although it has been proven that the evaluation of moves in MCTS converges to the minimax evaluation, the basic version of MCTS can converge to it after enormous time. Besides this disadvantage (partially cancelled by the improvements described below), MCTS has some advantages compared to alpha–beta pruning and similar algorithms. Unlike them, MCTS works without an explicit evaluation function. It is enough to implement game mechanics, i.e. the generating of allowed moves in a given position and the game-end conditions. Thanks to this, MCTS can be applied in games without a developed theory or even in general game playing. > The game tree in MCTS grows asymmetrically: the method concentrates on searching its more promising parts. Thanks to this, it achieves better results than classical algorithms in games with a high branching factor. > Moreover, MCTS can be interrupted at any time, yielding the move it considers the most promising. [1] https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Advantages_and_disadvantages https://en.wikipedia.org/wiki/Monte_Carlo_tree_search#Advant...
  • Terribledactyl 11y ago
    I wrote a MCTS backgammon move recommendation engine/AI for a class in college. It was a lot of fun. It was easy to ramp up to many many cores. I have no idea how to play the game well, never learned, but because the win/lose rules are so clear and using this method, no need to build in game/move theory. Still got great results compared to "advanced" players' games.
    • putterson 11y ago
      I wrote a MCTS Ultimate tic-tac-toe engine[0] over the last little while, and likewise don't know how to play the game well. Once thing I have been mulling over in my mind but haven't really explored is training an NN on the game tree produced by long searches and somehow extracting strategies a la DeepDream. I don't have much experience with NNs though so no idea if it even possible or what the extracts would look like. If anyone would find this interesting work to collaborate on feel free to contact me. The MCTS part is done. 0. https://github.com/putterson/uxobot https://github.com/putterson/uxobot
  • 11y ago
• new_hackers 11y ago
  I worked on a Go player using neural networks in college 15 years ago. Very interesting project and fun. Mine wasn't very good cause we didn't have a lot of training. But it would make legal moves and it was exciting to see when it made a "good" move (i.e. a capture or block).
• esturk 11y ago
  Does anyone know how strong FanHui is? I know Google ranks him as professional 2Dan but the rank may not mean the same thing as it is in China/Korea. I know he's the European Champion, but I've heard there is a large gap between the Asian professionals and their counterparts elsewhere. The ranking in general is also very skewed because it depends on the number of tournaments people win and which specific tournaments. Its a lot like Tennis where some tournaments have a rating of 1000, while others only have 500.
  • lambda 11y ago
    He's a professional 2 Dan in the Chinese Weiqi (Go) Association (source: http://gobase.org/information/players/?pp=Fan%20Hui http://gobase.org/information/players/?pp=Fan%20Hui). EGF and AGA have only just in the last couple of years started giving professional rankings, so most professionals in Europe and the US still have their professional rankings from China, Japan, or Korea, rather than European and American associations.
  • RBerenguel 11y ago
    He is 2p in China, so his rank is actually chinese. In Europe (EGF) he plays as 7d. An oddball rank would be 2-3p in China, 3-5 or so in Japan and maybe 2 in Korea. But just guessing, I'm to far to properly compare, the only gauge is when he plays other "non-EU pros" in the EGC.
  • comboy 11y ago
    There is a big gap between Fan Hui and top Asian players. But I think Demis is being very modest saying that the games were close.
  • igravious 11y ago
    So the thing is, there really are only Asian pros. (Having said that, here is a list[1] of Western pros). It's only in the last few years that the American Go Association could start certifying[2] Go players as pro. And to the best of my knowledge the European Go Association still does not have this power. Go, amazing game though it is, was relatively unknown outside CJK (China, Japan, Korea) until post-WW2. But globalisation has meant that the rest of the world is finally hearing about this beautiful game. So it migrates to the US via Japan (it's called iGo^ in Japan, which is why it is called Go in the West) and to Europe via Russia and the US. The US is a bit in advance of Europe but not by a huge amount. Arguably Eastern Europe is stronger than Western, as in Chess. So basically Fan Hui[3] is 2p Chinese rank which makes him pretty solidly 2p. He's the three time European champion which should give you an idea of the strength of players in Europe. The top European players like Alexander Dinerchtein who is roughly the same strength as Fan Hui has an official 3p rank, Korean I believe. So Fan Hui is some ways off the top 9p players in CJK but he was convincingly beaten by AlphaGo so I'd be hesitant to try to infer its rank from this one performance … [1] http://learnbaduk.com/western-go-professionals.html [2] http://www.usgo.org/aga-professional-system [3] http://senseis.xmp.net/?FanHui ^ Baduk in Korea, Weiqi in China
• rshm 11y ago
  AlphaGo Full Text - PDF : https://storage.googleapis.com/deepmind-data/assets/papers/deepmind-mastering-go.pdf https://storage.googleapis.com/deepmind-data/assets/papers/d... Facebook Paper - PDF http://arxiv.org/pdf/1511.06410v2.pdf http://arxiv.org/pdf/1511.06410v2.pdf Pachi Original Paper - PDF http://pasky.or.cz/go/pachi-tr.pdf http://pasky.or.cz/go/pachi-tr.pdf
  • mlindner 11y ago
    Pachi isn't in the same league as AlphaGo. Pachi can't win at all against AlphaGo without handicap. With a 4 stone handicap Pachi only wins 1% of the time against AlphaGo.
• andreyk 11y ago
  Don't think many have said it here, so just fyi, to me this does not seem like a big 'breakthrough' in AI so much as a good demonstration of smartly combining existing current ideas. Quoting from a developer of a monte-carlo tree based GO bot (http://www.sciencemag.org/news/2016/01/huge-leap-forward-computer-mimics-human-brain-beats-professional-game-go http://www.sciencemag.org/news/2016/01/huge-leap-forward-com...): "Coulom agrees, but he notes that there isn't one key new invention that makes the whole program work. "It's more like a great engineering achievement," he says. "The way they put all the pieces together is really innovative."" Not to disparage the result, but just saying it seems inline with the progress in recent years of using deep neural nets for reinforcement learning with games.
  • eli_gottlieb 11y ago
    >Don't think many have said it here, so just fyi, to me this does not seem like a big 'breakthrough' in AI so much as a good demonstration of smartly combining existing current ideas. Well yes. But good engineering is still impressive.
    • andreyk 11y ago
      Indeed, the approach and result are without argument impressive.
• deleted 11y ago
  [deleted]
• baq 11y ago
  honestly i didn't expect this news in this decade. well done.
• Madmallard 11y ago
  If the bot is trained through human play and trains against itself, would it not only be as good as the best human? This doesn't seem like computerized intelligence, this seems like advanced human intelligence. If you get the thing to play hundreds of games against 9P dans it will probably eventually beat them yes. But the theoretical limit to skill in that game is still probably a big margin above 9P. How will we make it hit that mark?
• dmix 11y ago
  Is there video available of the matches between AlphaGo vs Fan Hui? I'd love to watch them play.
  • wrsh07 11y ago
    You can see replays on this blog post: http://www.furidamu.org/blog/2016/01/26/mastering-the-game-of-go-with-deep-neural-networks-and-tree-search/ http://www.furidamu.org/blog/2016/01/26/mastering-the-game-o...
• Slippery_John 11y ago
  Please tell me this was written in Go
• plainOldText 11y ago
  Too bad Marvin Minsky did not get a chance to see this. I think he would have enjoyed it deeply.
  • peter303 11y ago
    This did not happen overnight. The big computer companies have been building AI labs for years, decades in case of MicroSoft. They've been revisiting Go for the past few years too. One of Marvin's early students advises Googles R&D. These companies have raided every major university. If Marvin was still alert in his final years, he would have known some about this.
• imh 11y ago
  If this trounces the leading human this spring, I'll be really excited if the AI experts start working on physical games. The RoboCup (robot soccer) hasn't had nearly the the improvements that more logical games have (e.g. chess and Go). I hope that combining game playing with physical movement with vision, and communication is the next frontier.
• dang 11y ago
  There is also a substantive blog post at http://googleresearch.blogspot.com/2016/01/alphago-mastering-ancient-game-of-go.html http://googleresearch.blogspot.com/2016/01/alphago-mastering..., via https://news.ycombinator.com/item?id=10981729 https://news.ycombinator.com/item?id=10981729.
• Eliezer 11y ago
  People occasionally ask me about signs that the remaining timeline might be short. It's very easy for nonprofessionals to take too much alarm too easily. Deep Blue beating Kasparov at chess was not such a sign. Robotic cars are not such a sign. This is. "Here we introduce a new approach to computer Go that uses ‘value networks’ to evaluate board positions and ‘policy networks’ to select moves... Without any lookahead search, the neural networks play Go at the level of state-of-the-art Monte Carlo tree search programs that simulate thousands of random games of self-play. We also introduce a new search algorithm that combines Monte Carlo simulation with value and policy networks. Using this search algorithm, our program AlphaGo achieved a 99.8% winning rate against other Go programs, and defeated the human European Go champion by 5 games to 0." This matches something I've previously named in private conversation as a warning sign - sharply above-trend performance at Go from a neural algorithm. What this indicates is not that deep learning in particular is going to be the Game Over algorithm. Rather, the background variables are looking more like "Human neural intelligence is not that complicated and current algorithms are touching on keystone, foundational aspects of it." What's alarming is not this particular breakthrough, but what it implies about the general background settings of the computational universe. Go is a game that is very computationally difficult for traditional chess-style techniques. Human masters learn to play Go very intuitively, because the human cortical algorithm turns out to generalize well. If deep learning can do something similar, plus (a previous real sign) have a single network architecture learn to play loads of different old computer games, that may indicate we're starting to get into the range of "neural algorithms that generalize well, the way that the human cortical algorithm generalizes well". A number of commenters are talking about how the human professional beat was well below the world champion. This is entirely missing the point. Beating the best human is an entirely arbitrary threshold, which is why Deep Blue vs. Kasparov wasn't a great sign per se. There's probably nothing computationally distinguished about the very best human versus a very good human - the world champion isn't using a basically different algorithm. What matters is the discontinuous jump, how it was done, and the absolute level of human-style competence achieved. This result also supports that "Everything always stays on a smooth exponential trend, you don't get discontinuous competence boosts from new algorithmic insights" is false even for the non-recursive case, but that was already obvious from my perspective. Evidence that's more easily interpreted by a wider set of eyes is always helpful, I guess. I hope that everyone in 2010 who tried to eyeball the AI alignment problem, and concluded with their own eyeballs that we had until 2050 to start really worrying about it, enjoyed their use of whatever resources they decided not to devote to the problem at that time.
• Buetol 11y ago
  I can only wish the source would be released for all the researchers working on AI to improve also their algorithms. I understand that Google wants to keep his edge but it also slow down the whole field.
  • modeless 11y ago
    Accusing Google of slowing down the field is laughable. Google has opened up a ton of AI stuff, in every category imaginable, from Inception (pre-trained model), Street View House Numbers (giant dataset), gemmlowp (infrastructure for fast matrix multiplies), deep dream (implementation of a specific deep learning technique), all the way to TensorFlow (complete production-ready neural net framework with examples and a free graduate-level university course to go with it). And of course they're publishing open access papers for everything in addition to the code releases. Furthermore, they're also employing core contributors who continue to maintain important libraries like Ceres Solver, Eigen, and Keras, just to name a few. Google has even open sourced DeepMind's previous most impressive achievment, the Atari player. Based on that track record it's probably only a matter of time before the Go player is released. I'd expect it not long after the upcoming match, if they win.
    • Buetol 11y ago
      Thanks, that's a very true and good reminder. I didn't know the Atari one was released, I take back what I said.
• nickhuh 11y ago
  For people interested in the use of neural nets to evaluate board position, it might be worthwhile reading up on TD-gammon which this work builds Off of
• mathgenius 11y ago
  I'm wondering if strong players will learn to beat AlphaGo by playing unconventional openings, so as to confuse the neural net, and get the upper hand before the MCTS can take over in the middle game. This could be good for the game of Go in general as top players are forced to find new ways to play. Just speculating as I am not a particularly strong player myself.
• hmate9 11y ago
  Poker next please!
• fiatjaf 11y ago
  My only question is: why are you doing this? You're taking out the fun of the game just to prove yourselves?
• interdrift 11y ago
  Why is this so important? How does it get us closer to general AI?
• bshanks 11y ago
  my summary (may be wrong): they create a convolutional neural network with 13 layers to select moves (given a game position, it outputs a probability distribution over all legal moves, trying to assign higher probabilities to better moves). They train the network on databases of expert matches, save a copy of the trained network as 'SL' then train it further by playing it against randomly selected previous iterations of itself. Then they use the history of the move-selecting network playing against itself to generate a new training set consisting of 30 million game positions and the outcome of that game, with each of the 30 million positions coming from a separate game. They use this training set to train a new convolutional neural network (with 13 layers again, i think) to appraise the value of a board position (given a board position, it outputs a single scalar that attempt to predict the game outcome of that board position). They also train ANOTHER move-predicting classifier called the 'fast rollout' policy; the reason for another one is that the fast rollout policy is supposed to be very fast to run, unlike the neural nets. The fast rollout policy is a linear softmax of small pattern features (move matches one or more response features, Move saves stone(s) from capture, Move is 8-connected to previous move, Move matches nakade patterns at captured stone, Move matches 12-point diamond pattern near previous move, move matches 3x3 pattern around candidate move). When a feature is "move matches some pattern", i don't understand if they mean that "match any pattern" is the feature, or if each possible pattern is its own feature; i suspect the latter, even though that's a zillion features to compute. The feature weights of the fast rollout classifier are trained on a database of expert games. Now they will use three of those classifiers, the 'SL' neural network (the saved network that tried to learn which move an expert would have made, before further training against itself), and the board-position-value-predicting network, plus the 'rollout' policy. The next part, the Monte Carlo Tree Search combined with the neural networks, is kinda complicated and i don't fully understand it, so the following is likely to be wrong. The idea of Monte Carlo Tree Search is to estimate the value of a board position by simulating all or part of game in which both players in the simulation are running as their policy a classifier without lookahead (eg within the rollout simulation, neither player does any lookahead at each step); this simulation is (eventually) done many times and the results are averaged together. Each time the Monte Carlo simulation is done, the policy is updated. In order to take one turn in the real game, the program does zillions of iterations; in each iteration, it simulates a game-within-a-game: It simulates a game where the players use the current policy, which is represented as a tree of game states whose root is the current actual game state, whose edges are potential moves, and whose nodes or edges are labeled with the current policy's estimated values for game states (plus a factor encouraging exploration of unexplored or underexplored board states). When the simulation has visited the parent of a 'leaf node' (a game state which has not yet been analyzed but which is a child of a node which is not a leaf node) more than some threshold, the leaf node is added to a queue for an asynchronous process to 'expand the leaf node' (analyze it) (the visit-count-before-expansion threshold is adaptively adjusted to keep the queue short). This process estimates the value of the leaf node via a linear combination of (a) the board-position-value-predicting network's output and (b) the outcome of running a simulation of the rest of the game (a game within a game within a game) with both players using the 'fast rollout' policy. Then, the SL neural network is used to give initial estimates of the value of each move from that board position (because you only have to run SL once to get an estimate for all possible moves from that board position, whereas it would take a long time to recurse into each of the many possible successor board positions and run the board-position-value-predicting network for each of these). Because the expansion of a leaf node (including running SL) is asynchronous, in the mean time the node is 'expanded' and a 'tree policy' is used to give a quick estimate of the value of each possible move from the leaf node board state. The tree policy is like the quick rollout policy but with a few more features (move allows stones to be captured, manhattan distance to two previous moves, Move matches 12-point diamond pattern centered around candidate move). At the end of each iteration, the action values of all (non-leaf) nodes visited are updated, and a 'visit count' for each of these nodes is updated. At the end of all of these iterations, the program actually plays the move that had the maximium visit count in the monte carlo tree search ("this is less sensitive to outliers than maximizing action-value"). some more details: During monte carlo tree search, they also use a heuristic called 'last good reply' which is sorta similar to caching. the move-predicting networks are for the most part just fed the board state as input, but they also get a computed feature "the outcome of a ladder search" because Go is symmetric w/r/t rotations of the board, the move-predicting networks are wrapped by a procedure that either randomly selects a rotation, or runs them for all rotations and averages the results (depending on whether or not the network is being used for monte carlo tree search or not)
• quackerhacker 11y ago
  So does that mean now companies can have their AI programs compete against each other in a Go match for the "title."
• gambler 11y ago
  When reading such news I always get the feeling that the game is stacked in favor of the computer. Not in the sense of rules, but in the sense of media coverage and interpreting the results. It seems like a lot of people in AI and IT are pretty desperate for validation of their notions about human (un)intelligence. Watch 'Game Over: Kasparov and the Machine' for a good description of what I mean. And yes, I bet many people here hate that movie. That's exactly what I'm talking about. There are a lot of relatively simple chess programs that can beat most amateur players. Personally, I cannot beat the Go program I have on my cellphone. (I am pretty horrible at the game.) None of that seems newsworthy. And yet after 5 wins against a pretty strong (but not world's best) Go player, and it's suddenly a "breakthrough" that changes everything. If some new chess player have beat Deep Blue 4 to 2, would we revert the perceived status of AI to what it was before that match with Kasparov? I'm not saying this advance in AI is unimpressive. I just don't see a fair evaluation of what it means. There is too much one-directional hype.
  • sanderjd 11y ago
    > If some new chess player have beat Deep Blue 4 to 2, would we revert the perceived status of AI to what it was before that match with Kasparov? Not saying I disagree with much of your comment, but I think the answer to that question is actually, "yes". As a middling chess player, I think it would have been impossible for "a new chess player" to have beaten Deep Blue 4 to 2, and these days, it requires near-best-in-the-world prowess to pick up any games at all off the best chess computers, which I think proves that it wasn't hype-y or unfair to claim that the machines have beaten us at this.
    • deleted 11y ago
      [deleted]
    • gambler 11y ago
      Hype is hype, whether it turns out to be justified or not. Not all people can beat even a trivial Go program. You may be missing my larger point. It is not about whether humans can beat the best chess or Go computers. It is about a very strong bias in favor of algorithms in general. The dynamics around human vs computer chess matches simply demonstrated this bias in an easily percievable form. Who cared about Kasparov's later victories and draws against other state of the art programs? They received very little coverage. Chess is just a game. The important thing to consider is what will happen when algorithms start to competre with people in more complex and ambiguous areas.
• fsiefken 11y ago
  Fortunately humans are creative and intelligent enough to devise games where they still have the upper hand. * Arimaa 17281 branching factor * Connect6 46000 branching factor * Nymbat 10^9 branching factor * Shogi * Crazyhouse chess More info: http://en.chessbase.com/post/computer-resistant-chess-variants http://en.chessbase.com/post/computer-resistant-chess-varian... http://arimaa.com/arimaa/ http://arimaa.com/arimaa/ http://www.cjgames.com/index.php?page=nymbat http://www.cjgames.com/index.php?page=nymbat https://en.wikipedia.org/wiki/Game_complexity https://en.wikipedia.org/wiki/Game_complexity http://www.littlegolem.net/jsp/games/ http://www.littlegolem.net/jsp/games/ http://senseis.xmp.net/?OtherGamesConsideredUnprogrammable http://senseis.xmp.net/?OtherGamesConsideredUnprogrammable
  • deleted 11y ago
    [deleted]
  • hyperpape 11y ago
    Last year a machine beat the best humans in Arimaa. Until this announcement, shogi was about as close as go, iirc.
• mark_l_watson 11y ago
  This is a wonderful achievement! I wrote and sold a Go playing program for the Apple II in the late 1970s, and I have had the privilege of playing the woman's world champion and the champion of South Korea -- so I have some experience to base my praise on. I never thought that I would see a professional level AI Go player in my lifetime. I am taking the singularity more seriously.
• graycat 11y ago
  But, but, but, ..., we should ask where did the AI software come from? Three guesses, the first two don't count, and the third is, may I have the envelope please, [drum roll], and the winner is, humans! So, it's not that AI beat a human. Instead, a human with a machine beat a human without one!
• thinkdoge 11y ago
  how far away is writing ai for dota/sc2?
• everly 11y ago
  Zuck just posted (literally yesterday) about FB's attempt to create an AI that could beat humans in Go. https://m.facebook.com/story.php?story_fbid=10102619979696481&id=4 https://m.facebook.com/story.php?story_fbid=1010261997969648...
• pmontra 11y ago
  Some info from the Nature paper. AlphaGo played Fan Hui using 1202 CPUs and 176 GPUs. It's strenght was assessed to be 3140 ELO on the scale used by www.goratings.org/ (BTW, this is different from the European ELO system) That would put it at #279 in the world. Fan Hui is number 633 at 2916. AlphaGo's next opponent will be Lee Sedol, #5 at 3515. The single computer version of AlphaGo is estimated to be 2890 ELO, which would be #679 in the world. It's is closer to what we might be playing against on our laptops and phones but still 48 CPUs and 8 GPUs.
  • devy 11y ago
    Interesting! Lee Sedol is not even #1 rated Go player on that chart, he's only #5 as of today.
  • tim333 11y ago
    Doing some arithmetic on that the increase in ELO score with number of processors seems to roughly match 60 points per doubling of computer speed suggested in Wikipedia's chess article[1]. As Sedol is 375 points ahead that would suggest they'd need about 80 times as many processors to equal him with current software. Maybe they'll improve the software. Or crank up a lot of machines. [1] https://en.wikipedia.org/wiki/Computer_chess#Playing_strength_versus_computer_speed https://en.wikipedia.org/wiki/Computer_chess#Playing_strengt...
• arsenide 11y ago
  If anyone wants to play a game of go, regardless if you are a seasoned amateur or a complete beginner, please send me a message on http://online-go.com http://online-go.com (username mongorians)! If you have no prior experience I would be happy to teach you the basics -- it is truly an incredible game.
• ragebol 11y ago
  What makes humans so much more intelligent that they can learn to be as good as this game when playing only up to 1000 games per year and be just as good as a something that can train on a million games per day? I want computers that can learn on small data instead of big data, like humans do.
• vancan1ty 11y ago
  If Google really wants the March matchup with Lee Sedol to be fair, it should make available a number of AlphaGo's training games for Sedol to evaluate. Otherwise, we have a similar situation to Deep Blue vs Kasparov, where Deep Blue had access to hundreds of Kasparov's games but Kasparov did not have access to Deep Blue's past games to evaluate. This is a major disadvantage for the human player.
  • xcombelle 11y ago
    knowing the previous game of a player is not such an advantage at least in go
• superforecaster 11y ago
  AlphaGo tackling Lee Sedol next. If you want a forum to make a prediction on it, check out GJ Open. https://www.gjopen.com/questions/133-will-google-s-alphago-beat-world-champion-lee-sedol-in-the-five-game-go-match-planned-for-march-2016 https://www.gjopen.com/questions/133-will-google-s-alphago-b... Forecasters will get scored, so you can see who's right and who's not. Hopefully we'll get some good technical debate on there too (disclosure: I'm affiliated with GJ Open site)