Tomorrow there will be a match that will surely go down in history — AlphaGo V.S. Lee Sedol, maybe some boyfriends are already thinking:

I don’t know much about go, and I’ve only heard about the high-concept field of artificial intelligence. Tomorrow girl friend asks “how to go under?” “And” How does AlphaGo play Go? Who is Lee Se-dol? How humiliating it is to be speechless at these questions!

Don’t panic!

Our live broadcast at 12 o ‘clock tomorrow will be easy to understand, and we have invited go and artificial intelligence experts to make live explanations. If you want to read it, we can make it understandable.

Of course, it is impossible for our expert commentary team to explain every go and AI concept in detail during the live broadcast. Therefore, we specially prepared a girlfriend can also read the knowledge of the post.

All right, let’s see who we’re dealing with.

Lee sedol is good, but AlphaGo is high-tech

Lee se-dol

People who don’t follow Go probably don’t know Lee Sedol. Lee sedol is a professional go player of the 9th Dan, which is already the highest level among professional go players.

Of course, Lee Sedol is not powerful in his rank, but he can maintain the first-class level for years. Since he was crowned Fujitsu Cup in 2002, he has won a total of 14 world championships in 10 years. He is the chess player who has won the world no. 1 title most in the last 10 years, and is recognized as a Legend of Go.

Anyway, it’s just a matter of knowing that Lee sedol is one of the best go players in the human race, and that he can always turn things around at the last minute.

AlphaGo

AlphaGo is a computer program developed by Google that, to put it more grandly, is called Go AI (artificial intelligence).

AlphaGo defeated Fan Hui, professional second Dan, in October 2015. It may not seem like much, but this is the first time a Go AI has beaten a professional player without making a move. How it does that, we’ll tell you later.

All in all, Lee Se-dol’s match against AlphaGo is a battle between human intelligence and high-tech, which has been described by many media as a “battle for human dignity”.

After watching the two sides, let’s take a look at how go is actually played.

A little knowledge of Go

Weiqi is played with black and white pieces on a square board, which should be known.

Professional go games are usually played on a 19-by-19 board, with the game starting on an empty board and each player trying to control more territory than the opponent by the end of the game.

The eye refers to the intersections occupied by the pieces on the board.

At the start of the match, blackball side first. In this way, the black side will have an advantage. In order to eliminate the first advantage of the black side and make the victory rate of the black and white sides consistent as far as possible, the black side needs to close the eyes when the final game is calculated. To avoid a draw, the end order usually includes half order.

The AlphaGo-Lee sedol match was played under the Chinese rule of 7.5 points, which means that a black person gives 7.5 points to a white person in the calculation of the winner. As for why the Chinese rules, industry experts speculate that it is very convenient to program.

A piece that is completely surrounded is eaten and removed from the board. For example, white can play in position A to take A black.

Pieces connected vertically or horizontally can be taken as a whole. For example, white can eat three spots in position A.

No same-type duplication: The rules of duplication prohibit the duplication of same-type duplication. You can’t bring it back right away. But you can pick it up later on the board. Which means you can get the loot, and then you can get it back.

Chi is the intersection point adjacent to a piece of chess. For example, white has three moves at A, B, and C. A piece of chess will be dropped if it has no air. A piece of chess is called “eat” only in one breath.

The calculation results

There are two ways to calculate the winner at the end of a game:

  • The numeral method calculates the encircled area, that is, the number of intersections occupied by both sides.
  • The number method calculates the number of eyes taken by both sides, including dead children.

If both parties have the same number of hands, the two calculation methods give the same result.

How does AlphaGo play Go?

AlphaGO continues to improve through deep learning based on a large amount of chess data, and improves through self-simulation. There are three main concepts involved: exhaustive, Monte Carlo tree search and deep learning.

An intuitive and lazy way for AI to approach any chess game is to run out of ways to win.

Exhaustive is a mathematical calculation method that determines a rough range of answers based on partial conditions, and verifies all possible cases within this range until all cases are verified.

For example, brute force is called brute force in cryptography. If the password contains only one digit, the password can be used up to 10 times: 1, 2, 3, 4, 5, 6, 7, 8, 9, 0.

A 2-digit password can be cracked in 99 attempts (00-99).

Monte Carlo tree search

An exhaustive scheme would result in a Tree map, invented for the computer game go, called the Monte Carlo Tree Search (MCTS). The general principle is: through the statistics of a large number of Monte Carlo sampling results, to select a better move.

Monte Carlo algorithm is a generalization of the characteristics of a class of random algorithms. It was born in the “Manhattan Project” of the United States in the 1940s. Its name comes from monte Carlo, a gambling city, symbolizing “probability”.

Zhihu user Su Ye gave an example to help us understand the Monte Carlo algorithm:

If there are 100 apples in the basket, let me close my eyes and pick out the biggest one. So I take a random one, and then I compare it with a random one, and then I keep the big one, and then I take a random one… Each time I picked it up, the apple I left behind was at least as small as the last one. The more I pick, the bigger the apple, but I can’t be sure I picked the biggest apple until I pick it 100 times. The algorithm for picking apples is the Monte Carlo algorithm — try to find the best, but it’s not guaranteed to be the best.

(Construction process of Monte Carlo tree search algorithm)

However, Go is simply too complicated. Chess has an average of 35 possible moves, and a chess game can have 80. In go, there are 250 possible moves, and a single game can last up to 150 moves.

A chess AI can beat a human by brute force, whereas a Go AI that relies only on Monte Carlo tree search for brute force is very slow.

Deep learning

AlphaGo has incorporated “deep learning” techniques to try to reduce the number of hard knocks required.

Deep learning is a branch of machine learning. Machine learning is the idea that an algorithm will build its own logic on the data it inputs for a problem to be solved without writing any special program code.

Deep learning emphasizes the models used, such as Google Photos, which gained more than 100 million users in less than six months, using a convolutional neural network model.

AlphaGo makes use of two deep learning Network models, which you have probably seen in many media, namely Policy Network and Value Network.

In short, strategy networks can be understood as chess networks, focusing on the present and predicting/sampling the next move. Value networks think longer term and predict where the chess game is going.

After reading the above knowledge post, if you still want to know the difference between AlphaGo and human players, take a look at the following words from Tian Yuandong. Tian Yuandong, a researcher in Facebook’s ARTIFICIAL intelligence group, has been quoted on Zhihu as saying:

A professional chess player can figure out an opponent’s style and adopt a strategy after watching a few games, and an experienced gamer can quickly pick up a new game after playing it a few times, but so far, a large sample of training is needed for ai systems to reach human levels.

It can be said that without thousands of years of accumulation of go players, there would be no go AI today.

The checkerboard illustration is from SmartGo

Reference article:

What is Go?

The analysis of the AlphaGo

Humanity’s last intellectual pride is about to crumble in the face of Google go AI

Ai in 5 days! Can the world’s top chess player “defend” human Intelligence?

Attached: AlphaGo vs Go champion Lee Sedol trailer video

 

Live preview:

Tomorrow at 12 o ‘clock noon, the final battle will be opened, love fan will be live for you. At the same time, we have invited go and artificial intelligence experts to give live commentary. As long as you follow fan, you will be able to get first-hand information about the finals.

The last Deep Blue war in human history? ! Google’s artificial intelligence AlphaGo will play Lee Se-dol of South Korea, one of the world’s top go players, from March 9 to 15. Can the human race hold on to its last dignity in five games? Ai fan invited a number of top go players and experts in the field of artificial intelligence for you to track and report the whole process, please continue to pay attention to.