Pages

Thursday, March 31, 2016

Deep Learning AlphaGo vs. Lee Sedol Match Overview (The historic match of deep learning AlphaGo vs. Lee Sedol)

The most spectacular, remarkable and pioneering match in the history of the most ancient of games has taken place all the while: the Google DeepMind challenging match where AI program AlphaGo  defeated top Go professional Lee Sedol (9p) who has been at the top of the world league for more than fifteen years. According to his own claims Lee Sedol has a Go-board in his head day and night: "if I come up with new strategies I place stones on the board in my head, even when I watch tv, have been drinking, or playing billiards". 

What worldwide is regarded as the most outstanding grand challenge for artificial intelligence, namely mastering the game of Go by computer programs, may have become a closed down chapter with this match. A chapter of searching for more than half a century, inventing new algorithms, translating go principles into manageable concepts for computers, and the development of ever improving programs with only one single goal: playing without handicap against humans without completely being swept off the Go-board.




Deep Learning AlphaGo, itself still in its infancy, is the very beginning of a great revolution in Artificial Intelligence. Barely half a year ago the program beat for the first time in history a Go-pro in an even game: Fan Hui (2p). Now it is ready for the enormous challenge to outperform and to defeat one of the strongest players of the world. DeepMind's ultimate aim  thereby is to disentangle AI completely and make the world a better place (a real advertising message).

With more than 100 million people worldwide who have watched the five games of this historic match online and the hundreds and hundreds journalists, commentators, and reporters who attended the press conferences during the match, you can imagine that uncountable many questions were dying to be asked:

Why is this match so outstanding? How well does AlphaGo play against Lee Sedol? Is the AI program able to play a reasonable game? What is hidden under the hood of AlphaGo? Is the progam able to come up with new and 'creative' moves? Has AlphaGo made some progress since the sometimes malfunctioning version against Fan Hui? How did Lee Sedol prepare himself mentally for this match against AlphaGo? Is he able to detect weaknesses in AlphaGo's way of play and to make use of them? Does Lee Sedol remain himself when playing against an opponent who cannot be seen by him and he doesn't know anything about? Is he able to withstand the psychological pressure of the hundreds of millions that are watching his go-actions closely? Is AlphaGo able to improve even further in the future?



Already being felt as the most wonderful, inspiring, overwhelming and most spectacular match of the 21st century. The games played by Lee Sedol and AlphaGo will be studied and analysed for tens of years to come and as a reference for what will be without doubt one of the biggest landmarks ever achieved in the history of AI.


In this overview article, from a bird's eye view and in a bird flight, everything about and around the historic match between AlphaGo and Lee Sedol, highlights of the games played, how both Lee Seol and Demis Hassabis (and their supporting teams) have been blindsided and blown off completely by AlphaGo's phenomenal strong way of playing as well as by the final match outcome, remarkable background details and telling photo's, what this match is really about, how the world has experienced, processed, and tries to recover from this match, the massive impact that this match is expected to have on both Go and Artificial Intelligence worldwide.


Wednesday, March 30, 2016

Part 1: Details of the Match of the 21st century (The historic match of deep learning AlphaGo vs. Lee Sedol)





Lee Sedol defeated by deep learning AlphaGo in historic match
The most spectacular, remarkable and pioneering match in the history of the most ancient of games has taken place all the while: the Google DeepMind challenging match where AI program AlphaGo  outbraved top Go professional Lee Sedol (9p) who has been at the top of the world league for more than fifteen years. According to his own claimings Lee Sedol has a Go-board in his head day and night: "if I come up with new strategies I place stones on the board in my head, even when I watch tv, have been drinking, or playing billiards". 

What worldwide is regarded as the most as the most outstanding grand challenge for artificial intelligence, namely mastering the game of Go by computer programs, may have become a closed down chapter with this match. A chapter of searching for more than half a century, inventing new algorithms, translating go principles into manageable concepts for computers, and the development of ever improving programs with only one single goal: playing without handicap against humans without completely being sweeped off the Go-board.
Deep Learning AlphaGo, itself still in its infancy, is the very beginning of a great revolution in Artificial Intelligence. Barely half a year ago the program beated for the first time in history a Go-pro in an even game: Fan Hui (2p). Now it is ready for the enormous challenge to outperform and to defeat one of the strongest players of the world. DeepMind's ultimate aim  thereby is to disentangle AI completely and make the world a better place (a real advertising message).

