After AlphaGo's match against Lee Sedol, I saw a lot of news that had headlines like Google's AI Masters the Game of Go a Decade Earlier Than Expected. To me it feels like these headlines are trying to get the reader to think: Why did experts think that this achievement was a decade away, when actually it was going to happen within a year?

Let's step back for a moment and think about a simpler problem. I'm going to roll a regular six-sided die repeatedly. After each roll, you're going to predict how many rolls it will be until I next roll a 6. So if you say 1, and the next roll is a 6, then you're right. How do you make your predictions? Take a moment to think of a method before reading on.

Let's imagine you see the following sequence of die rolls:

6 3 2 1 5 3 6 6 2 6 2 5 6 4 3 5 4

How long will it be until the next six?

Unfortunately, I have no way of knowing what you decided on, so let's imagine someone with the following thought process:

• On average, a six appears one in six rolls.
• Therefore, on average, there should be five non-sixes between two consecutive sixes.
• There have been 4 non-sixes since the last six.
• Therefore, I will predict that there will be one more non-six, so the next six should appear after two more rolls.

What does this person predict when there have been more than five non-sixes since the last six? Let's suppose that they predict that it will only take one more roll (i.e. the next roll will be a six).

So this person will make the following predictions:

      Roll: 6 3 2 1 5 3 6 6 2 6 2 5 6 4 3 5 4
Prediction: 6 5 4 3 2 1 6 6 5 6 5 4 6 5 4 3 2

Actually, this sequence came from a much longer sequence that I generated:

      Roll:  6  3  2  1  5  3  6  6  2  6  2  5  6  4  3  5  4
Prediction:  6  5  4  3  2  1  6  6  5  6  5  4  6  5  4  3  2
    Actual:  6  5  4  3  2  1  1  2  1  3  2  1  13 12 11 10 9

      Roll:  3  4  5  1  1  1  3  3  6  1  2  4  6  3  3  3  5 
Prediction:  1  1  1  1  1  1  1  1  6  5  4  3  6  5  4  3  2 
    Actual:  8  7  6  5  4  3  2  1  4  3  2  1  17 16 15 14 13

      Roll:  1  4  2  5  1  2  1  1  1  5  1  2  6  1  6  3  
Prediction:  1  1  1  1  1  1  1  1  1  1  1  1  6  5  6  5
    Actual:  12 11 10 9  8  7  6  5  4  3  2  1  2  1  3  2

Look at those long streaks of ones! This strategy sometimes is dead on, like the very beginning of this particular sequence, but most of the time this predictor sounds like someone who believes the gambler's fallacy too much.

So what about someone who has a different thought process?

• On average, the first six will appear on the sixth roll.
• The behavior of the die is independent of the past.
• Therefore, I will predict that the next six will come after six more rolls.

Let's take a look on the same sequence:

      Roll:  6  3  2  1  5  3  6  6  2  6  2  5  6  4  3  5  4
Prediction:  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6
    Actual:  6  5  4  3  2  1  1  2  1  3  2  1  13 12 11 10 9

      Roll:  3  4  5  1  1  1  3  3  6  1  2  4  6  3  3  3  5 
Prediction:  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6 
    Actual:  8  7  6  5  4  3  2  1  4  3  2  1  17 16 15 14 13

      Roll:  1  4  2  5  1  2  1  1  1  5  1  2  6  1  6  3  
Prediction:  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6  6
    Actual:  12 11 10 9  8  7  6  5  4  3  2  1  2  1  3  2

Well with this predictor, every time a six is rolled, you can say "Oh, look at how far off they were!" And if we were particularly adventurous, we might say that every single roll of a six took the predictor by surprise. But actually, this predictor is much closer to the truth of the matter. Regardless of history, the expected number of rolls until the next six really is six.

Going back to the real world, solving a popular unsolved problem is a lot like rolling a die (though with a lot more than six sides). If a problem has been attempted by a large number of people with no success, then probably the solution will require something new. In other words, solving the problem represents a breakthrough.

How can you possibly predict when a breakthrough will happen? Really, it's a lot like rolling a die. On the path to the eventual solution, many ideas will have been tried without success. There's certainly some degree to which you can judge how likely an idea is to work, but really nobody knows until it's tried.

In the case of computer go, the real prediction was that a professional-level program would be the result of a breakthrough. Saying that it would come in a decade is really just saying that you'd expect one such breakthrough every ten years.

One of those breakthroughs came with the advent of Monte Carlo Tree Search around 2006 or 2007. Before that, programs were not even 1 dan level. You can see that this one breakthrough allowed for huge improvements in the skill of these programs, and over the next few years the top ones climbed up to about an amateur 6 dan level.

AlphaGo's structure seems to be another such breakthrough. Other go-playing programs have started integrating neural networks in similar fashion, and Zen has recently hit 7 dan for the first time on KGS. With one breakthrough in 2006 and the next in 2016, ten years as the average breakthrough time seems plausible. Maybe those people predicting a decade were on to something.