Sadly as I write this my uncle and personal hero who spent 17 years of his life working towards a Ph.D. on abstraction hierarchies for use in Go artificial intelligence, has been moved into hospice care. I'm just glad that in the few days that are left he has a chance to see this happen, even if it is not the good old-fashioned approach he took.

[1] He recently started rewriting the continuation of this research in golang, available on Github: https://github.com/Ken1JF/ah

Finally, the sixth attempt is written in the right language! Now it will succeed for sure.

AlphaGo's architecture resembles much closer to how humans think and learn.

I initially learned Go to be able to have some chance of an AI. I then had some transformative experiences that coincided with my early kyu learning of basic Go lessons. On of the big lessons in Go is to learn how to let go of something. Taking solace in anything on the Go board is one of the blocks you work through when you develop as a Go player.

I had already known about two years ago that just the Monte Carlo approach was already scalable. If Moore's Law continues, it was a matter of time before the Monte Carlo approach would start challenging the professional ranks -- it had already gotten to the point where you just needed to throw more hardware at it.

AlphaGo's architecture adds a different layer to it. The Deep Learning isn't quite as flexible as the human mind, but it can do something that humans can't: learn non-stop, 24/7 on one subject. We're seeing a different tipping point here, possibly the same kind of tipping point when we witnessed the web browser back in the early 90s, and the introduction of the smartphone in the mid '00s. This is way bigger (to use a Go terminology) than what happened with chess.

    > 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 intelli-
    > gently, 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

edit: some actual estimates. Deep Blue had 11.38 GFLOPS[1]. According to the paper in Nature, distributed AlphaGo used 1202 CPUs and 176 GPUs. A single modern GPU can do between 100 and 2000 double precision GFLOPS[2]. So from GPUs alone AlphaGo had access to 4-5 orders of magnitude more computing power than Deep Blue did.

1] https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)

2] https://en.wikipedia.org/wiki/List_of_Nvidia_graphics_proces...

AlphaGo went way beyond that. It actually learned more like how a Go player does. It was able to examine and play a lot of games. That's why it was able to beat a 2p pro, and within less than half a year, challenge a 9p world-class player at least on even terms.

The big thing isn't that AlphaGo is able to play Go at all at that level, but that learned a specific subject much faster than a human.

While it's fun to hate on IBM, it's not really fair to say Deep Blue was throwing hardware at the problem but AlphaGo isn't. Based on the paper AlphaGo will perform much worse in terms of ELO ranking on a smaller cluster.

[0] http://www.economist.com/news/science-and-technology/2169454...

The AlphaGo that beat the 2p European champion five months ago was not as strong as the AlphaGo that beat Lee Sedol (9p). I don't think this was just the AlphaGo team throwing more hardware. I think they had been constantly running the self-training during the intervening months so that AlphaGo was improving itself.

If that is so, then the big thing here isn't that AlphaGo is the first AI to win an official match with the currently world's strongest Go player. It's that within less than half a year, AlphaGo was able to learn and grow to go from challenging a 2p to challenging the world's strongest player. Think about that.

And AI is just one strand. There are several strands that are as deeply changing, that is happening simultaneously.

I remember someone speaking about the shift between classical hard sci fi and more current sci-fi authors like Neal Stephenson or Peter Hamilton. The classical authors like Heinlein or Asimov might do world building where they just change one thing. What would the world be like if that one thing changed? After a certain point though, things were changing so fast that later authors didn't do that. There were too many things that changed at the same time.

Except if a big solar flare hits us ;}

Various commentators mentioned how both players, human and synthetic, made a few mistakes. Even I caught a slow move made by the AI. So whether Lee Sedol was at the top of his peformance, or not, is a bit of a debate. But the AI was clearly on the same level, whatever that means.

It was an intense fight throughout the game, with both players making bold moves and taking risks. Fantastic show.

The slow move might just mean that this was sufficiently big and safer.

Fan Hui said the machine played extremely consistently 6 months ago. He said playing the computer was "like pushing against a wall" - just very strong, very consistent performance.

Also, the people working on it flat out told the world that today's version of AlphaGo beats October's version literally all the time.

There are different strategies depending upon how much emphasis is placed upon early territorial gains as opposed to "influence" which is used for later later territorial gains.

Similarly, playing "passive" moves that make territory without starting a "fight" versus agressively contesting for every piece of territory available.

I am tremendously unfamiliar with recent A.I developments.

Can anyone provide some written references to this effect? Last time I searched (extensively), I couldn't really find anyone saying this.