With more than 100 million people worldwide who have watched the five games of this historic match online and the hundreds and hundreds journalists, commentators, and reporters who attended the press conferences during the match, you can imagine that uncountable many questions were dying to be asked:



Why is this match so outstanding? How well does AlphaGo play against Lee Sedol? Is the AI program able to play a reasonable game? What is hidden under the hood of AlphaGo? Is the progam able to come up with new and 'creative' moves? Has AlphaGo made some progress since the sometimes malfunctioning version against Fan Hui? How did Lee Sedol prepare himself mentally for this match against AlphaGo? Is he able to detect weaknesses in AlphaGo's way of play and to make use of them? Does Lee Sedol remain himself when playing against an opponent who cannot be seen by him and he doesn't know anything about? Is he able to withstand the psychological pressure of the hundreds of millions that are watching his go-actions closely? Is AlphaGo able to improve even further in the future?

Already being felt as the most wonderful, inspiring, overwhelming and most spectacular match of the 21st century. De games played by Lee Sedol and AlphaGo will be studied and analysed for tens of years to come and as a reference for what will be without doubt one of the biggest landmarks ever achieved in the history of AI.

In this overview article, from a bird's eye view and in a bird flight, everything about and around the historic match between AlphaGo and Lee Sedol, highlights of the games played, how both Lee Seol and Demis Hassabis (and their supporting teams) have been blindsided and blown off completely by AlphaGo's phenomenal strong way of playing as well as by the final match outcome, remarkable background details and telling photo's, what this match is really about, how the world has experienced, processed, and tries to recover from this match, the massive impact that this match is expected to have on both Go and Artificial Intelligence worldwide.








The Match details: why, what and how? 

Regarded as the outstanding grand challenge for artificial intelligence, Go has been considered for more than halve a century as one of the most difficult games for computers to master due to its sheer complexity which makes brute  force exhaustive search intractable (apart from the fact that there are more possible board configurations than the number of atoms in the visible universe).

On January 27th this year,  pioneering news went all over the world: AI program AlphaGo from Google DeepMind wins landmark five game match against reigning European Champion Fan Hui (2p). Never before, a computer program defeated a Go-prof with 5-0 in formal games without handicap. The most challenging and complex job until now, both for computers and artificial intelligence worldwide, thus appears to be brought to completion. Despite winning the match against Fan Hui, however, AlphaGo showed several weaknesses and the DeepMind team wanted therefore to investigate if they would be able to improve and upgrade AlphaGo's play to come level with that of the top Go professionals of the world. To this end, the DeepMind team also invited Fan Hui to help them to improve the program.

On Feb. 4th Demis Hassabis, head and co-founder of Google's DeepMind, announced in a tweet that AlphaGo will play a match coming March 9-15 against the best human Go player of the last decade: Lee Sedol (9p). This will be the biggest and most spectacular, remarkable, pioneering match in the history of the most ancient of games and for sure will long be referred to as the match of the 21st century. 



Most important goal of this match to the DeepMind team will be to test if an improved version of  AlphaGo can be an equivalent opponent for Lee Sedol and perhaps even will be able to defeat him. Moreover, to find and fix any new weaknesses or  immature types of moves of AlphaGo.  

The overarching and most important long-term goal of the DeepMind team, however, is to develop generic deep learning software that is able to tackle various ultra complex problems from a wide area of research fields including health care, energy, transportation, famine, genetics, physics, and so on, to support human scientists in finding effective solutions. 

Up to now, computer programs never have been able to beat the very best at Go so the match will be also a way of testing and judging the suddenly rapid progress of AI – how far these technologies have come (and perhaps how far they can go), what scientists and engineers have achieved so far in the context of AI.  

