Author Topic: Google’s AI Masters the Game of Go a Decade Earlier Than Expected  (Read 31408 times)

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
http://www.technologyreview.com/news/546066/googles-ai-masters-the-game-of-go-a-decade-earlier-than-expected/#comments

Google claims that they have developed a AI program to play the game of GO. The program was developed by their team named DeepMind and the program name is called AlphaGo. This program has already beaten the European GO champion and it will have a game of Go with Mr. Lee Sedol, the current master mind in Go, in coming March.

There is a YouTube video in that post which talks about how the Google team develops the AlphaGo. Though I think the way Google's team to develop the algorithm is sensible, I would put my bet on Mr. Lee when they come to play because the game of GO is a game beyond pure mathematics.

The algorithm, tho they claim that they have implanted some intuitive issues in the program, cannot calculate all moves that a human being would play. It is sensible to use two dimension algorithms (a policy algorithm and a value algorithm, where a policy algorithm would suggest a few moves to the value algorithm and the value algorithm would calculate the relative effect and choose the move valuable one to move), but I think human being would be much flexible in dealing with this "Utility Oriented" algorithm:

1. Human can set trap to let the computer have some prima facie advantages on the first twenty moves or even more, especially in the game of GO each player can have over 150 moves.
2. a full game board has 19 x 19 dots for playing the first move. Generally for sophisticated players or even amateur players, they would conventionally play their first move on  a handful of spots, which are rather sensible and important location. But if the professional player plays his first move in unconventional way, like the middle point of the board, it will be very difficult to calculate.
3. One of the reasons that GO is a complicated game because a prima facie bad move in a game may turn out to be a good move. There are quite a lot of game recorded in the history of GO and most of those famous games recorded were due to its unexpected moves. So the weight of intuition may be far more than a computer program can expect.
4. A game of GO usually can be divided into 3 phases: start up, mid-play, round-up (布局、中盤、官子). While round-up phase is almost a mechanical move which is fully mathematical. The start-up phase is now rather formal after years of development, unless the players play unconventionally. The mid-play phase is almost unpredictable. Someone may argue that given the computer is fast enough, they may calculate the move thoroughly. But the fact is that in a game of GO, there is a time limit for each player to play the whole game, usually 4 hours for one game and each player has 2 hour. I would say this is a rather tight time limit for computer.
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
https://www.youtube.com/watch?v=vFr3K2DORc8

The first match was done on 9 March 2016. It surprises most of the Go players that AlphaGo won the match. My estimate was totally wrong. Well....I am a novice of this game, you know.

AlphaGo played well in the middle of the game, which I think that should be the most difficult part for the computer to compute the combination. Lee had a good opening actually with good and intact right side and developing lower left. But AlphaGo can play a few hand to switch the tide, such as consolidating its upper left and invading Lee's territory at the middle right.

Tho Lee surrendered the game at last. Their points should be close but there is a handicap of a few point for the black side. So, anyway, Lee lost the first.

Let's see the second match, tho I am still confident that Lee will win back
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
Second Match: https://www.youtube.com/watch?v=l-GsfyVCBu0

Lee lost again......  :-\

It is apparent that Lee changed his strategy at the beginning of the game but AlphaGo still played a very good game throughout.

Some professional Go commentators said that AlphaGo played different styles during the game and some moves were far beyond professional's imagination.

Should I move my bet to AlphaGo now?

I think Lee may try playing extremely unconventional game to disturb its algorithm, like playing the first move at the middle of the board.

Next game will be on 12 March. Let's see if Lee can get one back.
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
Third match: https://www.youtube.com/watch?v=qUAmTYHEyM8

This is the third game which Lee has no way out. He has to win in order to get the US$ 1 mil.

He started aggressively but AlphaGo defended well. AlphaGo still played some unusual moves but it almost won all the local fights.

Hence, Lee had another lost and AlphaGo won 3 in a row.

Post-match press conference said that Lee was so nervous. Lee also said that he would relax and play better in the next matches, let's see.

「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
The fourth match: https://www.youtube.com/watch?v=yCALyQRN3hw

This is the turning point. Lee finally won this game.

AlphaGo was forced to resign. By saying so means that AlphaGo found that its winning percentage was so low to trigger the resignation threshold.

Some professional commentator said that Lee's move no. 78 was the "God's move" but Lee replied in the post match conference that this move was the only available move that he can envisage at that moment.

AlphaGo team said that after move no.78, AlphaGo made a mistake in move no.79 and it realized its fault at move no. 87. If that's the case, it is amazing that the programme keeps on reviewing its decision so quickly, so after 8 moves may be too late for a game of GO.

Lee played a good game on taking a large portion of territory at lower right and successfully squeeze the middle territory. A beautiful game indeed.