Fotland and others tried to figure out how to modify their programs to integrate full-board searches. They met with some limited success, but by 2004, progress stalled again, and available options seemed exhausted. Increased processing power was moot. To run searches even one move deeper would require an impossibly fast machine. The most difficult game looked as if it couldn’t be won."

http://www.wired.com/2014/05/the-world-of-computer-go/

The article then goes on to discuss how Monte Carlo was the real breakthrough.

Nonetheless, the quoted estimate in the article (mentioned twice, including in the second sentence) is "I think maybe ten years", ie 2024, which while inaccurate is probably "in our lifetimes".

Not quite what you are after, but it's pretty clear that he didn't think it would be beating the world champion in 14 years.

[1] NY Times, 2002, http://www.nytimes.com/2002/08/01/technology/in-an-ancient-g...

http://www.weforum.org/agenda/2016/03/have-we-hit-a-major-ar...

"At the US Congress 2008, he [Myungwan Kim] also played a historic demonstration game against MoGo running on an 800 processor supercomputer. With a 9 stone handicap, MoGo won by 1.5 points. At the 2009 congress, he played another demonstration game against Many Faces of Go running on 32 processors. Giving 7 stones handicap, Kim won convincingly by resignation."

(Kim Myung Wan (born 1978) is a 9d Korean professional who has taken up residence in the Los Angeles area as of 2008)

More information here, with a nice graph:

http://senseis.xmp.net/?ComputerGo

http://i.imgur.com/RvQsf6v.png

You can see progress seemed to be slow at 2012.

Then people hit on using Monte Carlo which was the big step forward you show in your graphs. But then, that progress seemed to stall to the degree that various people were quoted in a Wired article a couple years ago about how they weren't sure what was going to happen.

Yet, here we are today.

To add to that, in Godel Escher Bach, Hofstadter in 1979 predicted that no chess engine would ever beat a human grandmaster player. It just goes to show how hard it is to predict what is, and also will remain, impossible for machines!

"We always overestimate the change that will occur in the next two years and underestimate the change that will occur in the next ten. Don't let yourself be lulled into inaction."

There are no flying DeLoreans (Back to the Future). There are no hotels on the Moon (Mad Man). People overestimate long-term (20+ years) change.

It just shows once more that for any maxim there is a maxim with the opposite meaning.

> Pocket Fritz 4 won the Copa Mercosur tournament in Buenos Aires, Argentina with 9 wins and 1 draw on August 4–14, 2009. Pocket Fritz 4 searches fewer than 20,000 positions per second. This is in contrast to supercomputers such as Deep Blue that searched 200 million positions per second. Pocket Fritz 4 achieves a higher performance level than Deep Blue.[3]

The first steps are always the most inefficient. Make it work, make it right, make it fast.

[1]: https://en.wikipedia.org/wiki/Deep_Blue_%28chess_computer%29... [2]: http://cdn.slashgear.com/wp-content/uploads/2008/10/htc_touc... [3]: https://en.wikipedia.org/wiki/Human%E2%80%93computer_chess_m...

I find this overly optimistic because of the huge amount of power required to run the Go application. Remember, we're getting closer and closer to the theoretical lower limit in the size of silicon chips, which is around 4nm (that's about a dozen silicon atoms). That's a 3-4x improvement over the current state of the art.

The computer to run AlphaGo requires thousands of watts of power. A smartphone can do about one watt. A 3-4x increase in perf per watt isn't going to cut it.

If there will be a smartphone capable of beating the best human Go players, my guess is that it won't be based on general purpose silicon chips running on lithium ion batteries.

On the other hand, a desktop computer with a ~1000 watt power supply (ie. a gaming pc) might be able to do this in a matter of years or a few decades.

I already know that your answer will be: "but this time it is a fundamental physics limit". Whatever. I'm jaded by previous doomsday predictions. We'll go clockless, or 3D, or tri-state or quantum. It'll be something that is fringe, treated as idiotic by current standards and an obvious choice in hindsight.

That previous constraints have been beaten in no way supports the argument that we will beat the laws of physics this time.

If the normalcy bias was in effect, they wouldn't be spending that money.

It's certainly possible that we'll break more barriers with clever engineering and new scientific breakthroughs. But that doesn't mean the Normalcy Bias isn't in play here.

However, I'm talking hundreds of billions spent on R&D to specifically to solve problems associated with chip manufacture. It took on the order of 25 years to solve each of the problems listed in the grandparent's post. Nobody would spend that kind of money or time on something that they think somebody else would solve.

Say you spent a hundred billion dollars to extinguish the sun- that wouldn't work. How much money you spend is irrelevant when you're up against what people call "hard physical limits".

