Friday, April 29, 2016

Part 9: Review of Game 4: Lee Sedol's brilliant move reveals weaknesses AlphaGo (The historic match of deep learning AlphaGo vs. Lee Sedol)

[NL Versie]

Review of Game 4:  Lee Sedol's brilliant move reveals weaknesses AlphaGo

After Lee Sedol went under in the match against AlphaGo with three successive losses, and after his mental succumb under incredibly high psychological pressure yet early in the third game, the main question is what Lee Sedol still has up his sleeve when trying to defeat AlphaGo.

And how unimaginable resilient, persistent, and believing in himself Lee Sedol must be, after the new sledgehammer blow of the third game, to try to collect himself, to show that he is able to deliver, and to prove all humanity is right?

The opening of the fourth game is the same as that of the second game (in which Lee Sedol had white also) up to move 12. Lee Sedol response to AlphaGo's probe move (yosu-miru) in the bottom left corner is aggressive (triangle in Dia. 1), attacking both the black stone on the left and black's probing move. 

Dia. 1:  Game 4, after black 25 (circle, Lee Sedol is white) 
Lee Sedol forces AlphaGo to make a choice but the program simply plays somewhere else (tenuki, circle in Dia. 1). With a shoulder hit black first wants to see how things develop in this area before deciding how to answer white's double offensive (triangle in Dia. 1).

Dia. 2:  Game 4, after black 35 (circle, Lee Sedol is white)
Lee Sedol concentrates on taking territory in the edges and bottom corners while AlphaGo conquers the upper side and builds influence in the center (Dia. 2). Lee Sedol follows the amashi strategy: the amashi player takes territory in exchange for influence, and hopes to withstand the outside power and attacks later.

Dia. 3:  Game 4, after black 47 (circle, Lee Sedol is white)
When Lee Sedol tries to neutralize AlphaGo's strong center influence (triangle in Dia. 3), AlphaGo completely ignores his move and plays another shoulder hit at the right side (circle in Dia. 3). Again, black wants white to answer before deciding about attacking white's center group.

When black cuts off the four white stones in the upper center (triangle in Dia. 4) and white extends (circle in Dia. 4), a complex and ambiguous fight develops. AlphaGo heightens the tension and forces Lee Sedol to act with his center stones to prevent that black cashes in the influence built in the center. 

After white's extension (circle in Dia. 4), black's stones on the middle right comes under very severe pressure. How is black able to involve these stones in the game without weakening it's earlier investments in the center?

Dia. 4:  Game 4, after white 64 (circle, Lee Sedol is white)
AlphaGo's last move (triangle) cuts off the white group in the center.
Since multiple important and large-scale fights make it much harder for AlphaGo to judge the board position correctly, these are the ideal and complex battles to initiate for Lee Sedol.

Where to play next, is a matter of 'looking' forward at least 20-25 moves in this ambiguous fight in the center and right edge. Lee Sedol's fabulous intuition and immense skills in assessing all options and starting points in such explosive positions, are herewith invaluable (Dia. 4). Both AlphaGo and Lee Sedol have to rely on a very crude estimate of how the position may develop gradually.

Black decides to leave his stones at the middle right hand side and further strengthens his moyo to increase the pressure on white to the very maximum. For Lee Sedol it seems virtually impossible to do something  sensible with his center stones. After he cuts to make the position more complex (triangle in Dia. 5), AlphaGo answers confidently and seals off any escape routes towards the center (circle in Dia. 5).

Dia. 5:  Game 4, after black 73 (circle, Lee Sedol is white)
Although black has substantial weaknesses at both moyo edges, the white center stones appear to cooperate rather loosely and creating a living group is there out of the question. Also, to escape is not an option for white with such a majority of black stones awaiting him (center and bottom). Moreover, the aji of black's group in the middle right complicates an eventual white escape (Dia. 5).

In short, it looks like this once more will be a major victory for AlphaGo: white's position seems completely hopeless. But then Lee Sedol puts forward a completely unexpected, wonderful, and brilliant move that suddenly sets the entire board on fire.  All white center stones are activated at once and do cooperate effectively by exploiting the aji in black's center moyo in all conceivable means (Dia. 6).

Dia. 6:  Game 4, after white 78 (circle, Lee Sedol is white)
Lee Sedol's move just dropped out of the sky, both for all live commentators and the many top Go-profs that closely followed the game.  It unites all Lee Sedol's power, skills, perseverance, creativity, intuition, willingness to fight and to seek reprisal for all frustration and powerlessness in the previous three games. When seeing this move during the live commentary in China, top Go-prof Gu Li (9p) described Lee Sedol's move 78 (triangle in Dia. 6) as a "God's move". 

