The Chisel-Construct Cycle · AI Series · 18

Lee Sedol's Move 78

Han Qin · About 13 minutes · Published

1. A Decent Game

On January 21, 1965, the British weekly New Scientist published an essay called “The Mystery of Go.” The author, the mathematician Irving John Good, had worked with Turing at Britain's codebreaking center during the war. One section asks if a computer could play Go. Good's answer was that programming a computer to play a decent game of Go would be harder than making it play chess.

In essay four, a paper about chess from 1950 gave its reason for choosing the subject: playing chess well was generally thought to require thinking. Fifteen years later Good moved the boundary a step, to a game harder than chess.

Go doesn't have many rules. On a board of nineteen lines each way, two players take turns putting black and white stones on the intersections. When opposing stones surround a group so it has no liberties, the group is taken off. At the end what matters is who holds the larger area. Few rules, many places to play. The first move alone has 361 possible points. There are more possible positions on the board than atoms in the universe.

In May 1997 the machine in essay eleven called Deep Blue beat the world chess champion in a match. On July 29 of that year The New York Times quoted the astrophysicist Piet Hut as saying it might take another hundred years for a computer to beat people at Go, and perhaps longer. He also said a smart person could study Go for a few months and beat the programs of the time.

In 2014 a reporter for Wired asked the Go programmer Rémi Coulom when a machine would be able to beat a person without a handicap. He thought perhaps ten years. He added at once that he didn't like making predictions.

2. Handicap Stones

Handicap stones are a way for two people far apart in skill to play. The weaker player puts several stones on the board before the game starts. The greater the gap, the more stones.

Around 2006 several European researchers started thinking about Go programs another way. Facing a position, instead of trying to judge the quality of each move at once, the program quickly played out a great many possible games to see which moves led to more wins. It went a little deeper down the more promising paths. In a 2006 paper Coulom called this Monte Carlo tree search. Monte Carlo is the part of Monaco with the casino. The name means estimating by trying things at random. Coulom's own program was called Crazy Stone.

On June 22, 2012, the Japan Go Association and Tokyo's University of Electro-Communications signed a cooperation agreement. Each spring they would arrange handicap games between a professional and a program, in a match called the Denseisen. At the first one in March 2013 Crazy Stone received four stones from the ninth-dan player Yoshio Ishida. The program won.

At the second event on March 21, 2014, the ninth-dan player Norimoto Yoda faced Crazy Stone, again with a handicap. A reporter from Wired was there. The room had imitation wood paneling, fluorescent lights overhead, and a projection screen in the corner. A film crew was getting the live stream ready. The program ran on a system beside an old laptop; the screen showed its estimated chance of winning. A person read the screen and put its stones on the board. Yoda opened and closed his fan while he played. Near the end the program played several moves inside its own territory that needlessly cost it points. It cared about how likely it was to win, not how much it won by, and the programmer looked on with some embarrassment. In the end it won by two and a half points. At the third event the next March, Cho Chikun, ninth dan, gave a Korean program four stones. Cho resigned.

That year the professional Michael Redmond told a reporter for Wired how people play Go. Sometimes he saw a move and was sure it was right but couldn't say why. The reporter called it intuition, something that grows over years of training.

3. A Wall

From October 5 to 9, 2015, at DeepMind's London headquarters, European Go champion Fan Hui played five formal games without a handicap against the company's program AlphaGo. This was the London company acquired by Google in essay seventeen. Each side had an hour, then thirty seconds per move, with three periods available: run over thirty seconds and you used up a period. AlphaGo won all five.

The games weren't made public at the time. On January 27, 2016, the British weekly Nature put “Mastering the Game of Go with Deep Neural Networks and Tree Search” online, and the news of the games came out with it. Twenty people signed the paper. The second name was Aja Huang.

The paper describes how it worked. It had two networks. The first looked at a position and estimated where a professional player might place a stone and how likely each move was. The paper calls it a policy network. The second looked at a position and estimated who would eventually win. It was called the value network. Both helped the kind of search in the previous section avoid unpromising lines. The network that learned from records of human games estimated how people would play. On top of that, the program worked out stronger play by playing itself, and used self-play games to train the network that estimated who would win. The version that faced Fan Hui used 1,202 CPUs and 176 GPUs.