I've read several articles saying that different cancers are not exactly the same disease, but more like different diseases with the same symptom (uncontrolled tumor growth) and different etiology, even sometimes different from person to person, not just from tissue to tissue. This was said to be a reason that a general cancer cure is so elusive. But is it really thought of as impossible, not just elusive?

Maybe our inability to extinguish the sun is also a limitation of knowledge more than a hard physical limit!

Even if I'm right about this, your description of the situation would still be accurate in that there would be no way to simply throw more money at the problems and guarantee a solution; there would need to be qualitative breakthroughs which aren't guaranteed to happen at any particular level of expenditure. If people had spent multiples of the entire world GDP on a space program in the 1500s, they would still not have been able to get people to the moon, though not because it's physically impossible to do so in an absolute sense.

Yep, that's my point, thanks. Sorry, I'm not in my most eloquent today :)

Finally, the hardware we are using to run these programs is insane. Sure the silicon is approaching some hard physical limits, but your processor spends most of that power trying to make old programs run fast...

My prediction is that with enough ressources it is possible to write a Go AI which runs on general purpose hardware that's manufactured on current process nodes and fits in your pocket.

If you look at http://googleresearch.blogspot.com/2016/01/alphago-mastering... you'll find that Google's estimate of the strength difference between the full distributed system and their trained system on a single PC is around 4 professional dan. Let's suppose that squeezing it from a PC to a phone takes about the same off. Now a pocket phone is about 8 professional dan weaker than the full distributed system.

If their full trained system is now 9 dan, that means that they can likely squeeze it into a phone and get a 1 dan professional. So the computing power on a phone already allows us to play at the professional level!

You can get to an unbeatable device on a phone in 10 years, if self-training over a decade can create about as much improvement they have done in the last 6 months, AND phones in 10 years are about as capable as a PC is today. Those two trade off, so a bigger algorithmic improvement gets you there with a weaker device.

You consider this result "overly optimistic". I consider this estimate very conservative. If Google continues to train it, I wouldn't be surprised if there is a PC program in a year that can beat any Go player in the world.

It'll likely be hardware that can be generalized to run any kind of deep net. The iPhone 5S is already capable of running some deep nets.

As a friend mentioned, it isn't the running of the net, it's the training that takes a lot more computational power (leaving aside data normalization). A handheld device that is not only capable of running a deep net, but also training one -- yeah, that will be the day.

There are non von Neuman architectures that are capable of this. Someone had figured out how to build general-purpose CPUs on silicon made for memory. You can shrink down a full rack of computers down into a single mother board, and use less wattage while you are at it.

This really isn't about having a phone be able to beat a Go player. Go is a transformative game that, when learned, it teaches the player how to think strategically. There is value for a human to learn Go, but this is no longer about being able to be the best player in the absolute sense. Go will undergo the same transformation that martial arts in China and Japan has gone through with the proliferation and use of guns in warfare.

Rather, what we're really talking about is a shot at having AIs do things that we never thought they could do -- handle ambiguity. What I think we will see is -- not the replacement of blue collar workers by robots -- but the replacement of white collar workers by deep nets. Coupled with the problems in the US educational system (optimizing towards passing tests rather than critical thinking, handling ambiguity, and making decisions in face of uncertainty), we're on a verge of some very interesting times.

I just don't see a 1000x+ decrease in the power required happening in a decade or two without some revolutionary technology I can't even imagine. Is this what you meant? I'm sure most people couldn't imagine modern silicon chips in the 1950s vacuum tube era. But now we're getting close to the theoretical, well-understood minimums in silicon chips, so another revolutionary step is required if another giant leap like that is to be achieved.

    > physics and experience in working in semiconductors

    > without some revolutionary technology I can't even
    > imagine

> I find this overly optimistic

exDM69 never said it's not gonna happen, he just said that it's not going to happen in ten years, and I agree with him. Revolutions never occurs that quickly. To achieve that we don't just need an improvement of the current state of the art, we need a massive change and we don't even know what it's going to look like yet ! This kind of revolution may occur one day but not in ten year.

And it could even never happen, remember that we don't have flying cars yet ;)

The optimistic position is a bit like saying: "I 've lived 113 years, I'm not going to die now!". It's entirely possible for a trend to reverse itself. If machine learning has taught us something is that background knowledge (in this case, of processor technology) gives you much better results than just guessing based on what happened in the past.

Stacked 3D chips (HBM, etc), Heterogenous computing (OpenCL, Vulkan), Optical computing, Memristors, Graphene-based microchips, Superconductors, Spintronics, Quantum computers, Genetic computers (self-reconfigurable)

