Lee Sedol vs AlphaGo: How Google’s A. I machine beat the 18 times World Go Champion
It’s been 5 years since the historic match between AlphaGo and 18 times World Go champion Lee Sedol. Human vs Machine. Here’s a review of the event that has changed the face of A.I. We covered the days leading up to the match, the working of AlphaGo, the match itself, and what AlphaGo’s creators DeepMind have in store for the future.
Early Days
Demis Hassabis, the Co-Founder of DeepMind was a genius from a very young age. He is the child of a Chinese-Singaporean mother and Greek-Cypriot father, in London. At one point in his life, he was the second-highest-rated under-14 chess player in the world. To say that he had a natural attraction to board games from childhood would be an understatement. Demis went onto study Computational Neuroscience at Cambridge, and that’s where his curiosity towards understanding the human mind began.
Demis then went on to start a video game company with his college friend David Silver. He often played Go with one of his co-workers and joined local Go clubs playing against professionals. Around the same time, the IBM computer had defeated the then world chess champion, Garry Kasparov. Demis couldn’t help but think whether a machine could defeat a human in Go as well, and the idea of DeepMind was born.
Demis founded DeepMInd with his colleague and friend, David Silver. He connected with tech investors like Peter Thiel and Elon Musk and pitched his idea about a computer mastering the game of Go. Word soon reached Sergey Brin, co-founder of Google. Brin bought DeepMind at a valuation of $650 million.
During all this, DeepMind’s program had already mastered games like Breakout.
In Breakout, you try to break through the rainbow-colored wall with the help of a bat and a ball. The program has to learn everything by itself, after 100 games, the program was missing the ball most of the time. But the program slowly started to understand what it’s supposed to do.
After 300 games, the program was as good as any human player. But the most amazing thing happened after 500 games. The program had found a strategy in which the ball was bouncing off the bat at a particular angle such that it dug a tunnel around the side, and put the ball round the back of the wall, breaking the whole wall at once. The program had discovered something even the developers didn’t know about.
The next step was to conquer the game of Go. The most complex game mankind has ever seen.
What is Go?
Go is the world’s oldest, continuously played board game. It is one of the simplest and also most abstract.
Go
The rules of the game are very simple:
There’s only one type of piece. There’s only one type of move. You just place that piece on the board. And then, your goal is to create a linked group of your stones that surrounds some empty territory.
And when you surround enemy stones, you capture them and remove them from the board. You earn points by surrounding territory. And, at the end of the game, the person with the most territory wins.
The seems simple so far. But when you sit down and play, that’s when it gets tricky. You know the rules, you know what you’re allowed to do, but you don’t know what you’re supposed to do.
There are an astonishing 10 to the power of 170 possible board configurations — more than the number of atoms in the known universe. This makes the game of Go googol times more complex than chess.
The Mission
Beating a professional player at Go was a long-standing, grand challenge of AI research.
“We think of DeepMind as kind of like an Apollo program effort for AI. Our mission is to fundamentally understand intelligence and recreate it artificially. And then, once we’ve done that, we feel that we can use that technology to help society solve all sorts of other problems.” — Demis Hassabis, CEO and Co-Founder of DeepMind
And to achieve that, DeepMind invited the European Champion at Go, Fan Hui.
When Fan Hui saw the e-mail invitation for the first time, this was his reaction:
“When I see this e-mail, I don’t know if it’s true or not. I will accept this. Why not? For me, everything’s an adventure. I want to go visit DeepMind to know what is this Go project. On the first visit, I think maybe they want me to sit in the special room, push many, many wires in my head and also my body, let me play to scan my brain. I don’t know, [chuckles] to make some research.” — Fan Hui
Fan hui agreed to play a 5 match series with AlphaGo. He thought he would win the match since AlphaGo is just a “program”. Only to lose all 5 matches. The experience of losing to a program completely changed Fan Hui.
Artificial intelligence researchers have solved the game of Go, a decade earlier than expected.
Now, AlphaGo was getting better each passing day. It needed a bigger challenge. AlphaGo was to come up against the 18 times Go World champion, Lee Sedol.
Like Demis Hassabus, Lee Sedol was a child prodigy as well. He was just 8 years old when joined Master Kwan’s school of Go. He went on to dominate the world of Go for 10 years, winning 18 World Championships. Lee Sedol is a genius of the 21st century.
18 times World Go Champion, Lee Sedol
“I will not be too arrogant, but I don’t think that it will be a very close match. The level of the player that AlphaGo went against in October is not the same as mine. So, given that a couple of months has only passed, I don’t think that it is enough for it to be able to catch up with me. I hope that it will be either five-zero for me, or maybe four to one. So the critical point for me is to make sure I do not lose one.” — Lee Sedol
Lee Sedol might sound overconfident at this point, but can you blame him? Not only him, but everyone in the Go community thought that this was going to be too easy for Lee Sedol.
Working
There’s a big difference in the working of the IBM computer that beat chess champion, Garry Kasparov. The IBM Computer was programmed by expert chess players. And AlphaGo, more or less learned everything by itself.
Deep Learning
Deep Learning is a branch of Machine Learning whose purpose is to mimic the activity in layers of neurons in our brains. This is possible with the help of neural networks.
Neural Networks, imitate the web of neurons in the human brain. These networks operate on enormous amounts of data, and with the recent surge in computing power, neural networks have become extremely powerful. It teaches a computer to filter inputs through layers to learn how to predict and classify information. The inputs can be in the form of images, text, or sound.
The input provided to AlphaGo was 100,000 games played by strong amateurs, downloaded from the internet. The AlphaGo tries to imitate a human player.
Reinforcement Learning
After training AlphaGo with data from human players, the next step is to train it by playing against itself, millions of times. This is called Reinforcement Learning.
The program play against itself learns from its mistakes and improves upon them. This helps AlphaGo win games, rather than just predict the next move more accurately. Reinforcement Learning helps AlphaGo gain more experience, and optimizes its process by reducing the number of computations and memory consumptions (covered in the next topic).
Tree Search
Tree Search is an algorithm that creates all possible variations of the game and then tries to predict the outcome of the game.
For example, let’s take the classic game of tic-tac-toe:
A player wins by having their symbol forming a connection with the length of 3. The connection can be either horizontal, vertical, or diagonal.
The tree contains all the possible variations of the game, in this case, 255,168 variations. By searching through all the variations, the computer will know the outcome of the game before making any moves.
255,168 variations might seem a lot but compare to games likes chess and Go, it is negligible. Chess has 10 powered 120 variations, and Go has 10 powered 170 variations. To compute every variation is very inefficient and requires a large number of resources. Therefore, there is a need to optimize this problem.
Let’s take the previous example of tic-tac-toe:
If you rotate each variation accordingly, you will find that they’re the same variation with different positions of ‘X’ and ‘O’. By eliminating the identical variations you can eliminate 2/3rd of the search tree, making the algorithm 3 times faster.
Matchday
Fan Hui has been invited again by DeepMind, but this time as an advisor. He took the loss to AlphaGo very positively and came back to help make AlphaGo stronger. Fan Hui’s role was to find weaknesses in AlphaGo’s game. And he did. AlphaGo would go into a lump state, whenever it encounters a very specific tricky situation. This was a major setback and there was a real possibility that AlphaGo would lose the match. And the team wasn’t able to fix the problem either.
The match was going to be held in Seoul, South Korea, where Lee Sedol is a National Figure. 8 million Koreans play the game of Go, so there was a certain element of national pride involved.
In the first game, AlphaGo gave a tough fight from the very beginning. The moves that AlphaGo made were human-like, almost as if it has an intuition. Go professionals and enthusiasts were shocked by the bold moves that AlphaGo made. This was very unsettling for Lee Sedol. To make things worse, Lee Sedol couldn’t read what AlphaGo was trying to do. Because it’s a program, no feelings, no expressions.
AlphaGo made one aggressive move after another, no one could understand the reasoning behind those moves at that time. But as the game went on, it all started making sense. It was as if AlphaGo could predict the future.
AlphaGo had won the game by a big margin, no one could comprehend what had happened, it took time for Lee Sedol to accept the outcome.
“I would have to say that I was very surprised because I didn’t think that I would lose the game. I think the mistakes I made, in the beginning, lasted until the very end. That’s why I lost this game. I wasn’t able to foresee. I didn’t think that AlphaGo would play the game in such a perfect manner.
I have won world championship titles and have a lot of experience, so losing one game won’t affect me in playing games in the future. I think now it’s 50/50. I would like to express my respect to the team for developing such an amazing program like AlphaGo.” — Lee Sedol
In the second game, AlphaGo put on a commanding performance again. Lee Sedol felt immense pressure, so he goes onto taking a little break. But AlphaGo doesn’t wait for Lee to come back and goes onto play move 37. Lee comes back from his little break only to find himself confused and amazed at the same time.
“I thought AlphaGo was based on probability calculation and that it was merely a machine. But when I saw the move, I changed my mind. Surely, AlphaGo is creative. This move was creative and beautiful.” — Lee Sedol
Nobody understood whether this was a good move or a bad move. Normally Lee has to think for one or two minutes to make a move, this time he takes more than 12 minutes
The game came to a point where AlphaGo had attained an enormous amount of points. But Lee just didn’t want to resign, he couldn’t comprehend another loss to AlphaGo. After 4 hours and 20 minutes, he finally resigns.
The night before game three, Lee Sedol gathered with four Go professionals and analyzed the game all night. It was all or nothing for Lee in the third game. A loss meant that AlphaGo wins the match. But there was nothing he could do, by move 50, the win rate was already very high.
The psychological burden was adding up on Lee. He tried to fight directly in the game, but that’s not Lee’s style. When we change our style to play to accommodate the opponent, it’s not a very good sign, not just in Go, but in any professional game. This only makes it easier for AlphaGo. Again, Lee couldn’t do anything but resign. History was made as AlphaGo won three straight games to win the match against 18 time Go Wolrd Champions Lee Sedol.
4th game was a big turnaround for Lee Sedol. He had managed to outsmart the mighty AlphaGo. Lee Sedol had taken advantage of AlphaGo’s weakness. There was a sense of relief among the public and Lee Sedol. The machine was beatable after all. People were running out on the street, they were chanting and celebrating.
“But I didn’t expect it to be like this. I couldn’t believe I won one game. It was unbelievable. Thank you very much. I have never been congratulated so much for winning one game. After losing three games in a row, I couldn’t be happier.” — Lee Sedol
Lee Sedol’s move 78 was what turned the tides in his favor. According to AlphaGo, the probability that Lee would’ve played that move was 0.007%. That makes it a 1-in-10,000 move. A fellow Go professional called Lee’s move 78 a ‘God move’, something only Lee Sedol is capable of.
In the 5th game, Lee Sedol got off to a great start. He looked confident due to his previous win. The DeepMind team thought that they would lose embarrassingly. And this ‘embarrassment’ continued for most of the match. But then again AlphaGo doing some of its magic, won the match by 1 and ½ points. Just like in the rest of the matches, nobody understood what AlphaGo was trying to do. The program’s moves looked like mistakes that humans would do, yet it somehow managed to win.
Normally, we humans would consider our probability of winning a game by the margin of the score. But all AlphaGo cares about is winning, it doesn’t matter by how many points.
“It shouldn’t matter how much you win by, you only need to win by a single point. Why should I be seizing all this extra territory when I don’t need it? The lessons that AlphaGo is teaching us are going to influence how Go is played for the next thousand years.” — Frank
In the end, AlphaGo, a machine defeated the 18 time World Go champion. This match will be remembered as the event that put Artificial Intelligence in the limelight. Not only did the event change the perception of AI, but it also made the game of Go popular, all around the world. It was reported that there was a worldwide shortage of Go boards, such as the influence of the match.
“I have grown through this experience. I will make something out of it with the lessons I have learned. I feel thankful and feel like I have found the reason I play Go. I realize it was a good choice, learning to play Go. It has been an unforgettable experience”. — Lee Sedol
This wasn’t the end of something historic, but the beginning of something beautiful. Of course, Go is just a game, but we can learn important lessons from a computer being so successful at Go. Machines will have the capability to crunch through a huge amount of data and analyze it intelligently. Just as in the case of the Go games, the machine-made moves surprised even the experts. And, eventually, the machines will gain everyone’s confidence because we will see that very embarrassingly, that often they make a better guess than we could have made as humans.
What’s Next?
A lot of impactful work has been done in the past 5 years AlphaGo’s creators. DeepMind has created a better version of AlphaGo called AlphaGo Zero. How is it better?
- It is more powerful than previous versions of AlphaGo because it is no longer constrained by the limits of human knowledge. Instead, it can learn tabula rasa from the strongest player in the world: AlphaGo itself.
- AlphaGo Zero only uses the black and white stones from the Go board as its input, whereas previous versions of AlphaGo included a small number of hand-engineered features.
- AlphaGo has become progressively more efficient thanks to hardware gains and more recently algorithmic advances. Consequently, AlphaGo Zero consumes only 0.023% of the power that AlphaGo consumes.
DeepMind is working on other projects as well. Projects that are of real value to our society.
- AlphaFold is a system that accurately predicts the shape of proteins. This research has enormous potential in every field of biology, from helping tackle disease and quickly finding new medicines to unlocking the mysteries of how life itself works.
- DeepMind partnered with Moorfields Eye Hospital to develop faster ways of identifying, and better ways of understanding, common eye diseases from routine scans.
- DeepMind has also collaborated with the parent company Google on projects such as Google Assistant, Google Cloud Platform, Android Pie, Gmail, YouTube, etc.
Hey Everyone,
If you liked this article, please do give me a clap. Let’s see if we can get to 25 claps on my first article. I would like to know your thoughts about the story, so do leave a comment in the response section.
I have a few more articles in the pipeline, so give follow me to stay updated on everything A.I . What else would you like to read about in the field of Artificial Intelligence? let me know in the response section, and I’ll definitely work on it.
Thanks