One of the most intriguing and remarkable decisions of the DeepMind team while training AlpaGo has been to use a giga collection of  amateur games (≥ 6d to 8-9 dan, this is about 1-2d professional rankings) from the KGS Go Server. While they could have made the choice to use strong pro games instead (including strongest 9p profs of the world). Hassabis has repeatedly stated, confirmed and emphasized that there is –not any-- strong pro game included in the database that AlphaGo used to learn and train from. And specifically: the database doesn't contain any game played by Lee Sedol. Yet, there are at least 85,000 pro games publicly accessible out there, more than half the volume of the 130,000 KGS games that were used to train AlphaGo’s base system.

So let's imagine you have almost unlimited financial resources, one of the most advanced, distributed, and generic cloud computing platform of the world, and really many mega talented  employees (and daughter companies) that are beyond any doubt among the best of the best in state-of-the-art AI research world wide. What on earth could be a reason for you to explicitly –not-- use the largest collections of Go-prof games available nowadays? Usage or copy rights? Costs, or perhaps huge efforts to be able to use these games? Extremely unlikely. Perhaps, the 80,000 pro games (as compared to the 130,000 amateur games) are inadequate or too inhomogeneous for AlphaGo to learn from effectively? Very improbable and unlogical as the convolutional (read simply:coding by means of transformation) neural networks that AlphaGo is based on, are easily capable of extracting autonomously millions of characteristic features from game positions and patterns, even in case of using a relatively small number of, say 50,000 games.

Therefore, wouldn't it be more than obvious for the smart and highly motivated team behind AlphaGo, to go --exclusively-- for collections of professional Go-games, if their main and ultimate goal is to design, develop, train, test, use, and improve the strongest AI program worldwide to play Go in order to try to beat in the end the very best top professionals Go players in the world?  

So there probably is a very simple, logical, inherent, natural, and above all fundamental reason for this: the DeepMind team will investigate and analyse whether the way they designed and trained AlphaGo, i.e. exclusively on the on the basis of amateur games, can result to an 'intelligent' system that is able to play moves (from time to time) that are far beyond the amateur level from which it started to learn from in the first place. 

In other words: if AlphaGo will be able to beat Lee Sedol on the basis of amateur level games only (players that by no means would be able to win from Lee Sedol, not even with three stones handicap), wouldn't that prove that AlphaGo by design and training would have learned --by itself-- new, top-level pro moves and patterns that were absolutely absent and unknown in the original data from which it learned from? That AlphaGo consistently would have developed a playing strength that is demonstrably much stronger than any of the amateurs from whom these games stem? That really would be an incredible breakthrough in AI worldwide and irrefutable proof that deep learning models can become  --better-- than the data you feed them (as opposed to the generally accepted idea that deep learning models --at best-- can be as good as the data you feed them).




The match over five formal games will be played at the Four Seasons Hotel in Seoul, South Korea (games will start at 13h local time: 04h GMT, with rest days on March 11th and 14th). There will be played according to chinese rules (19x19, 7.5 komi) and thinking time will be 2 hours each (plus three periods of 60-second byoyomi). Each game is expected to take around 4-5 hours. The winner of the match receives $ 1M price money. If AlphaGo will be the winner, the prize money will be donated to charities including Unicef. In any case, Lee Sedol will receive at least $150,000 for participating in all the five games, and an additional $20,000 for each win. 

Hassabis explained about the match: “Go is the most profound game that mankind has ever devised. The elegantly simple rules lead to beautiful complexity. Go is a game primarily about intuition and feel rather than brute calculation which is what it makes it so hard for computers to play the game well. Working out who is winning in Go is very hard. A stone’s value comes only from its location relative to the other stones on the board, which changes with every move. 

At the same time, small tactical decisions can have, as every Go player knows, huge strategic consequences later on. There is plenty of structure—Go players talk of features such as ladders, walls and false eyes—but these emerge organically from the rules, rather than being prescribed by them. We are honored and excited to be playing this challenge match against Lee Sedol, a true legend of the game, and whether who wins or lose, we hope that the match will inspire new interest in Go from around  the world.” 

