AlphaGo vs. Lee Sedol: Results and Evaluation of Professional Go Players
Yesterday, the last fifth game of the Go match was held at the Four Seasons Hotel in Seoul. Each of them was covered at Geektimes for a week. In the series, someone won, but this would hardly be of interest to a visitor to a Russian-language site about high technologies and science, if not for one fact.
Played Lee Sedol, owner of the ninth professional dan, one of the best go masters in the world. His opponent was the AlphaGo computer go system, developed by Google DeepMind. Before the match, it was believed that no single product could beat the high-level master. But AI won with a score of 4: 1.
The speed with which AlphaGo honed the go is interesting. Even last October, the system for a demonstration match fed the player much weaker. Five months later, she goes around one of the best. It seems that we reached 1997 in chess, when the computer first beat the defending champion in the match. Since then, chess programs have improved their skills to such a level that a person is no longer able to win them in normal conditions.
')
Does this expect go? Should I be afraid of the power of artificial intelligence? I was able to receive comments and answers provided by the Vice-President of the Russian Federation of Go and the President of the Sports Federation of St. Petersburg Maxim Podolyak, professional go players and multiple European champions Ilya Shikshin (first professional dan) and Alexander Dinerstein (third professional dan).
The difficulty of go
This victory can be compared with another historical match. In 1997, the supercomputer Deep Blue for the first time in the world beat the current world chess champion in a match. The loss of Kasparov did not become the last defeat of the people. In subsequent years, computer-chess reached a point when even the strongest of chess players cannot beat them in normal conditions.
Go (baduk, Weiqi) is a board game that originated in ancient China and gained considerable popularity in South Korea, China and Japan. Today , about 60 million people play go. Players place stones of two colors on the board of a certain size. The goal is to fence off an area larger than your opponent on the board.
The President of the International Chess Federation, not without pleasure, says that now the fate of chess awaits him.
From the point of view of creating AI, with external simplicity, it is many times more difficult than chess - a googol ( 10,100 ) times, to be more precise. It is so many times more possible positions of stones on a standard 19 Ă— 19 board than in chess. Before the advent of AlphaGo, it was believed that for the time being, any programs were playing at the level of amateurs, and up to the level of masters, for another decade.
Board size is not the only obstacle. Many algorithms that were used for chess are not applicable. The number of moves is greater than in chess. The game starts with 55 possible moves, and soon almost all of the 361 points on the board need to be considered. Some of the moves are more popular, some are almost never used. The initial moves of the game - fuseki - quickly begin to go off into something original. In chess, pieces move away from the board, they are added to go (even if it is possible to remove them by capturing stones). This excludes the creation of a database of party endings Existing systems do not cope well with the end of the game, including this because of the co-fight.
Computer go systems do exist. Most often, such products evaluate moves using a tree search or a Monte Carlo method, use expert systems with a base of good moves, pattern matching and machine learning. Products like Crazy Stone, Zen, or GnuGo may show good results, but they still lose to professionals.
In 1989, Goliath was unable to beat amateur sixth dan with a huge handicap of 17 stones. Before AlphaGo, the highest achievement was the gain with 4 odds stones. This year, waited for a reduction to 3 odds stones. But suddenly there was a system that won out against champions on equal terms "dry".
Forces of the parties
Alphago
Age: less than 2 years
Country: United Kingdom
Dan :?
In 2014, Google bought DeepMind, a British artificial intelligence company. It was DeepMind that in the past attracted attention by creating artificial intelligence DQN, who independently learned to play 49 old Atari games . When describing another product of the company - AlphaGo - you can also use the word "independently".
This computer go system consists of a simple combination of the Monte Carlo method and neural networks of policy (policy networks) and value networks. Neural networks were trained in several stages of machine learning with the help of 160 thousand games with 28.4 million positions from the KGS server of players from the sixth to the ninth dan. Another million items were allocated for tests. At first, supervised network policy training was carried out directly using the moves of the human players. Another policy network underwent training with reinforcements. The second one played with the first one and optimized it so that the policy shifted to winning, and not just the predictions of the moves. Finally, training was conducted with a reinforcement of the value network, which predicts the winner of the games played by the policy networks. The result of a correct prediction of the next move was achieved in 57% of cases. Before AlphaGo, the best result was 44%.
AlphaGo was compared to other programs — it almost always beats all competitors — and the human player. To this end, with the participation of a judge from the “British Go Federation”, a match was organized against a three-time European champion and second professional Dan Fan Hui. All five games Hui lost.
Lee Sedol
Age: 33 years
Country: South Korea
Dan: 9 professional
Another participant in the match is a professional player in Go Lee Sedol. Sedol received his first professional dan in 1996 at the age of 13. The saddle has 18 international titles, it is one of the five strongest players in the world.
AlphaGo beat the European champion, where go levels are lower. At the same time, mistakes were made both by the program and by Hui. Not surprisingly, Cedol quickly accepted the challenge and agreed to play against AlphaGo. Lee said that he will easily win with a score of 4: 1 or 5: 0. After two or three years, Google will want to take revenge, and then it will be more interesting to play, said Sedol.
Course of events
From 9 to 15 March, a match of 5 games was held at the Four Season Hotel in Seoul according to the Chinese rules, where White’s compensation for Black’s first move (Komi) is 7.5 points. The winner of the match received a reward of $ 1 million. If the AI ​​wins, the prize fund goes to charity: UNICEF, go development organizations and others.
Attention to the games was significant. Technical need forced Google to lay a fiber-optic communication line to the hotel. The search giant did not send to Korea 1920 processor cores and 280 video accelerators, which started the AI. Instead, communication was established with the Google Cloud Platform servers somewhere in the Midwest. The stones on the board for AlphaGo were set by the operator Aja Huan (the sixth amateur dan).
The match was attended not only by the head of the unit, Demis Hassabis, but also by Google’s former executive director Eric Schmidt, as well as one of the company's key engineers, Jeff Dean. Go is a popular game in Korea. The match effortlessly made its way to the front pages of Korean newspapers, attended by members of the Korean parliament. The games were broadcast in Korean, Japanese, Chinese and English. Only English on YouTube broadcast watched an average of 80 thousand people.
At one o'clock local time, the first game began. Black played homework, and in seven moves the combination had to go beyond any base. Sedol demonstrated his typical style and attacked . But AlphaGo was not holding back - the system began to attack in about 12 stones.
According to commentators, AlphaGo played like a man: the system was looking for and creating vulnerable groups of stones to make strong moves. Although the AI ​​made some mistakes, blacks had good reasons for concern. In the last twenty minutes of the game, AlphaGo has developed an advantage. The game for 3.5 hours ended with the ninth dan master admitting defeat.
As Sedol said later, AlphaGo made one unusual move that no single person would have done. A representative of a team of people did not expect such a game. The system played noticeably stronger than against the European champion. As the head of DeepMind Hassabis said, the matter is not even in computing power - they are about the same as in the match against Hui. For the past five months, AlphaGo has played itself against itself and has used reinforced training to improve its own skills. Increased power came as a surprise.
Has the strength of the game and style improved after the match with Fan Hue in October 2015? All three commentators agree that there are significant changes. Ilya Shikshin, says that the program has noticeably increased its skill since October from the level of play of the European champion to the level of the world champion:
“I must say that this is a significant difference. The published batches of the program against Fan Hui left great doubts that AlfaGo would be able to defeat Lee Sedol. But during these few months the program has managed to make a big leap. ”
“Lee Sedol did not know with whom he plays. And the fact that he, in the first game, tried to provoke a program to make a mistake with the help of a non-standard first moves - this is what testifies to this. Instead of trying to find weaknesses in the program, he should have played his normal game. In this case, it would not be obvious who would win. ”
Alexander Dinerstein noticed the game of two different versions of the program. The version that played with Fan made much more mistakes.
After the first game, Sedol admitted that he was shocked, but he was optimistic: he believed that the opening moves would make it possible to achieve greater chances of victory. The second game made the outcome of the match more expected.
The AlphaGo system played black, that is, went first. AI made aggressive moves. The beginning was unusual. Commentators could not say whether it is bad or good. White played more conservatively.
Neural networks are not configured for maximum points. The program is looking for moves that will achieve victory. DeepMind researcher Thor Grapel explains strange solutions to this. Between the move, which will give a gain with an advantage of 80%, and another one, which will allow to win in 99 percent probability with a advantage of 1.5 points, AlphaGo will choose the last one. Sometimes the system loses points, but it only improves the chances of winning. Does this mean that weak moves are a sign of a car’s confidence in victory ?
In the first game, Sedol had time on the clock. This time he exhausted him, so the man had to spend just a minute on the course. By the end, AlphaGo had exhausted its time, so the speed of the exchange of moves accelerated to the limit. But not for long - the whites admitted defeat. As the head of DeepMind Hassabis said, AlphaGo was confident of winning somewhere else from the middle of the game.
Could DeepMind take into account the features of a particular player and lay its characteristics in AI? Maxim Podolyak says that the technical capabilities were:
“Since the base of professional games is in the public domain, it would be surprising if they were not used in the preparation of AlphaGo. Thus, it can be expected that the program has a detailed profile for all professional players, since its construction is not fundamentally different from the construction of a user preferences profile. And in this Google is strong. "
A similar point of view is expressed by Ilya Shikshin:
“I am sure that all publicly available games of Lee Sedol (over 1000) were uploaded to it. Knowledge of these parties and the possibility of reproducing them at any time could have given the program an advantage, while prior to the match, Lee Cedol could only study the games of the program against Fan Hui, where the AlphaGo level was significantly lower. ”
However, DeepMind says that AlphaGo was not reconfigured specifically for Lee Sedol. And it is hardly possible to make big changes in the neural network by running several hundred batches.
March 12, Saturday. Third game
From left to right: DeepMind founder Demis Hassabis, ninth professional dan owner, Lee Sedol, Google co-founder Sergey Brin.
The ability to decide the outcome of the match in this game has already attracted attention to the party. Google co-founder Sergey Brin flew into Seoul without a pomp and visited the game. It was obvious that victory is a demonstration of the power of technology that underlies the search giant. From advertising preferences to robo-mobiles who can move independently, almost everything Google’s relies to some degree on systems with elements of artificial intelligence.
As in the first game, Sedol went black, that is, the first. The experience of two parties could also be attributed to the number of moments favorable for a person. Rumor claims that Sedol and a team of go experts spent the night in search of AlphaGo's weaknesses. Alexander Dinerstein agrees with this:
“I heard that Lee Sedol didn’t sleep at night analyzing the games and preparing for the match in the company of his colleagues - Korean go professionals. Weaknesses of the program were found, but could not be used. It seems to me that he had to play more actively. With wrestling, as he usually does. The peaceful go that we saw throughout the match was not his strong point. ”
Indeed, in the third game, Black’s first moves were aggressive. As the match commentators said, in the first two games, Sedol tried a different style from his usual one, trying to put pressure on the weak points of the system. In the third game, he demonstrated his typical style with a good start and strong in the end. Albeit with an error, AlphaGo showed the ability to work with co-struggle - usually computer systems with a similar poorly cope. In previous games, there was no chance to demonstrate this skill.
The decisive party determined the historical value of the incident. This was AlphaGo's third win in a five-game match. This meant that the computer system had already demonstrated a victorious superiority. Two subsequent games should have shown its depth.
After the third defeat of a person at one of the press conference topics , the question was whether AlphaGo has any weak points. Sedol mentioned how he felt they were. He apologized to the Korean nation and the go community for showing the result.
Sedol chose the amasy strategy, capturing the territory around the perimeter, not the center. White's opening moves were the same as in the second game. White gave Black to capture the center, concentrating on the edges and corners. As in previous games, Cedol exhausted his time before his opponent, which meant only a minute per move.
78, White’s move was so great that commentators described him as tesuji, some called him “the hand of God”. Perhaps Sedol really felt the weak point of the computer system. AlphaGo responded weakly. According to the head of DeepMind Demis Hassabis, on the 79th move the system made a mistake, considering that the chance of victory is 70%. But she understood it only on the 87th move. After that, the AI ​​got confused.
AlphaGo began to make frankly weak and horrible moves. The system acknowledges defeat when the assessment of a chance of victory drops below 20 percent. About this, Google engineer David Silver recalled during the break, which took Lee Cedol. This is necessary in order to preserve the culture of the game - it would be disrespectful to the opponent to continue in a clearly unprofitable position. Silver declined to comment on a series of obscure moves of the system. The game continued, and Sedol still had to work in the conditions of lack of time. AI made another mistake, and later admitted defeat. The result of the confrontation for 4.5 hours was the first victory of a person in this match.
Sedol said that he had never been congratulated so much for just one win. He mentioned that the car is not so strong when it goes black.
Black began in a style similar to the first game. Then Sedol tried to mark the territory in the upper right and left corners - a strategy that he successfully used in the fourth game. AlphaGo picked up the center. From 48 to 58, the man and the car went on a par. But AlphaGo did not see the Tesuji black, and Lee took the lead.
Due to a small error, AlphaGo slightly worsened its position. As a result of a long battle, both players ran out of time, that is, they again had to place each stone in less than a minute. The game went into a deep yose, the board was almost completely filled with stones. White could still regain the advantage. Assessing the position, Sedol realized that he was losing. After five hours, he admitted defeat.
Questions
What does a match mean to Lee Sedol?
The result of the match was surprising — the defeat of one of the best human players, the sudden victory of one of the new computer go systems. Instead of a million, Sedol will receive 170 thousand dollars: 150 thousand for participation and 20 thousand for one victory.
A separate problem is why Sedol lost. As Ilya Shikshin says, he was not psychologically prepared:
AlfaGo managed to defeat Lee Sedol. However, this does not mean that the program is stronger. I think that their level is about the same. It’s just that Lee Sedol was not psychologically ready to fight the program in the first games, since it was a huge surprise for him that the program could fight him on an equal footing.
Alexander Dinerstein:
I admit that I did not expect such a scenario. Like most professionals, Go was confident that Lee Cedol would easily win. But we have seen program errors. I believe that the question is still open. Lee Sedol, even in Korea, is not the first number in the ranking. I think that other professionals of his level have chances to win, especially if we see the selections of games played by the program, according to which it will be possible to look for its weaknesses in the game.
What does the match mean for AlphaGo?
For the victory over Lee Sedol, the Korean Paduk Association officially gave the system the honorable ninth professional dan. This means that she is considered a top level player.
Lee Sedol is not the strongest player on the planet, there are others. For example, the owner of the ninth professional dan Ke Jie argues that with a probability of 60% he could beat AlphaGo. Go Ratings site really ranks it higher in the rankings. The call to AlphaGo was also thrown by the Chinese master of the ninth professional Dan Gu Li. There are rumors of requests to play against Iyama Utah.
As long as an opponent is chosen for AI, the editor will calculate that AlphaGo may be higher than the best person in the ranking. According to his estimates on the Bayes theorem, the AlphaGo rating is 3649, while Jie has 3621, below.
However, it is too early, if at all possible, to make any statements about the strength of the system. Only a few games have been published, and the real power of the system is unclear. And does it make sense in rating points if the system can find a weak spot? As Alexander Dinerstein says, it would be interesting to check the program in a match against Takemiya Masaki, the owner of the ninth professional dan:
“He was one of the strongest masters in the world of the early 90s. We noticed that the program prefers the game to the center, to influence. Lee Cedol in all batches took points in the corners. And Takemiya-Sensei is famous for being very fond of playing at the center himself and is not at all “greedy” at the beginning of the game. It is not clear how the program would have behaved against such an unusual style of play. ”
From the computer system, one can expect original and unexpected moves that a person would never have thought of. As Maxim Podolyak says, he saw in AlphaGo moves natural, explicable moves of an exceptionally strong player:
“As they say in one book, the party flows like a stream from a mountainside, naturally and powerfully. B.102 looked impressively strong in the first game. But this is not a “divine” move. ”
Dinerstein asserts that some AlphaGo moves were not considered by people:
“One of the match commentators, Kim Songung, 9th dan (Korea), even thanked the program for contributing to the development of Go theory. Only a decade ago, Fujisawa Suko, one of the leaders of the Japanese Guo, claimed that he knew only 5% of the Go game. The remaining 95 - this is the knowledge that people do not yet possess. Apparently, the program was able to know the game even deeper.
What does a match mean for Google?
The Internet giant has once again shown that it has some of the best technologies in the world. It was Google that was the first to solve another computer science problem. DeepMind sees utilitarian applications for their own groundwork: these are purchase recommendation services or medical data analysis.
But you can distract from commercial projects and still fantasize about go. It doesn't matter if computers start playing better than a person or not. You can set one product on another, and watch the battle of two manufacturing companies. And they are: Facebook is creating a darkforest robot, which is still weaker and has not yet participated in official matches against professional players. This month darkforest has to compete in the computer world championship in Japan. The best of the tournament programs will play against Koichi Kobayashi.
Will someone watch the Facebook battle with Google on a 19 Ă— 19 board? By the way, it's easy to imagine confrontation and personal dislike. In January, Zuckerberg spoke about his system on the same day as Google. And if Facebook had only development news, DeepMind was already showing off a victory over the champion.
Maxim Podolyak:
Hardly. It would be about the same as looking at how the program draws fractals or color spots of the screen saver on the monitor. No one is interested in mechanical search options, there is nothing phenomenal. But the fact that this can make people - a phenomenon.
Alexander Dinerstein:
Chess players of such matches are held for a long time and do not cause much interest. Personally, I would love to watch a program tournament that would be commented by a person. By the way, the top pros with AlphaGo comments would be just as interesting to watch the tournament.
Ilya Shikshin:
I think that matches between computer programs can cause people's interest. Such matches have already been broadcast and gathered several hundred spectators. The level of a person in go is still far from perfect. There is where to grow and develop.
What does match mean to go?
It is possible to perceive in different ways the defeat of the smartest people who have absorbed thousands of years of experience, and the victory of a soulless piece of iron with pieces of silicon inside, launching a program that is not even two years old.In the community of fans of the game, someone is markedly negative. Others see AlphaGo popularization assistance. But he will only win if he competes with and learn from whom, notes Ilya Shikshin:
“The program played very well and deservedly won. Could this match end differently? I think no.I am sure that Lee Sedol discovered a lot for himself during these 5 games. Now he must be ready to fight AlfaGo, but, alas, it's too late. Go-world got a serious rival in the face of this program.
But the discoveries made more than one Lee Sedol. The millions of people who watched this match also discovered something new. Someone has enormous possibilities of technology and artificial intelligence, someone has found something new in the game and now looks at it differently, but for someone the game itself has become a discovery.
Personally, I am very pleased to see that my favorite game these days has become the center of attention of the whole world. I believe that from now everything will be just better. ”
Alexander Dinerstein:
“I suspect that the prizes in Asian countries may decrease, but for the rest of the world, the advantages of a match advertisement, which was enormous, should be outweighed. I expect the influx of new players to go, and we should only be happy about that. Many have heard about this game for the first time. ”
It is also possible to solve problems that are not obtained from people:
“The world of go is of course upset, but with the advent of the program, we can learn a lot of interesting things. For example, in Go there is a problem , invented in 1713 by the famous Japanese master Dosetsu Inseki. The calculation goes two hundred moves ahead. Whole books have been published on it, but no one has been able to solve it. There are beautiful solutions, but they differ from the one originally announced by the author of the assignment. Finally, we will find out if this problem has a solution. Or maybe Dosetsu himself was wrong? ”
If the AlphaGo force systems become the norm, it will be easy to cheat and use the moves of such a system. So far, the champion beats a huge computing cluster. To drag him with him is physically impossible. Today, the computing power of a smartphone is enough to put on the shoulder blades in chess of any person. This did not happen immediately, but we should expect similar things for go in the near future. Someday the possibility of fraud will fit in your pocket even in the absence of a radio link. As Dinerstein says, electronic devices are now relaxed in go championships:
« . . , ( ). , , . . , , , .»
?
The algorithm was created over the months, he was taught to play on human parties, and then he independently reached the highest level. This is one of the best visual demonstrations of the power and speed of AI.
As Ilya Shikshin says, he was struck by the speed with which the system learned the game:
“In a short period of time, the program learned to play at the highest level. It was interesting to see how the program behaves, when it wins and when it loses. ”
What does a match mean to all of us?
Is AlphaGo artificial intelligence?
The system has learned to play go on parties of people. Artificial neural networks have seen as many games as no one will play in their entire life. Then, in games against itself, the system brought the skill to a level that brings victory over the best of people. This is not the case of Deep Blue, when the solution search algorithm was set entirely by hand.
This is hardly any different from how we learn to speak. Children somehow acquire the ability to repeat words, put words into sentences, and then express their thoughts with the received fragments. It takes years of training, this is only possible in some moments of life when the brain is most susceptible. How does AlphaGo differ from a person who has learned to speak, and after honing his skill before writing literature?
You can look inside the project and experience strong disappointment: there are algorithms that can be interpreted and understood. But at the same time its goal AlphaGo performs perfectly. This is the problem: the AI ​​in the view of skeptics must be inexplicable, be able to do everything and hate humanity. The simple execution of the task raises accusations of the options.
But the question of the essence of the terms is not so interesting. It is more frightening to think that AlphaGo plays go better than all its creators, and even the people whose parties were taught by its neural networks.
Will artificial intelligence destroy us?
Subject to the effect of artificial intelligencesometimes require programs to be aware of themselves. This is exactly what AI does not do. IBM Watson beat people in the intellectual game Jeopardy, but does not know about it. He is not torn in the desire to play more. He does not rejoice in victory. He does not even understand that he won. He has no consciousness.
AI is not canonical images in the form of a red light bulb HAL9000 or the evil “SkyNet”. Artificial intelligence is unconscious. This is just a computer program, “smart” enough to perform tasks that usually require the participation of a person’s analysis. This is not a cold-blooded killing machine.
For example, today there are too many scientific articles and studies. Read all physically impossible. We need a system that could read and organize these monstrous arrays of information. And such a system will have artificial intelligence.
But this AI will not kill people. Rather, he will take their jobs.
Will the AI ​​leave us without work?
Artificial intelligence can significantly improve the efficiency of labor. This is what should be a source of concern.
At the dawn of civilization, everyone was engaged in food production, but it was barely enough. Today, almost no one is engaged in agriculture, but food is abundant. The answer to this riddle is in the productivity and efficiency of the tools.
A translation system that only requires proofreading and comparing terms can make the life of a translator much easier. Does this mean that half of the translators risk losing their jobs?
A simple analysis of the text will allow you to highlight a hot phrase in the article, and then post similar with a link to the original through the social network API. Does this mean that the ranks of SMM players will thin? The answer to the requirements to raise the minimum wage cashiers. A flotilla of unmanned trucks will move independently between cities, and the driver will sometimes only sit behind the wheel in order to park. What to do with the huge mass of freed truckers?
Analyzing the video stream broadcast sports match, the robot can make a news article, which will not differ from that written by man. Where in this scenario are more jobs for journalists?
The expert system will evaluate the legal document and make its decision on it. What to do with the vacant army of junior staff in law firms?
Not even the loss of jobs, but their character is dangerous. First of all simple low-paid types of work will start to disappear. Employed in such positions are most economically vulnerable.
Will we be able to adapt to the deep social changes that will occur even without a revolution, but with a sharp flash? Who will benefit from the AI: only those who own such a system? Does this mean another increase in social inequality?
These are the questions that should frighten at the next thaw of the winter of AI. This primitive phobia of omnipotent mechanical killers must not be at all. News of the uprising machines will remain the headlines "the robot killed a man ." Technology is just a tool. Other people create danger.
AlphaGo is another herald of such an obscure future of change. But this AI is not a threat to him, if only because the game only makes it more popular thanks to him. Can not make it worse, another player, the parties which are watching millions.