The rest of the technologies you mention have great potential but will they be available in a smartphone in one decade? I don't think so.

It might as well slow down again and we have to remember that most humans in history saw little to no advances in technology over their lifetime.

I'm excited for the possibilities modern science opens up but I also think we might reach a point where fundamental progress stalls for a century or two.

(2000 kilocalories / day -> ~100W; the brain uses about a quarter of your calories.)

Not necessarily the same kind, and, if I had to make the call, I would say they aren't of the same kind.

I don't think that's quite true as a description of what we knew about computer Go previously, though it depends on what precisely you mean. Recent systems (meaning the past 10 years, post the resurgence of MCTS) appear to scale to essentially arbitrarily good play as you throw more computing power at them. Play strength scales roughly with the log of computing power, at least as far as anyone tested them (maybe it plateaus at some point, but if so, that hasn't been demonstrated).

So we've had systems that can in principle play to any arbitrary strength, if you can throw enough computing power at them. Though you might legitimately argue: by "in principle" do you mean some truly absurd amount, like more computing power than could conceivably fit in the universe? The answer to that is also no; scaling trends have been such that people expected computer Go to beat humans anywhere from, well, around now [1], to 5 to 10 years from now [2].

The two achievements of the team here, at least as I see them, are: 1) they managed to actually throw orders of magnitude more computing power at it than other recent systems have used, in part by making use of GPUs, which the other strong computer-Go systems don't use (the AlphaGo cluster as reported in the Nature paper uses 1202 CPUs and 176 GPUs), and 2) improved the scaling curve by algorithmic improvements over vanilla MCTS (the main subject of their Nature paper). Those are important achievements, but I think not philosophical ones, in the sense of figuring out how to solve something that we previously didn't know how to solve even given arbitrary computing power.

While I don't agree with everything in it, I also found this recent blog post / paper on the subject interesting: http://www.milesbrundage.com/blog-posts/alphago-and-ai-progr...

[1] A 2007 survey article suggested that mastering Go within 10 years was probably feasible; not certain, but something that the author wouldn't bet against. I think that was at least a somewhat widely held view as of 2007. http://spectrum.ieee.org/computing/software/cracking-go

[2] A 2012 interview though that mastering Go would need a mixture of inevitable scaling improvements plus probably one significant new algorithmic idea, also a reasonably widely held view as of 2012. https://gogameguru.com/computer-go-demystified-interview-mar...

This is exactly the opposite of my sense based on following the computer go mailing list (which featured almost all the top program designers prior to Google/Facebook entering the race). They said that scaling was quite bad past a certain point. The programs had serious blindspots when dealing with capturing races and kos[1] that you couldn't overcome with more power.

Also, DNNs were novel for Go--Google wasn't the first one to use them, but no one was talking about them until sometime in 2014-2015.

[0] Not the kind of weaknesses that can be mechanically exploited by a weak player, but the kind of weaknesses that prevented them from reaching professional level.

That means that the problem is exponentially hard. EXPTIME, actually. You couldn't possibly scale it much.

To be fair, a lot of the progress in recent years has been due to taking a different approach to solving the problem, and not just due to pure computing power. Due to the way go works, you can't do what we do with chess and try all combinations, no matter how powerful of a computer you have. Using deep learning, we have recently helped computers develop what you might call intuition -- they're now much better at figuring out when they should stop going deeper into the tree (of all possible combinations).

   Play strength scales roughly with the log 
   of computing power

The achivement was a leap towards the human level of play (and quite possibly over it). There might be additional leaps, which will take AIs WAY beyond humans, but none of those will scale linearily in the end. (And yeah, I guess you didn't want to say that either)

AlphaGo utilizes the "Monte Carlo tree search" as its base algorithm[1]. The algorithm has been used for ten years in Go AIs, and when it was introduced, it made a huge impact. The Go bots got stronger overnight, basically.

What novel thing AlphaGo did, was a similar jump in algorithmic goodness. It introduced two neural networks for

1) predicting good moves at the present situation

2) evaluating the "value" of given board situation

Especially 2) has been hard to do in Go, without playing the game 'till the end.

This has a huge impact on the efficiency of the basic tree search algorithm. 1) narrows down the search width by eliminating obviously bad choises and 2) makes the depth at where the evaluation can be done, shallower.

So I think it's not just the processing power. It's a true algorithmic jump made possible by the recent advances in machine learning.

[1] http://senseis.xmp.net/?MonteCarlo

This is what struck me as especially interesting, as a non-player watching the commentary. The commentators, a 9-dan pro and the editor of a Go publication, were having real problems figuring out what the score was, or who was ahead. When Lee resigned the game, it came as a total surprise to both of them.