With black 79, AlphaGo fails to play the best response and what happens is a sequence of moves that the program calculated as the strongest answers. In exchange for it's group lost on the right, AlphaGo just gets a poor sente move that the program also could have played immediately (Q13 in Dia. 7).

Dia. 7:  Game 4, after white 94 (circle, Lee Sedol is white)
Commentator Michael Redmond (9p) showed that instead of black 79 much better responses were possible than AlphaGo actually played in the game. In the end, AlphaGo has to give up the stones in the middle right, so that Lee Sedol not only has secured his group and largely destroyed black's center moyo but in addition cashed in a pile of points on the right. 

With move 110 (circle in Dia. 8), white secures his relatively weak stones in the center by attacking the black group on the left (center). In this manner, white creates enough options to connect with the group in the bottom left in case of emergency. 

Direct comparison of Dia. 7 and --more than thirty moves later-- Dia. 8 immediately demonstrates that white has achieved the unimaginable: it is as if white's invading center stones were able to escape through an invisible tunnel (David Ormerod). Lee Sedol efficiently utilized the aji in black's center that he correctly estimated 25 moves earlier.

Dia. 8:  Game 4, after white 110 (circle, Lee Sedol is white)
With this successful center fight, Lee Sedol takes a clear lead. The South Korean live commentators cannot hide their excitement when it becomes clear that Lee Sedol --after three hours into the game-- probably will notch a win. 

There is nothing left to AlphaGo other than to secure it's group on the middle left and to allow that Lee Sedol meanwhile connects his center group --in sente--. Then white further erodes black's center by connecting the three white stones on the upper side. Black's entire moyo has been neutralized (Dia. 9).