Fan Hui later told a reporter for Wired that the program was strong and steady, like a wall. If nobody had told him, he said, he might have taken it for an unusually strong person with a slightly odd way of playing.

If nobody had told him. In essay five, Turing's imitation game in 1950 called for a person who couldn't see who was on the other side and had to judge from what came back. Sixty-five years later, a professional sitting across a Go board said something that sounded like an answer to that question. He knew the other side was a machine because someone had told him.

4. The Four Seasons

In March 2016, on the sixth floor of the Four Seasons Hotel in Seoul, AlphaGo played five games against the Korean ninth-dan player Lee Sedol. They played on the ninth, tenth, twelfth, thirteenth, and fifteenth. Each game began at one in the afternoon.

They used Chinese rules with a komi of seven and a half points. The Chinese rules count stones and the area they enclose. Black moves first and has the advantage, so a seven-and-a-half-point adjustment offsets that advantage at scoring. Each side had two hours, followed by three one-minute periods. The prize was a million dollars. After AlphaGo won the match, the company announced it would donate the money to charities and Go organizations.

Aja Huang sat opposite Lee Sedol, with a computer in front of him. When Lee placed a stone, Huang entered the move. The screen showed where AlphaGo wanted to play. Huang picked up a stone, set it on the board, and pressed the clock.

In essay sixteen, around 1770, the Turk played chess by having a person hidden in a cabinet make the moves for a machine. The people watching couldn't see him. In Seoul in 2016 a person sat in plain sight, putting down stones for a machine with everyone watching. The machine chose the move. A person's hand put the stone down. The computers doing the calculations weren't in the room.

Lee Sedol resigned in the first three games, so the match was decided in the third. In the fourth the program resigned. In the fifth Lee resigned. Four to one.

5. Move 37

In the second game, on March 10, AlphaGo had black. On move 37 it put down a stone. At the English-language commentary desk, one person said it was a strange move. Another said he had thought it was a mistake.

Fan Hui was there. Looking at the move, he said it wasn't one a person would make. He had never seen a person play like that. After about ten seconds he saw how it related to the stones already on the board. He said it was beautiful.

In the control room, DeepMind's David Silver brought up AlphaGo's records. He later told a reporter for Wired that the policy network trained on human games put the chance of a professional playing that move in that position at one in ten thousand.

One in ten thousand measures this: from what people have played in the past, would a professional coming to this position move there? It doesn't measure whether the move is good or whether a person could think of it.

Years later, the company described move 37 on its own website as a move with only a one-in-ten-thousand chance of being played. The model learned from past games and the professional it was meant to represent both disappear from that sentence.

At the press conference afterward Lee Sedol said through an interpreter that the previous day he had been surprised. Today he was speechless. From beginning to end, he said, he hadn't felt ahead for a moment. AlphaGo's play in that game was nearly perfect.

6. Move 78

After losing the third game on March 12, Lee Sedol began the press conference by apologizing for letting people see how powerless he had been. The line that traveled farthest from that press conference was that Lee Sedol had lost, not humanity.

On March 13, in the fourth game, Lee had white. On move 78 he played in the middle of the board. The ninth-dan player Gu Li called it a divine move that day.

AlphaGo didn't resign straight away. It made a series of moves the commentators couldn't make sense of. A few more moves went by before its assessment of the position caught up. Lee said afterward that it looked as though the program had malfunctioned. In the end the program resigned. At the press conference Lee said he thought this was the first time he'd won just one game and received so many congratulations.

On its later website the company gave move 78 a number as well: one in ten thousand. The same number, described in the same way. The machine played move 37. Measured against human game records, a professional would play it with a probability of one in ten thousand. A person played move 78. The company used the same wording for it, but did not say how it got the number.

On March 15, in the fifth game, Lee Sedol resigned. A great many people watched. Google said the first game alone drew sixty million viewers in China. DeepMind later said more than two hundred million people around the world watched the five games. Two days after the match, South Korea's government announced it would spend about a trillion won over five years on artificial intelligence research.

