AlphaGo

I'm still trying to digest the news of AlphaGo's win against a Go (Baduk, Weqi) professional. I read the Nature paper - which is not to say I understand it. Of course the paper is not meant to be a full explanation that I would understand of how the software works ;-) Todays is a triply off day - carnaval in Brazil, my official vacation at USP, and a snow day in Boston - so I'll take the opportunity to jot down some thoughts.

The jump in strength from what was previously achieved by Go machines was enormous. An 8-stone improvement (800 Elo, whatever) over the best programs. Incredible. That's very much unlike what happened in chess - then everybody could see the progress of machines and knew that the champion's defeat was coming.

The main questions is: what is a "convolutional" neural network, and how is it so different from a garden-variety neural network that it can learn to evaluate positions? Positional evaluation had not been achieved in any significant way by any algorithm before. Convolutional neural networks, also called "deep learning", are said to be suited for pattern recognition - although they still have to deal with the standard issues of neural networks, namely, the need for enormous training sets, and the problem of local minima in gradient search. Although there are claims that deep learning deals with local minima effectively. The main question though is more subtle - who expected that Go positional evaluation is amenable to pattern recognition? What is the topology of a winning Go board? How did AlphaGo figure it out, as it is clear that no human did?

There are 3 hypothesis:

1 - Go turns out to be significantly easier that we had thought. That rhymes with the idea that chess books are (used to be, before machines) a lot better - more fun - than Go books. Chess books used to talk about real strategic insights - until all the insights became available: then they devolved into a morass of listings of 30 move long openings which are almost like exhaustive searches. Lasker wrote "Chess must not be memorized... You should keep in mind no names, nor numbers, nor isolated incidents, not even results, but only methods." That worked 100 years ago, but it turns out that memorizing works better now.

Go books range from the soft, metaphysical, to the exhaustive lists of josekis and tsumegos. Now this might be explained away by saying that "we don't understand the mysterious ways of Asian culture" but this explanation is nonsense. Conceivably chess had found the deep tactical insights which are halfway between the vague and the overly concrete, and Go was still jumping from one extreme to the other. Is that because chess had been better studied? Or because Go is more complex, less structured, and thus less amenable to literary description?

Chances are we will never know. The most likely explanation is that the secrets of Go are hidden more deeply than those of chess, yet not so deep that computers cannot find them. But there are others.

2 - Artificial intelligence is advancing faster now. After 50 years of having been the technology of the future for now and all ages. Maybe. This is the 1st AI (defined in broad terms) advance that is unexpected. Do you remember another one? I don't.

Of course Go WAS more complex than chess and took a while longer to solve; but now computers are more powerful and the advances come faster. I don't much believe this line of reasoning but we cannot discount that the pace of advancement in artificial intelligence will quicken. This hypothesis is testable: just wait 5 years and see if other, bigger problems fall. The technological singularity folks would be happy, but don't really think it will happen.

3 - Least likely explanation: well, most published research findings are false. The disagreement is on the meaning of most - my favorite estimate is 92%. Every field has its way of being false - outright fraud is rare except in the medical sciences. In engineering, false tends to mean that the conditions assumed in the paper never happen in the situation to which it wants itself applicable. But I digress.

The reason this alternative is unlikely is because if there is something false in the publication it will get checkmated, just as Lasker said of hypocrites (he actually meant anti-semites) on the chessboard. Now again I cannot evaluate the publication, and I much doubt that it is meant to be evaluated the way mathematicians check proofs in peer review. But I did look at a commented game - again I cannot compete with the pros - and one cannot imagine how the computer was playing if it wasn't running a very good algorithm.

So hypothesis 3 is the least likely - not that I put it above any scientists to punish false results, or that science depends on individual honesty or competence - but it's the most easily testable. Pity, because at some level it would be the most satisfying - another 10 or 20 years of gradual improvement in Go playing would have been fun to watch.