AlphaGo tries to catch up with active play but Lee Sedol plays magnificently sharp. An example of this is Lee Sedol's counter move in Dia. 9: white ignores black's threat at the bottom right corner and plays a larger counter threat (circle in Dia. 9; that also prevents black's sente moves in this area). 

Dia. 9:  Game 4, after white 136 (circle, Lee Sedol is white).

Another example is Lee Sedol's ignorance of a big endgame move by AlphaGo (triangle in Dia. 10) which he replies with an even more binding move (circle in Dia. 10).

Dia. 10:  Game 4, after white 146 (circle, Lee Sedol is white)
About twenty moves later, AlphaGo threatens with a pointless dame point to cut off white's meanwhile large center group (triangle in Dia. 11). In response, Lee Sedol plays a big endgame move settling his group at the same time (circle in Dia. 11). If AlphaGo would have played here first, the program would have gained several points --in sente--. Thus, with this move (triangle in Dia. 11) AlphaGo in fact resigns.

Dia. 11:  Game 4, after white 168 (circle, Lee Sedol is white).
Obviously, AlphaGo's logic is not optimal anymore at all since it plays many forcing moves generated by the meager potential that the opponent might make a mistake (Michael Redmond). After playing a handful of doubtful moves and several mistakes that even lost additional points, AlphaGo resigned (Dia. 12).

Dia. 12:  Game 4, end position after white 180 (Lee Sedol is white). 
Dia. 12 shows the final position after Lee Sedol's move 180, nearly five hours into the game, at which AlphaGo resigned after it's notion that the probabilities of winning this game were falling below it's critical threshold of 10% for resignation. At this point, AlphaGo is behind at least 5 points (komi included) and therefore needs to make more than ~20 points in the bottom center area (without Lee Sedol getting any compensation for that) in order to catch up.

Even though Lee Sedol played under ultra-high pressure for more than one hour (from move 90 on), using his last byo-yomi period up to the max each move, he was able to maintain and solidify his advantage built up in the middle game. This is the first time that AlphaGo lost a game against a top professional Go player (in the official match games without handicap). Lee Sedol's great victory is an extraordinary and historic achievement which has led to the deepest respect and admiration from all over the world.

A Korean Go-pro stated: "Lee Sedol just fought the 1000 years history of Baduk and I am proud of him". An Younggil (8p) concluded that the game was "a masterpiece for Lee Sedol and will almost certainly become a famous game in the history of Go". 

Lee Sedol's win against AlphaGo shows --and does prove for the first time-- that deep learning AlphaGo does not play perfect all the time and sometimes has severe problems in judging correctly complex middle game positions. Despite the considerable pressure, Lee Sedol could play his own game and exposed a clear glimpse of AlphaGo's weaknesses.

During the press conference afterwards, the public and press were wild with enthusiasm and chanted: Lee Sedol!” ”Lee Sedol!” “Lee Sedol!. Several minutes flashing recorded a radiant, visibly overjoyed and genuinely pleased Lee Sedol: "I have never been congratulated so much just because I won one game. Winning this game is still valuable, the drive behind the win today is the trust and the compassion of you all. This one win is so valuable and I will not trade this for anything in the world". 

After the game Lee Sedol answered a question about his mental condition: "after loosing the first three games and thus the match against AlphaGo, I could not say that there was no psychological shock ... but it was not to the extent that I would have to stop playing the ongoing match because at any moment of the game, I really enjoyed the game. I can tell you that I've not retained any severe damage and I'm very happy to say that I won this single game".

And asked what Lee Sedol was thinking when he was played his brilliant move (move 78, Dia. 6): "I thought I would be able to gain some profit quite easily but that wasn't the case. It became more difficult than I had expected and at that point in time, at time of 78th move, that was the only move that I could see, there were no other moves, no other placement that I could think of. That was the only place I could place my stone, it was the only option for me, so I put it there. So I am quite humble for all the praise that I'm getting for that".

Demis Hassabis said: "AlphaGo made a mistake around move 79 but it realized it's mistake only after the 87th move, when it was too late to recover from. AlphaGo thought it was doing very well at the start of the complex center fight but was pressured by Lee Sedol in some mistakes. It is because of the incredible fighting spirit Lee Sedol showed that a creative genius like him is able to find out and exploit any weakness of AlphaGo. The loss by AlphaGo is very valuable: we will look at all the statistics and are looking forward to learn from these weaknesses and fix these problems".

David Silver, Google DeepMind's team leader, added: "We have designed AlphaGo to learn by itself by repeating self-plays. But such an algorithm must have holes in it that we cannot know about. Lee was able to push AlphaGo to expose such a weakness".

Lee Sedol concluded: "I believe AlphaGo has two weaknesses: when I made an unexpected move, AlphaGo responded as if the program had a bug, indicating that the machine lacked the ability to deal with surprises. Furthermore, AlphaGo finds it more difficult to win the game when it has black as opposed to when it has white. Therefore, I would like to ask Demis Hassabis and David Silver: 'would it be possible for me to take black in the last game instead of drawing lots?'". The answer was: "yes, it's fine"

This fourth game of the match was decided by Lee Sedol's profound and fabulous move in a complex middle game fight that forced deep learning AlphaGo to a sequence of mistakes. After this, the game was completely turned around and AlphaGo was unable to defend against all weaknesses exposed in it's center position. After three successive losses against the program, this game Lee Sedol clearly outperformed AlphaGo for the first time: a great and historic achievement by Lee Sedol.  

Sunday, April 24, 2016

Part 8: Review of Game 3: Lee Sedol's opening mistakes due to enormous mental pressure (The historic match of deep learning AlphaGo vs. Lee Sedol)

[NL Versie]

Review of Game  3: Lee Sedol's opening mistakes due to enormous mental pressure

After two successive losses, Lee Sedol is under extremely high pressure not to lose the entire five-game match with AlphaGo. Lee Sedol is heavily touched, very disappointed and feels particular anguish after the shock of his second loss. Both his confusion afterwards about why he had lost the game and the difficulties he had with his team tracing back any mistakes, showed also that AlphaGo played a nearly perfect game.  So, is Lee Sedol able to win from a Go-program that plays virtually perfect?

This match proceeds completely different from what Lee Sedol had expected and hoped. He tries to play with his great sense of responsibility for the hundreds of millions of people worldwide that count on him in this historic match against AI. One way or another he has to turn the tables, but how?

With black 17, a rather complicated opening fight starts in the upper left corner (see Dia. 1). White's invasion inside black's influence is an attempt to reduce the black potential severely, without leaving a weak group that is easy to attack or giving black some advantages otherwise (for instance, to allow for much strength on the outside or territory on the inside). 

Dia. 1:  Game 3, after black 17 (circle, Lee Sedol is black) 
If AlphaGo succeeds in making a solid base with this invasion or a group that easily can extend and escape towards the center, without too many benefits for Lee Sedol, and white's mission proves to be a success, AlphGo can take over the initiative and try to control the game towards victory.

Dia. 2:  Game 3, after white 28 (circle, Lee Sedol is black) 
The opening develops and AlphaGo plays a nice move towards the center meanwhile threatening Lee Sedol's three stones (circle in Dia. 2). As black took the corner and is strong on all sides, everything looks promising for black at this point in the game. However, in this very complicated opening fight in the upper left, Lee Sedol makes a deciding mistake already early in the game. This unfortunate mistake ascertains that the game is pretty much decided shortly after his (at first sight) effective and offensive move (triangle in Dia. 3). 

AlphaGo responds underneath (circle in Dia. 3) to ensure the option to connect later or to be able to attack Lee Sedol later on. This move provides some life-air to the white group as well as possibilities to pressurize black's stones thereabout (triangle in Dia. 3).

Black really had to play first on this point (circle in Dia. 3, instead of triangle) to threaten to connect underneath himself (and keep white weak and separated). And if white then would have responded, black nevertheless would have had (in sente) the opportunity to play the triangle move. In short, a missed opportunity by Lee Sedol which immediately gives AlphaGo the initiative.

Dia. 3:  Game 3, after white 36 (circle, Lee Sedol is black) 
Younggil An (8p) described Lee Sedol's earlier moves as possibly the game-losing moves and Andrew Jackson from the American Go Association considered black 35 (triangle in Dia. 3) as the fatal, losing move. 

Dia. 4:  Game 3, after white 48 (circle, Lee Sedol is black) 
After about fifty moves AlphaGo dictates the game and forces Lee Sedol to continue defending. With 48 (circle in Dia. 4) white also defends his group and at the same time attacks both the black stone left and the black group left (middle).

Obviously, white handles attacking as best defense. Even though white's upper left group is itself still in the danger zone, white is able to escape towards the center. And in case of emergency white can try to make eyes with forcing moves on black's upper left corner. 

Dia. 5:  Game 3, after white 70 (circle, Lee Sedol is black) 
AlphaGo manages to control the fight such that it builds strong influence while attacking, what could the program wish more? Lee Sedol has no other choice since his entire black group on the left, though more or less connected (eventually, later on there is a ko), simply has an inadequate base. With move 69 (triangle in Dia. 5) black escapes to no man's land towards the center where white is waiting for him on every side.

Dia. 6:  Game 3, after white 78 (circle, Lee Sedol is black) 
Lee Sedol creates a base for his 'hanging' group on the left and then starts a counterattack on the right hand side with black 77 (triangle in Dia. 6). By making the position more complex, Lee Sedol might be able to find a solution to deal with AlphaGo's large potential at the lower edge.

Also, white's upper left group is not yet entirely safe and still a significant burden white has to take into account.  AlphaGo's response on Lee Sedol's counterattack is yet effective and cooperates optimally with all white's stones at the right edge. In addition, it's response provides opportunities in case white's group in the upper left later on needs support. 

Dia. 7:  Game 3, after white 90 (circle, Lee Sedol is black) 
To stay in the game Lee Sedol needs to keep AlphaGo from making too many points on the right hand side as well as to prevent getting a half-baked center group whereby his chances for an invasion into white's moyo at the lower edge will become without any prospects.

With 89 (triangle in Dia. 7) black connects more or less the two cutting stones on the right (on P8+9) and at the same time attacks the white group in the upper left. AlphaGo is alert and strengthens it's group immediately with 90 (circle in Dia. 7). It looks like that Lee Sedol should have played here himself first (threatens to cut, makes points and weakens the white group) in sente. However, AlphaGo succeeds in further simplifying the position as the white group in the upper left now has almost sufficient options to live.

Dia. 8:  Game 3, after black 129 (circle, Lee Sedol is black) 
After white lives in the upper left, black in the lower right, and most smoke clouds have disappeared, Lee Sedol's only chance to win the game is to reduce white's huge moyo at the bottom severely (either by living inside or  by dimpling from the outside).

However, AlphaGo stays very calm and plays sophisticated during Lee Sedol's invasion (triangle in Dia. 8). This move gives white a number of opportunities to connect the two white stones either to the left or to the right. Black again complicates the situation to threaten breaking through white's surroundings towards the center,  or to capture the two white stones and try to live. 

Dia. 9:  Game 3, after white 148 (circle, Lee Sedol is black) 
During this complex fight, Lee Sedol manages to get the maximum out of the position by creating, in an ingenious and beautiful manner, a game-winning ko (triangle in Dia. 9). However, AlphaGo again plays calm and efficient: apparently the program has already computed that it will win this ko anyhow. Then white just ignores the ko for now and occupies the largest endgame move on the board (circle in Dia. 9) while threatening to enter black's territory at the upper side. 

Dia. 10:  Game 3, end stand after white 176 (circle, Lee Sedol is black) 
It is for the first time that AlphaGo is forced into a complex and big ko-fight. Despite earlier expectations that the program herewith would suffer from severe problems, AlphaGo plays superb and shows it assesses, computes, and latches ko-fights excellently.  

Unfortunately, Lee Sedol is unable to force AlphaGo into any error, not even a single one. Using internal ko threats, AlphaGo triumphs (as the program already 30 moves ago had evaluated or computed). And after white 176 (circle in Dia. 10) there is no other option for Lee Sedol than to resign. 

Kwon Kay-Yong, one of Lee Sedol's former coaches, told a news agency: "AlphaGo played consistent and well balanced from start to finish while Lee, as he is only human, showed some mental vulnerability". Thereby, Lee Sedol's great feeling of responsibility --towards all people that were watching over his shoulder and had such a great faith in him-- inevitably began to work against him. 

According to Younggil An (8p) and David Ormerod, this third game demonstrated that "AlphaGo is simply stronger than any known human Go player. AlphaGo was seen to capably navigate tricky situations known as ko-fights that did not come up in the previous two matches". Ormerod added: "in the middle of a complex, all-or-nothing ko fight, AlphaGo displayed sufficient 'confidence' that it was winning the fight and simply ignored the ko and played a large move elsewhere". 

During the post-game press conference, where hundreds of photographers exposed Lee Sedol to minutes-long dazzling flashlight, while the loss of the Google DeepMind challenging match was still hammering his mind with this third successive defeat by AlphaGo, Lee Sedol was visibly touched and deeply saddened: "I don't know how to start or what to say today but I think I would have to express my apologies first: I should have shown a better result and better outcome and better contents of the game played. I apologize about not being able to satisfy a lot of people's expectations. I felt powerless. If I would redo the match I probably would not have been able to win".

And: "In the first game I  have lost because I bad judged the capabilities of AG. The second game would be the mental break of you but at the beginning of the 2nd game, the game did flow the way I intended and there were a number of opportunities which I admittedly missed. Looking at the third game: I do have extensive experience in the playing the game of Go but there was never a case or game where I experienced this amount of pressure. I was unable overcoming the amount of pressure I was experiencing. Sure I lost the match, AlphaGo is now a clear winner. However, when when it comes to human beings, there comes in this psychological aspect. If I play the fourth and fifth game of the match, I do ask you to continue keep following the match and keep your interest in the games and follow what happens".

Michael Redmond (9p) commented: "At first, I sort of doubted the capabilities of AlphaGo but after three straight wins these were canned now. Lee Sedol played a very powerful fighting game. In this third game, he played to do his style and showed us an exciting match and I believe that Lee Sedol would have been difficult to beat today by any other top human professional. I think that Lee did his very best and showed us a very good game. Nevertheless, AlphaGo played excellent this fighting game and played the ko's everybody was afraid that it might have a weakness in, played all of the complicated fighting". 

To continue: "I think it is fair to say that it beat Lee Sedol at his own game. What I see in AlphaGo is the potential when it plays new moves as it did in the 2nd game, it's potential to inspire Go players to perhaps study a different type of opening moves. I think we could have a revolution of the years coming up with AlphaGo helping us, giving us a boost to start it. I like to characterize today by my believe that the AlphaGo team created a true work of art".

Hassabis described AlphaGo's victories on Lee Sedol as: "hard to believe" and said the games had been 'mega-tense': "while AlphaGo computes tens of thousands positions per second, Lee Sedol incredibly can compete with that in periods of high pressure. His ingenuity and extraordinary talent have stressed AlphaGo to it's limits during these first three games.  We came here to challenge Lee Sedol as we wanted to learn from him and see what AlphaGo is capable of. And his amazing genius and creative skills have done that". 

And answering a journalist's question, Lee Sedol said: "Although AlphaGo is a strong program, I would not be able to say AlphaGo is a perfect program (not at the level of so called divine Gods). Yes, compared to humans it's moves are different and from time to time are superior but I do feel that there are weaknesses in AlphaGo's way of playing. Today was Lee Sedol's defeat but not a defeat of human beings". 

Google and the Korean Baduk Association, who both organized this match, already agreed earlier on that the match would continue up to and including the fifth game in case the winner of the match would be known after three wins in a row.  

[Part 9: Review of Game 4: Lee Sedol's brilliant move reveals weaknesses AlphaGo]