Park Chimoon, Vice Chairman of the Korean Baduk Association (KBA) said: “The whole world is interested in this event as this is the first stage where humans and computers are  competing in intelligence. I am proud that this historical stage is baduk (Go). I hope Lee Sedol will  win this time in order to prove humans’ remarkable intelligence and preserve the mysteries of baduk.” 

The match will be live streamed on DeepMind's YouTube channel as well as broadcasted on TV throughout Asia through Korea's Baduk TV, as well as in China, Japan, and elsewhere. Among others, Match commentators will include  Michael Redmond, the only professional Western Go player to achieve 9p status with over 500 professional wins under his belt, who will commentate in English, and Yoo Changhyuk (9p), Kim Sungryong (9p), Song Taegon (9p), and Lee Hyunwook (8p) will commentate in Korean alternately.




Hassabis stated that "if AlphaGo will win the match against legendary Lee Sedol, I believe that this would mean AlphaGo is better in playing Go than anyone in the world". Lee Sedol said in a first statement he is etremeley joyed and excited to take on the challenge: "I am privileged to be the one to play, but I am confident I can win".

Depending on possible further improvements and development of AlphaGo during the past few months (apart from possible adaptations in AlphaGo specifically focused on Lee Sedol's way of playing) and the enormous processing power that will be used by the DeepMind team during the match, AlphaGo's strength probably will approach that of top players like Lee Sedol. 

Therefore, chances are ultra high that this will be an extremely exciting, thrilling, nerve-racking, exhausting and inspiring match. If AlphaGo will win this match against Lee Sedol, this undoubtedly will be orders of magnitude more sensational and spectacular than it was when AlphaGo won against Fan Hui (or at the time Deep Blue defeated Kasparov).  

[Part 2: AlphaGo under a Magnifying Glass]

Tuesday, March 15, 2016

AlphaGo wins fifth game after not knowing a known tesuji


[NL Versie]

In the fifth and exciting last game of the Google DeepMind challenging match, deep learning AlphaGo played an impressive and very balanced moyo-building game. Even though Lee Sedol had substantial (secure) territory already early in the game and although he was able to thwart AlphaGo's huge moyo plans, the program succeeded in getting enough compensation to stay ahead by a small margin of just a few points. 




Both Lee Sedol and AlphaGo played a very solid opening and after move 40 (circle, white is AlphaGo) the outcome of the game appears completely open from their opposing forces of moyo and territory.

Then AlphaGo miscomputes the effectiveness of a tesuji and looses some points in the bottom right corner. Fortunately, it played those moves in territory already realized by black and it got some sente moves at the outside which would be quite handy if AlphaGo would want to turn it's moyo potential into real territory later in the game.



After Lee Sedol's move (triangle) to keep AlphaGo under pressure in the upper left while at the same time reducing AlphaGo's moyo potential around the center, AlphaGo came up with a great response (move 70, circle) turning around the flow of the game by putting high pressure on black.




Lee Sedol needs to create a living group but in return, AlphaGo adds up strength to gradually help it's moyo building strategy. In a complicated middle game, Lee Sedol is forced to find efficient manners to prevent AlphaGo from realizing it's entire moyo by playing smart reduction moves. He succeeds but it comes at a price after AlphaGo plays a beautiful counter attack move (circle, move 136), putting again ultra-high pressure on Lee Sedol.  





In the final phase of the game, Lee Sedol wonderfully manages to reduce most of the entire moyo built up by AlphaGo (triangle, after move 183). But, despite Lee Sedol's great moyo reduction skills, it is still deep learning AlphaGo that is ahead due to the sufficient compensation it got along the way. 

For the top Go professionals commenting on this fifth game, it is difficult to say where Lee Sedol perhaps made a mistake. But one way or another AlphaGo managed to catch up again after falling behind when misreading a tesuji earlier in the game. Overall, the flow of the game and the way of playing, both of Lee Sedol and AlphaGo, seemed to be very balanced.

In the remaining 100 moves in the endgame, Lee Sedol was unable to overcome his arrears of just a few points. Even though he was ahead on the board, he would lose by about 2.5 points when including white's komi (7.5 points). This was the first time in the match a game developed so close in counting. 


Lee Sedol resigned after move 280 (circle) while less than a handful of small endgame moves were left. This was another stunning and incredible exciting historic game where the distinctions in playing strength between the world's top Go-professional Lee Sedol and deep learning program AlphaGo during the match were most of the time very hard to discover. 


So the final outcome of the match is: AlphaGo defeats Lee Sedol by 4 - 1. A result that only a small minority ( < 10-15%)  of the more than 100 million people worldwide who watched this match online, would have predicted in advance. AlphaGo has impressed all Go players worldwide with rock-solid, deep reading, sometimes unexpected and really wonderful, effective moves in these games.




During the post-match press conference Lee Sedol said: "I am sorry because the match comes to an end". Answering a question about whether the five games might have changed his understanding of the game of Go, Lee Sedol responded: "Basically, I don't necessarily think that AlphaGo is superior to me. I believe there is still more that a human being can do to fight against the AI program. That's why I felt a little bit regrettable because there is more that a human could have shown during this match."

Lee Sedol concluded: "Enjoyment is the essence of Go. I do wonder whether I've always been enjoying the game but I do want to admit that yes, I did enjoy the games against AlphaGo. Creativity of human beings and also all the traditional and classical beliefs that we have had, well I've come to question them a little bit based on my experience with AlphaGo. So I've more studying to do down the road". 


Commentator Chris Garlock remarked: "this match has triggered unprecedented global attention to the game of Go. We could not have asked for a more wonderful or generous gift to this game. The five historic and beautiful games of this once-in-a-lifetime challenging match will be studied over and over again in the years to come, launching what I'm sure is going to be a new era in the most ancient of games. I'm really looking forward to that". 

Sunday, March 13, 2016

Latest Predictions AlphaGo vs. Lee Sedol (9p)

               

[NL Versie] 




Nearly all polls worldwide show the same result:   ~75 - 85 % of all voters is convinced that Lee Sedol will win the coming match against AlphaGo. This is also the prediction of the majority of the participants of a price contest among dutch Go players (over  ~105 participants, organised in cooperation with chess and go shop  'het Paard ' and an ICT company). 




There are, however, many reasons to believe that AlphaGo, since the match about half a year ago, in which European Go Champion Fan Hui (2p) was beaten with 5 – 0, at least will play a few dan grades stronger against Lee Sedol. The estimated actual playing strength of AlphaGo is  ≥ 8th dan prof. 


  • AlphaGo has learned from it's (small) mistakes during the match against Fan Hui
  • improvements to AlphaGo's playing algorithms (for example for move selection and performance evaluation)
  • AlphaGo may be can built now on top of extended joseki and shape libraries 
  • finetuning and extension of AlphaGo's neural network training sessions
  • prevention and circumvention of specific problem situations (e.g. complex ko situations about many points)
  • selection of specific groups of professional Go games, not only from the KGS Go Server but as well (selectively) from other Go servers worldwide
  • improvement of the balance between on one hand AlphGo's neural networks for move selection and position evaluation and on the other hand precise computation through Monte Carlo Tree Search
  • extension of the number of conventional ( > 1202 CPUs) and graphical coprocessors (> 176 GPUs) that the distributed version of AlphaGo can use simultaneously during it's games against Lee Sedol
  • increase of the thinking time (computation time) per person: this match 2 hour p.p. (was 1 hour during the match against Fan Hui) which will be strongly beneficial for AlphaGo (especially towards the endgame)
  • implementation of new ideas and concepts to increase severely the performance of AlphaGo and/or make use of perhaps weaker elements in the way Lee Sedol plays (if these exist at all  since Lee Sedol has won over 68% of his games during ~the last years)
  • extension of the number of studied Go-positions (>60 million) and/or games played (e.g. against itself, ≥ 1.3 million) to increase the accuracy of AlphaGo in reproducing Go-profs moves. It has been shown by the DeepMind group that small improvements in this accuracy do lead immediately to big leaps forward in playing strength 
  • improvement and extension of position filters which determine whether a (subpart of a) position during a game against Lee Sedol is sufficiently being recognized by AlphaGo
  • improvements in reinforcement learning the value of Go moves by more detailed and accurate backpropagation of the final game result to each move and/or position


Despite all possible improvements of AlphaGo during the match against Lee Sedol, I expect that: 

  • Lee Sedol wins at least one game against AlphaGo 
  • the winner of the first game will also be the final winner of the match
  • Lee Sedol will win the match with 3-2 
  • AlphaGo also will win at least one game 
  • Lee Sedol demonstrable (*) will forget to play at least one move that he really had to play immediately, and this will happen at least once EACH game of the match
  • in the endgame, Lee Sedol demonstrable (*) plays less well than AlphaGo and, consequently, in EACH game of the match Lee Sedol will loose points in the endgame
  • at least one game Lee Sedol will reach a position of total resignation (*). Whether he indeed resigns or ultimately wins / loses is irrelevant
  • Lee Sedol has to put in all effort to realize and keep his eventually built profit until the end of the game
  • within one year after the match with Lee Sedol, AlphaGo will play a similar match against a strong 9p prof (possibly Lee Sedol again) and this time AlphaGo will win this match (of the five formal games, AlphaGo will win then at least 3 games).

(*) as for example reviewed by a majority of 10 independent top Go profs (9p) from South-Korea, China and Japan.






And if you do want to make bets about this:  Deep Learning models are as good as the data you feed them. 

Lee Sedol played brilliant and won the fourth game against deep learning AlphaGo


[NL Versie]

For the first time during this five-game match, Lee Sedol was able to take a clear lead after a brilliant move in the second half of the middle game, fighting hard to prevent AlphaGo from making (potential) territory in the center.


Even though Lee Sedol played under ultra-high pressure for more than an hour, using his last byo-yomi period up to the max each move (maximum of 1 minute per move), he was able to maintain his built up advantage until far in the endgame of this fourth game of the match. Finally, AlphaGo resigned after playing a handful of doubtful moves and several mistakes that even lost additional points. 





Top Go-prof Gu Li (9p) described Lee Sedol's move 78 (triangle, Lee Sedol is white) in the fourth game of the match against AlphaGo as a "God's move". Another Go pro commented after Lee Sedol winning this fourth game: "Lee Sedol just fought the 1000 years history of Baduk". 



The way AlphaGo chooses it's next moves on maximizing it's probability of winning (instead of maximizing the difference by which it may win) forces AlphaGo apparently to play suboptimal and perhaps even faulty moves when it's probability of winning the game is falling below a specific threshold (e.g. 50 %). 





This is the final position of game 4 after Lee Sedol's move 180 (circle), the point in the game  at which AlphaGo resigned after it's notion that the probabilities of winning this game were falling below it's critical threshold 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.


When AlphaGo's awareness of being defeated by Lee Sedol was passed to Google DeepMind's team member  and operator Aja Huang (6d amateur), he placed two  stones on the board to let Lee Sedol and the world know that AlphaGo resigned and for the first time lost a game (in the official match games without handicap) against a top professional Go player.


This time, Lee Sedol was able to exploit a sequence mistake fighting AlphaGo while the program was misjudging an important middle game fight and lost a heavy group of stones. In return, AlphaGo just got a pover and rather modest sente move. Commentator Michael Redmond (9p) showed several sequences that AlphaGo could have played instead, which would probably have resulted in a considerable better outcome of this fight for AlphaGo.


Lee Sedol's first win against AlphaGo shows --and does prove for the first time-- that deep learning AlphaGo is not playing perfect all the time and really experienced some severe problems in judging correctly the outcome of a rather complex middle-game fight. Even though the fighting in this game seemed not to be as tough as for instance during the second game of the match where ultra-strong AlphaGo defeated Lee Sedol at his own game of fighting play.


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."