Those who are interested in Go – board fighting games, wondering how can an AI algorithm win the minds of the greatest player in Go game? This article is the answer to this question.
Go has a long history, and is one of the oldest board games to still be in play today. The rules of Go are pretty simple, focusing on surrounding a larger territory than that of an opponent. In a game of Go, there will be black and white pieces, or in more accurate terminology, black and white Go “stones”. All the stones are of the same shape – either convex on both sides or flat underneath and convex on top. A standard Go board will be marked with a 19×19 grid, and there were also other sizes like 13×13, 9×9, or even 17×17 in historical times.
Players will take turns placing the stones on vacant points on the board, which are intersections of the marked grid. Once placed on the board, stones may not be moved. However, they can be “captured” and removed from the board, if surrounded by opponent stones at all adjacent points. A game of Go will end when one party resigns, or when there are no further moves to be made. When a game concludes, the winner is determined by counting each player’s surrounded territory along with captured stones and komi (points added to the score of the player with the white stones as compensation for playing second). The side with a higher score will be named the winner.
Go rules are relatively simple, yet strategically-wise, it is an extremely flexible game – you know exactly you can do, yet completely confused as to what to do in an actual game. Compared to chess, which has 20 possible moves each turn, the total number of possible moves in Go are completely overwhelming at 200. And if you try to calculate the total number of moves across the board, it will surpass the total number of molecules in this universe. As such, it is extremely challenging to program a Go-playing AI.
2. DeepMind and AlphaGo
DeepMind (or Google DeepMind after Google purchased the firm in 2014) is a British AI company, established in September 2010, under the name of DeepMind Technologies. Since January 2014, after being purchased by Google, DeepMind had started in-depth AI projects in collaboration with the tech giant. Now, Dr. Demis Hassabis is the CEO and founder of the company.
AlphaGo is a computer program developed by DeepMind to play Go. Before 2015, even the best Go-playing programs can hardly defeat an amateur. In fact, through decades, most people believe that Go is too innovative and complex for computers to master. And what makes AlphaGo stands out from all the previous AI attempts is that: AlphaGo utilizes artificial neural networks, which can solve problems via evaluating, testing, and drawing experience, without stiff encryption by human, but rather relying on self-study by the program itself – through millions and millions of Go games, and even more playing against itself.
3. The historic match between AlphaGo and Lee Sedol
First, let’s explore a little about Go ranks and ratings. In particular, Go ranks are separated into the amateur system and the professional system, and terms like kyu and dan is used in ranking. The highest level possible to achieve by a professional player is 9-dan (9p).
In October 2015, AlphaGo had defeated the European Professional Go Champion Fan Hui, who was a 2-dan (2p) professional player at the time. This is the first time an AI had defeated a human professional player in a standard 19×19 game without a handicap. The overwhelming defeat (5-0 to AlphaGo) of Hui had shaken the world of profession Go, who started to have doubts about the actual prowess of AlphaGo. They raised questions like “What is the actual prowess of AlphaGo?” and “How long till it defeats the world’s top players?” It is these questions that push those behind AlphaGo to continue improving it, as they want to push AI algorithms to their limits, watch the learning process, and see how far can it go. To test this, DeepMind professionals need to find one thing: a stronger opponent.
Lee Sedol is a 9-dan professional player (the highest rank in Go) from Korea. He is a hero, pride of this nation, and is one of the strongest players in the history of Go. Lee Sedol started to compete professionally since he was 13 (first dan rank was at 12), and had dominated the world’s Go scene for over a decade, belting 18 World Championships. And DeepMind had selected Lee Sedol, for they wanted a legendary player, who acknowledged the best in the past decade.
Regarding this special match between AlphaGo and Lee Sedol, Demis Hassabis had said: “This is a historic moment in for both AI and Go. Until now, AlphaGo had been able to overcome all challenges we have set. Yet, we cannot know its real power, until this battle with a world’s top player like Mr. Lee Sedol.”
Fan Hui also commented: “Lee Sedol is face pressure from the entire world. Before, he competed for his nation, for himself. But now, he is competing for the sake of humanity and our wisdom.”
Contrary to expectations, Lee Sedol expressed his confidence regarding the match. He believed that human intuition is not easily overcome by AI, and hoped to win 5-0 or 4-1 over AlphaGo.
Into the real battle
The DeepMind – Lee Sedol event lasted from March 8, 2016, to March 15, 2016, at the Four Seasons Hotel in Seoul, Korea. The battle’s commentators were Michael Redmond (9-dan) and Chris Garlock, with 5 live matches on March 9, 10, 12, 13, and 15 respectively, attracting 8 million audiences from the Korea Go Union. The battle is under Chinese Go rules, with 7.5 komi points. Each match is limited to 2 hours, before going into byo-yomi, where each player will a maximum of three 60-second moves before the match ends. Aja Huang was DeepMind’s representative, who placed for AlphaGo.
So, did Lee Sedol defend humanity, or did AlphaGo created history?
1st Match 1 (March 9, 2016)
In the first match, AlphaGo controls the white stones, and Lee Sedol, with the black stones, moved first. Lee had the upper hand during most of the match, but AlphaGo surpassed him in the last 20 minutes, and Lee Sedol resigned. The match ended after 186 moves, with Lee making grave mistakes at Black 123 and Black 129, which made him unable to overturn the match. He blamed himself for the moves the moment the match ended.
2nd Match (March 10, 2016)
AlphaGo (Black) moved first this round and had continued its winning streak. Later after the match, Lee Sedol had said: “AlphaGo has got an almost perfect match.” In particular, move No. 37 of AlphaGo is regarded as extremely innovative and unique. AlphaGo had showcased distinctive moves, with a forward insight. In fact, most professional Go players though the move to be a mistake, before realizing the intentions behind it.
3rd Match (March 12, 2016)
In this match, the white stones belonged to AlphaGo. The match was extremely convincing, and the AI played intimidatingly strong. The match ended after 176 moves, and AlphaGo had made history with 3 consecutive wins against Lee Sedol.
4th Match (March 13, 2016)
The fourth match was special in that it was Lee Sedol’s first win against AlphaGo. In fact, after 3 consecutive wins, the commentator Chris Garlock had to exclaim: “Does AlphaGo even have any weakness?” However, this round, AlphaGo had made the mistake of being overly confident. Lee Sedol’s 78th move had been called “magical” (Lee Sedol magic!) and AlphaGo had made a mistake immediately after that. In the end, after 180 moves, AlphaGo had to resign. This was extremely meaningful to Lee Sedol and his supporters, as it shows that, in front of AI, humans could still retain his robust intelligence, even though the future would be challenging.
5th Match (March 15, 2016)
According to Fan Hui, in the 5th match: “It seems that Lee Sedol’s weaknesses were resurfacing, and he made some extremely bad moves.” The match ended with AlphaGo’s win after 280 moves.
4. The lesson from AlphaGo
- Nam Chi-hyung (Go Research Professor – Myongji University): “We had talked a lot about AlphaGo’s unique moves, which seems to be mistaken. Yet as the match ended, we have to doubt ourselves as well as our judgments.”
- Frank Lantz (Head of Game Center – New York University): “To me, the most interesting thing that I learned from the game is AlphaGo’s ‘lay-low moves’. Alpha had taught us that, we are too reliant on scores, and are focusing on that for victories. At some points, you can surround more, and get more points, and I am losing with fewer points, but that does not necessarily mean you will win. Maybe I only need one move to overturn the battle. So why should I try to gain more unnecessary territory? That was what AlphaGo wanted to change in our perspective of the game in the future.”
- Lee Sedol: “What surprised me was the way AlphaGo made those moves that we thought were innovative, yet were extremely mundane to it.”
DeepMind utilized neural network technology – which simulates the human neural network, in AlphaGo. Therefore, AlphaGo could learn to play Go on its own by analyzing millions of previously made moves. Then, combined with reinforcement learning, it played against itself to improve further. These matches helped to create new moves that the computer can use to re-train itself, and as such, the moves are not entirely human. This means that AlphaGo does not play as humans do, but in fact, do so completely different.
The final result of 4-1 to AlphaGo is an important landmark in AI research. It had destroyed the notion that “machines cannot defeat humans in Go,” and since had come to a motivation for DeepMind experts to continue developing later, upgraded versions like Alpha Zero and Alpha Star.
Video about AlphaGo’s journey of defeating the best Go player:
Vu Duy Long – FPT Software
FPT TechInsight is now officially introducing the new corner – “READER OPINION”, where you can share your own writings on new technologies, programming experiences, previous projects… to the tech-lover community. Quality posts will be selected to publish on the FPT TechInsight’s website, with attractive royalties sent to the authors, as thanks for their contributions.
We welcome all contributing ideas and writings sent to: [email protected]. Please clarify in the email title as “Reader opinion – Full name”. Hotline: +84 853 543 538