Todd's Place
I don't do these:
  • Last Seen
  • Blog
  • Contact
  • Air Quality

How did AlphaGo do it?

3/13/2016

0 Comments

 
I want to give you a feel for the fight. I've watched all four matches now, with commentary, in their entirety. These take 4-6 hours each. We are fortunate to be living while this great battle took place. However we are even luckier that we have analysis from Michael Redmond, the first and only non-Asian, 9-dan player in history...and he's an American! I've studied enough Go to barely understand his simplified commentary. I'm not an expert nor even an amateur of any rank. However, I hope to entertain you, by trying to explain some fun observations from these historic matches. Here is the best short blurb i've found, introducing Go to a layperson. Let's get a little background next.
​

AlphaGo vs Fan Hui

In October 2015, the european champion, Fan Hui, was beaten 5-0 by AlphaGo. Again, Fan Hui is a 2-dan ranked professional player, with 9-dan being the highest possible rank. Go is a popular game in Asia, with many more players there than in the US. The dan ranking system is highly nonlinear, and Fan Hui is an amazingly strong player. While this was impressive, various 9-dan players were unimpressed by AlphaGo's play. It was considered "too conservative" and it "made too many mistakes". Lee Sedol, a top-ranked 9-dan world champion was the obvious next opponent. Based on AlphaGo's performance against Fan Hui, Lee Sedol remarked that he wouldn't lose a single match to AlphaGo. Unfortunately, Lee did not take into account that AlphaGo was currently being massively improved, month-by-month, in a secret Google skunkworks. The AlphaGo that Lee would encounter later, is an immensely more powerful threat.

How did AlphaGo do it?

If you asked most experts two years ago, they would have predicted AlphaGo could not beat a player as strong as Fan Hui. There are certain kinds of moves which you can't compute by analyzing locally. Humans describe Go patterns and moves in a rich vocabulary of "shape", "thickness", "power", "influence", "small", "big", and hundreds of other terms which are Japanese. One such kind of move is inscrutable, to both computers and laypeople, namely the "big" move. If AlphaGo could understand this type of move, it could understand lots of other advanced Go concepts.

While it is easy to imagine AlphaGo being able to master some local moves (called "small" moves in Go), there are mysterious "large" moves, often very far from the current fights on the board. Especially in the beginning, smaller fights break out in the corners, since you can secure territory in corners more easily; you only need two sides of a rectangle to secure a corner. Then fighting moves towards edges, which can be secured with three sides of a rectangle. It is uncommon and difficult to win by attacking the center, as you need to secure all four sides from your attacker.

The goal in Go is simple, try to link your stones to surround and secure the most territory. I used to play and study Go. I've read several books on common patterns (called "joseki") and graded Go problems. I played a dozen games a week for years and was undefeated in rural, farmland PA. Once I got to graduate school, I played against a Chinese graduate student in my lab, and never won a game against him, even with free stones as a handicap. He was a good, amateur-level Go player in China. He knew how to do big moves. 

We'd start by putting some stones near corners, then we'd start duking it out in a particular corner. We were fairly even here. I had studied, and if you can look ahead a few moves you'll do OK. In Go this is called "reading". We would be settling in to a slow exchange of small moves, when, all of the sudden, he would place a stone on the opposite side of the board. I knew that was a big move, but it was completely inscrutable. Many, dozens of moves later, we'd be fighting somewhere else, and that one isolated stone would be in perfect position to destroy my attack! This happened over and over again, game after game. It was not an accident.

Clearly, Go players don't play big moves with an understanding of how the board will look, 100 moves later. Instead, they study how smaller patterns, standard joseki, interact with each other, sometimes clear across the board. This takes years of study in dedicated Go schools, where nothing else is taught. Most great players start early as children.

It should be clear by now, that just looking ten or twenty moves won't work in Go. Those computations would overwhelm all the computers on earth, and still not get you the big moves. For small moves, however, you have to have some capability to "read" the board. AlphaGo combines (monte-carlo) tree-searching for small moves with a neural network for big moves. Actually, there are lots of sub-systems in AlphaGo, but those are the main two. The neural network takes many, many games as input, and then "learns" how to predict human moves, especially big moves. The neural network needs a ton of data, more than all games played in history. Once it had exhausted all games in history, then it had to generate over one million games per day, playing itself! So there was a phase where AlphaGo was training itself with human games, supplementing this training with self-played games, leading up to the match with Fan Hui. This worked well, so they added more layers of processing, more computers, and then they let that new system play itself for months. This was the vastly stronger AlphaGo that Lee Sedol encountered. It's a total beast.


0 Comments

Your comment will be posted after it is approved.


Leave a Reply.

    Author

    I'm an applied-math-research Ph.D. and serial startup founder. I am a recognized computer security expert, fortunate to join the ranks of many, great CTO's. I've founded and seed-funded multiple, successful, VC-backed companies. I'm still at it!

    My wonderful wife and I moved from New England to near the Portland Oregon area. We LOVE the Pacific Northwest, and we've been here a few years now. We have an adorable baby girl, Vivi.

    People here are nice and smile a lot. Vegetables are insanely delicious. Driving is not like Mad Max.

    This blog is very Vivi-centric. Our family just can't resist. :) Also, there are some stupid hacking and geek tricks.


    Archives

    December 2020
    November 2018
    October 2018
    September 2018
    April 2018
    March 2018
    February 2018
    January 2018
    December 2017
    November 2017
    October 2017
    September 2017
    August 2017
    July 2017
    June 2017
    May 2017
    April 2017
    March 2017
    February 2017
    January 2017
    December 2016
    November 2016
    October 2016
    September 2016
    August 2016
    July 2016
    June 2016
    May 2016
    April 2016
    March 2016
    February 2016
    January 2016
    December 2015
    November 2015
    October 2015
    August 2015
    July 2015
    June 2015
    May 2015
    April 2015
    March 2015
    February 2015
    June 2014
    April 2014
    March 2014
    January 2014
    October 2013
    April 2013
    March 2013
    February 2013
    January 2013

    Categories

    All

    RSS Feed

Copyright 2012-2021  Todd Brennan