On Monday November 25, Lee Sedol , the South Korean master of go 9 dan , said in an interview that he would no longer participate in professional competitions. As the main reason for ending his sports career, Sedoll calls the appearance of computer go systems that play better than any of the people. Even if you become the best, there will still be something that can never be surpassed, says Sedol.
Outside of fan circles, Lee Sedoll gained fame for playing games against the AlphaGo system developed by Google DeepMind. Because of their characteristics, Go programs have not been able to optimize for a long time so that computers can beat people. In 2016, the British DeepMind held a match of five games, in which one of the best people - Sedol - lost to this little-known program.
Three years have passed since that game. During this time, an improved version of AlphaGo beat another champion man , DeepMind released several scientific works on the neural network and talked about the AlphaZero system , and then, it seems, lost any interest in the project. Only now Sedol decided to leave go. Are there any other reasons for solving it?
We talked about the development of computer go systems and the reasons for Lee Sedol’s deed, with 7-time European go champion, current champion of Russia and member of the Presidium of the Russian Federation go Alexander Dinerstein .
In January 2016, the usually laconic DeepMind erupted in scholarly work, a press release, and a video clip. For the first time in the world, artificial intelligence was created that is able to beat the human champion in the Asian game of go.
At that time, go was considered one of the last board logic games in which people could play better than any computer algorithm. Like chess, go is a game with full information , that is, players are aware of all the moves that other players have previously made. But if not a single grandmaster since 2005 can beat the best of chess programs, then computer algorithms in go at that time played at the amateur level.
Two players place black or white stones on a board of a certain size. The goal of the game is to fence off a territory larger than the opponent’s size on the board with stones of their color. Many of go's moves are based on intuition, which is difficult to describe with an algorithm.
The computational complexity of go is associated with a large number of possible positions and correct moves from them. The task of finding the outcome of the game is related to the calculation of the optimal value function in the search tree, in which there are b d moves. In the first, the number of correct moves is b ≈ 250, the length of the game is d ≈ 150. On a standard board, there are 19 × 19 lines of possible positions per googol (10 100 ) times more than atoms in the Universe.
Programs prior to AlphaGo relied on a Monte Carlo tree search to evaluate the value of each state in the search tree. When creating AlphaGo, deep convolutional neural networks were added to this algorithm. With the help of 160 thousand matches, the neural networks were trained from the game server go through the Internet KGS with 29.4 million positions. Additionally, AlphaGo played five thousand games against itself.
The laboratory program obtained exceeded any commercially available products and open source computer projects. AlphaGo has won 499 matches out of 500 against player programs. The algorithm had to be tested on a person, so they invited the three-time European champion Fan Hui to play against the program. In October 2015, at the London office of Google, Hui lost five out of five games to the algorithm.
At that time, this was not a final defeat. Of course, Hui is a good player, but for the European Championships. The masters of go from the main focus of the spread of the game, Asia, have the highest level. Therefore, to consolidate the result, Google announced its intention to hold an AlphaGo match against Lee Sedol, who at that time was considered the best player of the decade, in Seoul in March 2016.
Of the five games in the series, Sedol won one. Only in the fourth game — when AlphaGo’s three wins had already determined the outcome of the match — did the AI defeat.
For some reason, DeepMind programmers did not provide a dramatic message in case of a program loss.
DeepMind could be satisfied with a score of 4: 1. But inside the company continued to work. By June 2016, plans were formed to let AlphaGo play against another go champion, Chinese Ke Jie . The match was scheduled for May 2017.
On December 29, 2016, an unusually strong player under the name Magister or Master began to play regularly on a Tygem Korean server and Chinese Fox. The player won 60 games against high-level professionals. For the victory against the stranger, they even appointed a reward . On January 4, the head of DeepMind, Demis Hassabis, admitted that this player is the new version of AlphaGo.
AlphaGo Fan played against Fan Hui, who played the version against Sedol called AlphaGo Lee, on the Internet and AlphaGo Master played against Ke Jie. Each version required less and less equipment to run, but played stronger than its predecessor. DeepMind estimated that for a Fan c Lee game on an equal footing one would have to give three handicap stones, Master turned out to be three more stones stronger than Lee. It is not surprising that at the Future of Go Summit in the spring of 2017, Ke Jie lost all three games to the new AlphaGo version.
Google has not released AlphaGo source code and is not selling the program. Probably, these games are just a demonstration of the technological power of the company. AlphaGo owes its success to Google’s proprietary TPU hardware accelerator. By reducing the number of required modules, it is easy to track the increase in efficiency. The games of Fan Hui counted 176 video accelerators, 50 TPU boards were played against Sedol, only one was set against Tse.
The computing cluster that beat Lee Sedol.
DeepMind demonstrated the success of software development. To learn the first three versions of AlphaGo, the rules of the game required hundreds of thousands of lots of people, some manually set functions were incorporated into the algorithm. The AlphaGo Zero version learned to play completely independently, and the neural networks of politics and values in it were combined into one. In 3 days of self-training, Zero surpassed Lee, in 40 days - Master. In less than a month and a half, the algorithm from scratch learned to play better than people in a game whose history has thousands of years of human experience.
DeepMind has never released AlphaGo source code. The program cannot be acquired anywhere or played against it, since the spring of 2017 it has not played against people. For those who want to adopt the wisdom of AlphaGo, there are only published batches of the product . Perhaps Google does not want to associate its activities with computer go systems.
But others quickly adopted knowledge from published data. Similar in scale and scope of activities on Google, Chinese Tencent began to create its own algorithm almost immediately after the very first publication of scientific work on the Fan Hui match. Over the year, a product called Fine Art pumped a lot. Already in 2017, on the FGS server, the algorithm for the first time scored 10 dan. At the Computer Go UEC Cup computer championship in March 2017, the Fine Art program exceeded 29 algorithms and gained the right to play against the human champion and won. For its similarity with the DeepMind program, the Fine Art algorithm was nicknamed "Chinese AlphaGo."
AlphaGo Zero and AlphaZero learn not on the basis of parties of human players, but in games against themselves. Third-party developers tried to repeat these programs. The open-source project Leela Zero frankly says it is trying to recreate what DeepMind described in a scientific paper.
Facebook created its own implementation of computer go. In May 2018, the company opened the source code for the ELF OpenGo project. Trained on 2000 video accelerators, the algorithm runs on a single video card. Facebook said the program plays stronger than four of the thirty best go players in the world. And indeed, not one of the professionals is already trying to defeat this product.
Facebook also did not hide that it is based on research from DeepMind. This is evidenced not only by the text, but even by the names of scientific papers: “ ELF OpenGo: An Analysis and Open Reimplementation of AlphaZero ”. Based on ELF, OpenGo Facebook created a tool for analyzing lots of human players . Today, this program remains one of the strongest among the publicly available, many professional players analyze its own games.
South Korean company NHN Entertainment has also taken over the experience of DeepMind. The development of the HanDol program began in 2016 during a period of general interest in AlphaGo. Version 1.0 was released in December 2017, its game level was comparable to player level 9 given. HanDol 1.0 required training on the recordings of people's games, HanDol 2.0 adopted the idea of training only on games against itself. NHN Entertainment claims that HanDol Lee plays no worse than AlphaGo Lee, players say the algorithm is slightly worse than AlphaGo Master.
HanDol has also established itself as a computer system go stronger than people. By the end of January 2019, the program defeated the top five masters of 9th dan in South Korea. NHN Entertainment offers HanDol as a player training and party analysis service.
Three years after the publication of DeepMind's first scientific work on AlphaGo, there was no trace of human excellence in Go. The power of computer systems in Go does not raise questions, they are already turning to them for advice, they are learning from them. Several scientific works and dozens of games without any access to the program - but even the AlphaGo documentary was filmed on it (available in a pirated translation into Russian).
Nevertheless, more than three years have passed since the match Lee Sedol - AlphaGo. Why did Sedol decide to leave go just now?
Our questions were answered by the 7-time European champion and the current Russian champion in go Alexander Dinerstein.
At 36, Lee Sedoll interrupts his legendary 24-year career. Does it happen in Go that many professionals leave the game at the turn of 35-40 years? What is the typical way in the life of the master of go 9 dan?
This path largely depends on the country in which the master lives. In Japan, professionals often play tournaments until the last day of their lives. For example, one of the leaders of the Japanese middle of the last century Suguchi Masao (9th dan, 1920-2017) played tournament games even at the age of 97 years, although without much success. In China, professionals often end their careers and switch to coaching at the age of 35–40. Tournaments for veterans with good prizes are regularly held in Korea, so it’s not customary to resign ahead of time here.
But I believe that for Lee Sedol, who has earned tens of millions of dollars in his career, prize money does not play a significant role.
What will the Sedol live in the future? He probably decided a financial question for himself until the end of his days, but what do former champions usually do after leaving the game?
Open their schools, train children. But Lee Sedoll was not noticed. Yes, his go school has long existed in Korea and in China, but his well-known name is simply used here. Lee Sedoll himself does not teach anyone.
I heard that he went to university and decided to get a higher education, but I hope that he will not choose for himself a path that is completely unrelated to go. After all, this is the master who can convey a lot to future generations.
To mark the departure from Go, Li Sedol next month will play against the computer system go HanDol. But the champion says that he will lose the first game even with the planned two handicap stones. What are the odds of Sedoll in a game against HanDol? What form is the human player in now?
The match of 3 games will be held on a floating handicap. If Lee Sedoll loses on two stones, then you will have to play on three, and then, possibly, on four stones. But I am sure that it will not reach four stones. Lee Sedol now ranks 14th in the Korean go ranking and 54th in the unofficial world ranking, but many still consider him one of the strongest masters in the world.
Lee Sedol’s victory over AlphaGo in the fourth game of the match was largely random - Lee Sedol was far behind on points, but was able to fool the program by applying an incorrect (but with a very difficult refutation) move.
But I remind you that all the games of that match were played on equal terms. If you look at the current state of affairs, then nobody will be able to beat the strongest programs on equal terms. Professionals take 2 stone handicaps from the Chinese FineArt program (and it is considered the strongest in the world after leaving the AlphaGo arena), but on two stones the program wins about 95% of all games.
I think that it will not be easy for Li Sedol on two stones, but he must manage on three. And 4 stones is already a handicap from the category of a rook in chess. Masters on such a handicap should not lose. As far as I know, chess players so far successfully beat the program with a handicap in the knight, I think that we also have 3 stones - this is the ceiling. And no matter how much the programs progress, on 4 stones they will never be able to beat a person.
By the end of January 2019, the South Korean computer go system HanDol defeated five masters of 9 dan. Where is HanDol located: at the level of AlphaGo Lee (versions for playing with the Sedole) or AlphaGo Master (versions for playing against Ke Jie)? Does HanDol have potential against the later and stronger AlphaGo Zero or AlphaZero?
Those five games were played on equal terms. I watched them, I remember that the professionals had no chance. I think that now in the world there are several programs that could well compete with the strongest versions of AlphaGo. This conclusion can be made by analyzing AlphaGo games with modern programs. They find up to 95% of the moves that AlphaGo played, and offer to play precisely at these points.
I think that Lee Sedoll is not able to feel the difference between AlphaGo, which he fought in 2016, and modern programs. But Lee Sedola has an important advantage. Then he did not know with whom to deal, and was sure that he would win the match with a dry score. AlphaGo was not given to test in advance.
Korean professionals have never used a computer before to study go. I remember how I showed Lee Sanghong (the elder brother of Li Sedol, who also has 9 professional dan) the Ukrainian development of the early 2000s - a database of professional games with the ability to search by position. He looked at her with great surprise, noting that Koreans do not use this and keep knowledge in their heads.
And now the program is in the public domain. Lee Sedol will be able to practice, play with them on a different handicap. Yes, and the go strategy has since advanced greatly - people have studied computer ideas, trying to imitate machines. Now, when you watch modern games, it doesn’t immediately become clear who played them - the person or the program - it all became so similar in opening.
The defeat of 2016 did not force Sedol to immediately abandon go. HanDol's notable victories against Korean champions date back to the beginning of this year. At the end of 2019, without any noticeable reason, he announced his resignation.
In addition to the increased strength of the weak form of AI from DeepMind for Lee Sedol's departure from the sport, there are reasons in the form of a judicial conflict with the Korean Paduk Association regarding the financial issue of membership fees. The gray-haired man could play as part of a professional league in China or Japan, but questions of nationality made him refuse.
Is it possible to call a computer go system the reason for leaving is more of a compliment to its developers, and the real reason is more mundane? Does Sedol twist his soul?
Lee Sedoll was always harsh in his statements and actions. His dissatisfaction with the policy of the Korean Paduk Federation (go), which took away 10% of the prize money, including in tournaments played in other countries, has long been known. But this is not the money for which it is worth throwing go.
I think that Lee Sedol has a picture in front of his eyes of another legendary Korean master - Lee Changkho. The man who was considered the strongest in the world before the appearance of Lee Sedol in the arena in the mid-2000s. Lee Changho did not quit. He actively plays in tournaments, but has rolled back to 40th place in the Korean ranking.
What is curious - 44-year-old Lee Changkho does not recognize computer circuits. He plays like he played all his life. He claims that he does not use a computer and even has a phone with buttons. It seems that Lee Sedoll is not particularly friendly with computers. And the modern professional go (like modern chess) is now many hours of training with the machine, polishing options, searching for new products.
Lee Sedol, apparently, decided that here he could not keep up with the youth. Although it was possible not to give up go, but to gather a headquarters for yourself, invite professionals who love this painstaking work. With this approach, Lee Sedoll could still stay afloat.
For a chess player, Sedol’s action can cause a smile: in chess, the computer has been playing the best of people for two decades. Chess players got used to it.
The HanDol system is provided as a training service. She can beat almost any person, so she has a lot to learn.
Is it pointless to walk in the shadow of giant machines or is it enough to select smartphones at the championships? Will we now learn from programs, not wise human masters? How do you assess the future of professional go in an era when commercially available computer systems are stronger than humans?
The main negative - go lost the status of the only game in the world that the machine can not cope. And we used this slogan, even joyfully reported on it for beginners. The mystery is gone. Professionals have lost the status of gods, turning into mere mortals. Books on Go have lost their meaning - according to the programs, they teach us the wrong things. Of course, there are many cons.
But the main plus is that now it is not necessary to study in China, Korea, or Japan. In order to beat Asian professionals, now it’s enough to install a program for yourself and try to play the way it does.
But for now, however, we are not really succeeding in this. Tournaments with prizes of hundreds of thousands of dollars are still won by Asians. But Europeans and Americans, even those who "sleep in an embrace with a computer," still lose to them. But I hope that the situation will change in the future, and we will show them more!