Another finding was that AlphaGo seems struggling in the last few moves before it resigned. It played some moves that was so stupid that even I as a novice would not play.
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
The final match: https://www.youtube.com/watch?v=mzpW10DPHeQ

A final match which was full of expectation, especially after Lee's win. Lee said that he at least found two weaknesses of AlphaGo, first was that AlphaGO played well when it was the white side, i.e. play later. The second was that it did not respond well on the unusual moves.

With that in mind, I expected that Lee would play some unusual moves in game 5, but it turned out that not many unusual moves.

Lee played very well at the beginning and AlphaGo seemed to make another mistake, which resulted in losing the lower right corner and quite a lot of white stones killed. I expected that Lee would win again at that time, as his territory was far larger than that of AlphaGo's.

However, AlphaGo fought back beautifully by taking territory bit by bit. At the end, the game was so close that Lee only resigned close to the finish, after he calculated that he cannot win. He was really disappointed.

Some professional said that Lee only lost 2.5 points. As Lee took the black side and played first, there was an adjustment that Lee had to get 7.5 points more than AlphaGo in order to win, i.e. for the territory per se, Lee was ahead of AlphaGo by 5 points.

I thought that Lee won all along this game and did not think that AlphaGo can win.

As I understand from AlphaGo from the press conference, AlphaGo played each move in accordance with its calculated winning probability. It does not care how many points he will win, as long as the move can enhance its winning probability. This needs a very deep calculating which I don't think human being can do. Like this game which Lee, as a professional,  or the commentator, who is a 9-dan professional, can roughly estimate how many points he is ahead or behind but they can never be so precise to know he is winning 1 or 2 points, but it seems AlphaGo can.

I do learn a lot by watching these games and it makes my hand etching to play some.  :D
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
ON 23 May 2017, AlphaGO vs Ke Jie. This time it is a 3 round game. I expect that Ke Jie would never win a game, given that this AlphaGO is the newest version with lots of improvement and the record in a few months ago that Ke Jie was beaten by the Master (the computer account set up by Deep Mind team to test AlphoGo on internet GO game).

Ke Jie is the no. 1 ranking player in the world at the moment. Here is the link for his first game: https://www.youtube.com/watch?v=Z-HL5nppBnM

I found that Ke Jie played rather conservatively. He focused on getting as much territories as possible at the very beginning. Surprisingly, AlphaGo let him take up a lot of territories at the beginning, only defend a few of them. In the middle of the round, AlphaGo showed its planning worked. It built a solid foundation and surrounded the mid-field well. You can see Ke Jie kept losing his territories bit by bit. They had to play to the last move in order to distinguish the winner. At last, AlphaGo won by just a half point.

At least, even for a novice like me, I saw the AlphaGo was improving. It improved on the aspect that its calculation was faster and much more accurate. Besides, it strategy was well played and I am sure that AlphaGo knew he was winning at any time. That's why it allowed Ke Jie to take territories without severe defense. I doubt that AlphaGo was like playing its own game, as long as it was ahead of the opponent, it will play its own way, even the advantage was just 0.5 point.

An exciting game actually. Look forward to the next game.
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
Round Two:

https://www.youtube.com/watch?v=1U1p4Mwis60

As expected, AlphaGo won. Ke Jie resigned in the later part of the game, unlike round 1 that he played till the last. However, Ke actually played much better than the first round but he envisaged that he cannot win before the end of the game. This time Ke Jie played some moves rather unusual and made AlphaGo taken more time to respond. In addition, Ke Jie played the white, the colour that he plays better. This is evident in the press conference after the game that AlphaGo analysed Ke Jie's moves in about the first 50 moves that their winning probability was about 50%, i.e. Ke played like AlphaGo.

A good challenge by Ke but a sad lost.
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」

Offline hangchoi

  • SBC Old Boys
  • ***
  • Posts: 3,007
  • Alcoholic + Golfmania
    • MaJeff's Wine Blog
Round Three:

https://www.youtube.com/watch?v=ru0E7N0-kFE

Ke said before the round that he would do his best, but it did not look like he did. He tried hard at the very beginning but somehow a few bad moves that dragged him into a hopeless game. In the middle of the game, even a novice like me can see that Ke was struggling to alive. Until later AlphaGo played a stone on the middle upper of the board, even I myself can see that Ke had no chance to win.

Among all three games, Ke played the best in the second round. He did well actually, tho he lost all 3. It cannot be comparable with Lee Sedol last year because AlphaGo had much improvement and its database has more that 100 million game. However, I think in a few years later, people will only remember that Lee Sedol is the only human being who can beat AlphaGo once.
「吾心信其可行,則移山倒海之難,終有成功之日。吾心信其不可行,則反掌折枝之易,亦無收效之期也。」