The secret of the ancient game of go. Why has the computer still not beat the man?

Remy Cool (left) with Crazy Stone vs Grandmaster Norimoto Yody



In 1994, the computer beat the world champion in drafts, in 1997 - in chess. Today computers are superior to people in absolutely all popular games with complete information , except for one.



The classic game with a 2500-year history has very simple rules, but computer programs cannot even get close to winning over the best grandmasters, Wired writes .



The ancient game can be considered the "eastern version of chess." Like chess, it is a game with complete information, that is, at any time of the game, all players have complete information about the state of the game and affect the game with discrete actions. Here, success does not depend on luck or speed of reaction.

')

Despite the increase in computing power of computers (the world chess champion today is likely to lose even to your home PC), go algorithms at the expert level remain unsolved and one of the most interesting problems of AI. The problem is that very few are able to rise to the ninth dan in the game. For this you need to study for several years in Japan or Korea. There, talented children have been taken home from school to study at an academy of about 9 years old.



Advanced lovers almost always get stuck at a certain level of the game and cannot improve the result: “Some mental leap is required to remove this blockage, and the same problem is in program development,” explains David Fotland, PA-RISC’s main developer Hewlett Packard in the 70s. He tested the go program on his development processor. “The question is how to evaluate the entire board, not individual fragments.”



The game has long been popular not only in the east, but also in the west, especially among mathematicians and physicists. For example, Einstein often played go, as did the famous mathematicians John Nash and Alan Turing.



Computer programs for go have been developed for 45 years, and almost as much attention has been paid to this problem as to chess programs. The first was written by the genius of game theory Alfred Zobrist in 1968. She could beat the absolute newcomer who had just met the rules ( recording the first man-computer game ). The beginning seemed optimistic. In the next four decades, an enormous amount of time and intellectual effort was spent, but even with the progress in the computing power of the program, even an advanced amateur could not be overcome.



The reason can be understood if we compare it with chess. At the beginning of a chess game, White has 20 possible moves, and Black has 20 possible answers. After the first move, there may be 400 different positions on the board. Now compare the numbers in go: on the 19x19 board, Black has 361 possible initial moves, and White has 360 answer choices. This means 129,960 possible combinations only after the first round.



The so-called “branching factor” —the average number of moves available in each round — is 35 in chess and 250 in go. Games with strong branching make it difficult for standard algorithms that use the minimax rule to create a tree of possible combinations. Even with the analysis of not all, but only promising branches for a deeper analysis. What works in checkers and chess does not work in go. The selection of perspective branches in a tree of possible combinations of go is often a completely mysterious process. Even the players do not understand how they do it: “Just look at the board and know,” they say.







Again, in chess it is almost always possible to understand who wins, at least by the number of pieces. In this situation, only experts can interpret the situation.



The average number of moves in the game: in chess - about 40, in go - 200. Given the branching factor and these statistics, the impotence of computers becomes understandable.



Talented French programmer Remi Coulom achieved the first success with the program Crazy Stone in 2006, when he decided to combine the minimax and the Monte Carlo method. The new algorithm for calculating the branch tree, he called Monte Carlo Tree Search or MCTS. The Frenchman won the championship among computer programs UEC Cup in 2007 and 2008, but it did not bring him fame, and Remy abandoned the development. But in 2010 he received an offer from the Japanese game developer Unbalance - and in 2011 the first commercial version of Crazy Stone was released. In 2013, Remy triumphantly returned to the championship.



However, in 2014 there was a failure. In the final confrontation against the Zen program, the audience realized that something strange was going on after the third move. The Zen program, after the standard setting of two stones in the corners, suddenly put the third stone near the center. So no one played, it was clearly "inhuman" decision. Soon the level of winning expectations at Crazy Stone rose to indecently high values, more than 60%. Apparently, the program considered a safe group of stones in the upper right corner, although it was not safe. Since a successful strategy depends on the correct assessment of the board, viewers began to whisper about the possible defeat of Crazy Stone. And so it happened: on the 186th move, Crazy Stone admitted defeat, and Zen became the new champion of the UEC Cup.



However, Kuloma still has the opportunity for revenge. As a finalist, he received the right to play against a real human grandmaster with a handicap of four stones. This year Norimoto Yoda arrived at the tournament. The Japanese grandmaster sat at the table in a traditional green kimono. Remy Cool - wearing rimless glasses and a blue sweater, which was in the last championship.



The professional commentators who accompanied the online broadcast of the game agreed that Crazy Stone played well and even had an advantage. Yoda was extremely annoyed and looked stern, and Kulom fussed, looking now at the laptop, now at the game board, then at the chronometer - anywhere, just not at the Horse.



Insulting defeat Crazy Stone suffered in the very ending. Winning 11 stones, any person would make some obvious defensive moves to prevent the opponent from recouping and maintaining an advantage. But Crazy Stone was programmed to win only. Therefore, its algorithm was to make meaningless moves in its own zone in a win situation, waiting for the opponent to admit defeat. But here such a trick did not work out - and Oda managed to recoup. In the second match against Zen, he already looked better and won four stones from the program.







Remy Culem was still happy - and promised for the next championship to finalize the algorithm of actions in the end.



Apparently, the computer will soon win the last game with full information, which is still left for the person. According to Kulom, the program will win without a handicap for 10 years. Experts who know the power of the best players are not so sure. The fact is that at the highest levels the game goes to a qualitatively different level, the moves are no longer predictable. At the same time, the quality of the game of programs still relies not so much on the computing power as on the quality of the code: for example, the same Crazy Stone and Zen on 64-core standard servers easily defeated 2048-core opponents clusters. That is, programs can be buried in the wall again.



But even if computers win the go, one cannot speak of the “fall of the last intellectual bastion” where man dominates, as newspapers wrote after the victory of Deep Blue in chess. Go programs are simply highly specialized tools for solving specific problems. They are very far from the human mind and do not try to emulate the brain. “For me, this is just entertainment,” says Kulom, “no more than that.”