Just keeping score in Go appears to be harder than a lot of other games.

The incentive structure of the game leads to moves that firmly define territory usually being weaker, so the better the players, the more they end up playing games where territory is even harder to evaluate.

It's obvious by just reading Hacker News.

Fitting analogy. There was a line in the film Blood & Donuts about the moon being ruined when they landed on it, which I couldn't really feel until today.

But nevertheless, fitting so much computing power in such a small device is a great achievement.

I don't think any mass comparison is really meaningful, mind, but it's not that simple.

My point is, humans "in the wild" likely didn't have any equivalent to chess, because they didn't have sufficient leisure time. Chess is a product of an environment that's just as "artificial" as the one which produced cell phones.

I think the entire analogy is stretched a little thin of the players requiring all of this, but I also think the original attack on the Go AI based on it's mass is off base as well.

The response of the Iranian sages was the invention of Backgammon, to highlight the role of Providence in human affairs.

[p.s. not all Iranians are willing to cede Chess to the sister civilization of India: http://www.cais-soas.com/CAIS/Sport/chess.htm] ;)

Plus, not far away in the future we will be able to connect an smartphone to a 3D circuit printer and print a new one, to achieve 'self-replication'

edit: according to the livestream

During the play, the computational requirements are vastly less (but I don't know the figures). It's still probably more than is feasible to put in a smartphone in the near future. Assuming we get 3x improvement in perf per watt from going to ~20nm chips to ~7nm chips (near the theoretical minimum for silicon chips), I don't think this will work on a battery powered device. And CPUs are really bad at perf per watt on neural networks, some kind of GPU or ASIC setup will be required to make it work.

> Evaluating policy and value networks requires several orders of magnitude more computation than traditional search heuristics. AlphaGo uses an asynchronous multi-threaded search that executes simulations on CPUs, and computes policy and value networks in parallel on GPUs. The final version of AlphaGo used 40 search threads, 48 CPUs, and 8 GPUs. We also implemented a distributed version of AlphaGo that exploited multiple machines, 40 search threads, 1202 CPUs and 176 GPUs.

In fact, according to the paper, only 50 GPUs were used for training the network.

This is equivalent to one person expending 500 years solely to learn Go.

Given the rules, and a big book containing every professional go game ever played, and no other instruction, it's not entirely clear to me that Lee Sedol would be able to reach his current skill level in 500 years.

For this particular example, training a system involves (1) analysis of every single game of professional go that has been digitally recorded; and (2) playing probably millions of games "against itself", both of which require far more computing power than just playing a single game.

I've seen this written by many people but is there any solid evidence/study that proves this?

Edit: seems like Pocket Fritz and Komodo are easily able to beat grandmasters.

This stuff is happening fast, and we might have found ourselves, historically, in a place of unintelligible amounts of change. And possibly undreamt of amounts of self-progression.

That's not exactly true

https://en.wikipedia.org/wiki/Limits_to_computation

Not to mention that we suddenly forgot that computers have their own units of measurement, such as clock speed (hertz) and memory size (bytes).

Is it? The problem here is it is really hard to compare the TCO. For example prime human computation requires years and years of learning and teaching, in which the human cannot be turned off (this kills the human). A computer can save its state and go in a low or even a zero power mode.

>such as clock speed (hertz) and memory size (bytes).

Which are completely meaningless, especially in distributed hybrid systems. Clock speed is like saying you can run at 10 miles per hour, but it doesn't define how much you can carry. GPUs run a far slower clock speed than CPUs, but they are massively parallel and are much faster than CPUs on distributed workloads. Having lots of memory is important, but not all memory is equal and hierarchy is even more important. Computer memory is (hopefully) bit perfect and a massive amount of power is spent keeping it that way. That is nice when it comes to remembering exactly how much money you have in the bank. Human memory is wonderful and terrible at the same time. There is no 'truth' in human memory, only repetition. A computer can take a picture and then make a hash of the image, both of which can be documented and verified. A human can recall a memory, but the act of recalling that memory changes it, and the parts we don't remember so well are influenced by our current state. It is this 'inaccuracy' that helps us use so little power for the amount of thinking we do.

Are the units I proposed perfect for the job? Of course not, just look how much you wrote. But I bet that if you do the same "thoroughly" analysis for measuring computing by weight you'll be able not only to write a fat paragraph such as your last one, you can write a whole book on who wrong/meaningless/stupid it is (not that anyone would read such book though).

But who made that machine?

I'd say a more precise evaluation would be that the ability to program a machine to assist in playing chess outdid the ability to play chess without such assistance.