7. Zero

In late 2016 and early 2017, one account on South Korea's Tygem and China's Fox Go Server played a string of fast games against top professionals, among them Ke Jie, Park Junghwan, Yuta Iyama, and Gu Li. The account name changed along the way. The later name was Master. By January 4, 2017, it had played and won sixty games. That day DeepMind's Demis Hassabis said online that the games were a test of a new AlphaGo prototype.

On May 23, 25, and 27, 2017, in Wuzhen, Zhejiang, Ke Jie played three games against AlphaGo. In the first AlphaGo had white and won by half a point. In the other two Ke Jie resigned. After the match the company said AlphaGo would not play in matches like it again.

In October that year Nature published another paper, “Mastering the Game of Go without Human Knowledge.” The new version was called AlphaGo Zero. The company's account says earlier versions first learned from thousands of amateur and professional games. This one skipped that step, starting with random play and playing only against itself. After three days of training it played a hundred games against the version that had beaten Lee Sedol and won all one hundred games. By forty days it was stronger again. The following year the same line of work was extended to chess and Japanese shogi. It was called AlphaZero.

The title says without human knowledge. The paper and the company list what the system was given: a nineteen-line board, black and white stones, whose turn it is, where it can and cannot play, and who won when it's over. People designed the network and the search. People decided how it would practice, one game at a time. It didn't learn from games people had played. It played the game people had been playing for centuries.

The players were changing, too. In April 2017 DeepMind interviewed several Chinese professionals. Zhou Ruiyang said what he had taken from the program was that no move was impossible. Playing at the three-three point early, a pattern that had rarely been played, was taken up for study again.

In March 2023 four researchers published “Superhuman Artificial Intelligence Can Improve Human Decision-Making by Increasing Novelty” in the Proceedings of the National Academy of Sciences. They used a Go program stronger than people to assess the moves professionals had actually made over several decades. After 2016 the quality of human play had measurably risen, and the rise was associated with a greater number of novel moves.

8. One in Ten Thousand

In November 2019 Lee Sedol filed the paperwork to retire from professional Go. Even if he became number one, he told a Yonhap reporter, there was something he could not beat. The next month, from December 18 to 21, he played three farewell games against HanDol, a program made by a Korean company. In the first he received two handicap stones. The program badly misread a major part of the position and resigned. It won the other two.

In 2023 a group of researchers published “Adversarial Policies Beat Superhuman Go AIs.” They had trained another program to look for weaknesses in KataGo, a strong open-source Go program. It found a weakness in how KataGo judged which stones would live or die in a large circular position. A strong amateur, Kellin Pelrine, learned the approach and won fourteen of fifteen games against KataGo in a test with a human player. KataGo's author subsequently changed the program. Later people found ways to win against revised versions as well.

Something he couldn't beat: a ninth-dan professional said this in 2019. Four years later an amateur took an approach found by another machine and beat a program the paper called superhuman.

Two things were left out in this essay. One was what came before one in ten thousand: the model learned from human games estimated whether a professional would move there. Cut that and the number becomes a measure of how rare the move itself is. The other was what went unsaid after without human knowledge: it skipped learning from records of human games, but people still supplied the board and the rules. Take that away and it sounds as though the program got nothing from people at all.

There's one other thing that isn't in the machine, whether you cut anything or not.

AlphaGo gives a point on the board. Strange, a mistake, not a human move, beautiful, divine, creative: all of those were said by people. On its later website the company called move 37 creative and move 78 divine. People gave those names to the moves. The program's records have no field for them. Before Fan Hui said it was beautiful, ten seconds went by. Those ten seconds were his.

The one putting the machine's stones down is a person. The one across the board is a person. The one apologizing after resigning is a person. The company says two hundred million people watched the five games. Is a game played by no one and watched by no one still a game?

By the number the company gave later, move 78 was one in ten thousand. Lee Sedol made it. The ruler used earlier to measure people was made from their past moves. The next move is still made by the person sitting at the board. This series calls the part that no calculation based on the past can take in the remainder.

The machines are still being built. Each generation says again where the boundary lies.