AlphaGo

Logo of the AlphaGo computer program

AlphaGo is a computer program that plays the board game Go and was developed by DeepMind . It is also known under the pseudonyms Master (P) and Magister (P) . AlphaGo combines machine learning and traversing techniques .

In January 2016 it became known that AlphaGo had already defeated the multiple European champion Fan Hui ( 2nd Dan ) in October 2015 . This makes it the first program under tournament conditions without default (handicap) on a 19 × 19 board a professional Go player to beat. In March 2016, AlphaGo beat South Korean Lee Sedol , who is considered one of the world's best professional players ( AlphaGo versus Lee Sedol ).

background

After the IBM Deep Blue program had beaten the then world chess champion Garri Kasparov in a competition under tournament conditions with 3.5: 2.5 points in May 1997 , Go was the next big challenge for the developers of artificial intelligence systems. Because of the greater complexity of Go compared to chess, which results from the larger board (19 × 19) and the disproportionately larger number of possible moves, Go can be used with traditional brute force algorithms ( alpha-beta search ), i.e. H. by trying out all possible moves, practically impossible to conquer. Another problem was that - unlike chess - there were no expedient heuristic methods for Go to evaluate a given position.

Existing Go programs at the end of the 1990s had a skill level that barely exceeded that of ambitious human beginners.

With the use of so-called Monte Carlo algorithms for a tree search, a breakthrough came from 2006, which led to programs such as Crazy Stone or Zen reaching the strength of very good amateurs. Successes against professional players could also be achieved on a small board (9 × 9) or with four stones given on the standard board. Monte Carlo programs use statistical methods to find train candidates. The move is scored by playing random moves from the position on the board to the end.

AlphaGo marks a significant leap in development compared to previous programs. In 500 games against other programs, including Crazy Stone and Zen, AlphaGo won all but one. In October 2015 there was a comparison match with the reigning European champion and professional Go player Fan Hui , who holds the 2nd professional Dan. AlphaGo won the games 5-0.

architecture

AlphaGo uses deep neural network learning methods in addition to Monte Carlo methods . Two categories of neural networks and a tree search are used:

• The policy network ( "control network") is used to determine Zugkandidaten with large amounts of games both by supervised learning (English. Supervised learning) conditioned as well as by Reinforcement learning (English. Reinforcement learning) training
• The value network ("evaluation network ") is used to evaluate positions and is set through reinforcement learning.
• The Monte Carlo tree search calculates the variants. All three components are combined in this tree search.

The approach differs from current programs in that it can at least in principle also be transferred to other areas of application. First, by analyzing a database of 30 million trains, the program learns to “predict” a person’s train. That succeeds 56%. When evaluating the move, unlike in Monte Carlo programs, it is not necessary to play the game through to the end. With this approach alone, AlphaGo succeeds in defeating traditional programs. In practice, however, the most powerful version of AlphaGo is also assessed using the Monte Carlo method.

In the games against Fan Hui, the distributed version of AlphaGo ran on a computer network with a total of 1,202 CPUs and 178 GPUs and used 40 search threads ( search threads ). In the later matches against Lee Sedol, 1920 CPUs and 280 GPUs were used. To provide the massive computing power required during the learning phase, the Google Cloud Platform and TensorFlow Processing Units ( ASICs for the TensorFlow software collection ) were used.

Famous games

AlphaGo versus Fan Hui

AlphaGo (black) vs. Fan Hui (white). The 4th game on October 8, 2015, AlphaGo won by giving up White.

The first 99 trains (train 96 on train 10)

Trains 100-165

AlphaGo versus Lee Sedol

→ Main article : AlphaGo versus Lee Sedol

From March 9, 2016 AlphaGo competed against the South Korean professional Lee Sedol , 9th Dan. Lee is considered one of the best players in the world right now. The game was played according to the Chinese rating with a Komi of 7.5. AlphaGo won the five-game match 4-1. Lee could only win the fourth game (with white), so that AlphaGo was already the winner after the third win in the third game. All five games ended by giving up. AlphaGo is the first computer program that could defeat a professional player of this skill level - even several times - without a handicap. In February before the event, Lee had announced that he would win "big". After losing the third game, he stated that he was shocked by the computer game and that he felt under a lot of pressure after losing the first two games. He stated it was a personal defeat, but not for humanity.

The tournament was held in Seoul , South Korea , and received a lot of international media attention. Among other things, the games were broadcast live on YouTube streamed and Dan player 9-by the American Michael Redmond commented in English. The winner received a million dollars. AlphaGo's victory bonus is intended to be donated to charity. After the end of the competition, the South Korean Go Association awarded Hanguk Kiwon AlphaGo the highest rank 9p of a 9th professional Dan.

AlphaGo versus Ke Jie

→ Main article : AlphaGo versus Ke Jie

AlphaGo against Ke Jie was a go match at the Wuzhen Future of Go Summit 2017 from 23.-27. May 2017 in Wuzhen , China. The world number one Ke Jie was beaten three times by AlphaGo. During the same period, AlphaGo competed against a team of five top players who could plan each of their moves together. AlphaGo also won this match.

AlphaGo Zero

In October 2017, the AlphaGo developers published the results of the latest AlphaGo development stage. The program called AlphaGo Zero was equipped with modified software and reduced hardware architecture with no prior knowledge of the game, but only with the rules of the game and trained by playing against yourself. Only four tensor processing units were used as hardware for inferencing . AlphaGo Zero was also developed with the help of TensorFlow . It was stronger than the AlphaGo version that Lee Sedol was able to defeat after just 3 days and defeated them 100-0. After 40 days of training, it also hit the youngest and previously strongest expansion stage of the program, AlphaGo Master.

AlphaZero

→ Main article : AlphaZero

In December 2017, the Google company DeepMind introduced the AI AlphaZero. It learned the games chess, go and shogi one after the other within a few hours and was then better than any software that had been developed so far and thus far superhuman. AlphaZero is only trained by programming the rules of the game. AlphaZero then trains against itself for a few hours. Human game strategies are not shown to the AI. The AI ​​develops all game strategies independently. The chess website chess24 commented: The time of the sophisticated chess programs is probably over. The former world chess champion Garry Kasparov said he was amazed at “what one can learn from AlphaZero and basically from AI programs that can recognize rules and methods that have hitherto remained hidden from people.” And “The effects are obviously wonderful and far beyond of chess and other games. The ability of a machine to copy and surpass centuries of human knowledge in a complex, closed system is a tool that will change the world. "

Web links

• AlphaGo - DeepMind. In: deepmind.com. January 28, 2016, accessed November 12, 2018 . 

Press reports

• Tobias Berben: Master (P) alias AlphaGo plays 60: 0 - Go-Baduk-Weiqi.de. In: go-baduk-weiqi.de. January 4, 2017. Retrieved January 8, 2017 . 
• Harald Bögeholz: How Google AI wants to beat people in Go - c't Magazin. In: heise.de. February 26, 2016, accessed March 8, 2016 . 
• Jo Bager: Google's AI AlphaGo wins and wins - heise online. In: heise.de. January 5, 2017, accessed January 5, 2017 . 
• Oliver Fritsch: AlphaGo: “I can no longer recognize who is a person and who is a machine”. In: zeit.de . March 9, 2016, accessed March 9, 2016 . 

Programs

• Minigo on GitHub - An open-source implementation of the AlphaGoZero algorithm
• AlphaGo Teach. In: alphagoteach.deepmind.com. Retrieved November 12, 2018 .  - AlphaGo database

Individual evidence

1. ↑ Elizabeth Gibney: Google reveals secret test of AI bot to beat top Go players. In: nature. Springer Nature Limited, January 12, 2017, accessed April 30, 2020 . 
2. ↑ AlphaGo: Mastering the ancient game of Go with Machine Learning. In: blogspot.com. Retrieved March 11, 2016 . 
3. ↑ Go duel human vs. Software: Technical Ko at Spiegel Online , March 12, 2016 (accessed March 12, 2016).
4. ↑ Zen computer Go program beats Takemiya Masaki with just 4 stones! (No longer available online.) In: gogameguru.com. Go Game Guru, archived from the original on February 1, 2016 ; Retrieved March 11, 2016 (American English). Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.  
5. ↑ Google software defeated Go-Genie in the last match. FAZ, March 15, 2016, accessed on September 13, 2017 . 
6. ↑ ^{a b c} David Silver, Aja Huang u. a .: Mastering the game of Go with deep neural networks and tree search. ( Memento of January 28, 2016 in the Internet Archive ) In: Nature. 529, 2016, p. 484, doi : 10.1038 / nature16961 .
7. ↑ Showdown. In: The Economist . March 12, 2016, accessed March 10, 2016 . 
8. ↑ AlphaGo: using machine learning to master the ancient game of Go. In: Official Google Blog. Retrieved March 10, 2016 (American English). 
9. ↑ Christof Windeck: Google I / O 2016: "Tensor processors" helped win the Go - heise online. In: heise.de. May 19, 2016. Retrieved November 23, 2016 . 
10. ↑ Match 2 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo on YouTube
11. ↑ ^{a b} "He is just human" . In: Tagesschau online , March 12, 2016, accessed on March 13, 2016.
12. ↑ Chen Xieyuan: Lee Sedol Says Not Defeat of Humans after Historic Go Match with AlphaGo. China Radio International, March 13, 2016, accessed on March 13, 2016 (English): "Although losing for a third time, the 33-year-old grandmaster still thinks it is" not a defeat for humans ". "AlphaGo shows the part of its weaknesses, so I doubt whether it has skills that can actually deliver a message to humans. Therefore, I think Lee Sedol is the one who lost today, not humanity." 
13. ↑ dpa / AFP: Google software defeats Go world champion. In: FAZ.net . March 9, 2016, accessed March 9, 2016 . 
14. ↑ bähr / dpa: Go-Genie loses against the computer. In: FAZ.net . March 10, 2016, accessed March 10, 2016 . 
15. ↑ dpa: Go world champion against computer - admitted defeat. In: FAZ.net . March 12, 2016. Retrieved March 12, 2016 . 
16. ↑ Google's AlphaGo gets 'divine' Go ranking . In: The Straits Times.com . March 15, 2016. (English)
17. ↑ Harald Bögeholz: Artificial Intelligence: AlphaGo defeats Ke Jie for the third time - heise online. In: heise.de. May 27, 2017. Retrieved May 28, 2017 . 
18. ↑ Harald Bögeholz: Artificial Intelligence: Five professionals are not enough against AlphaGo . In: Heise online . May 26, 2017.
19. ↑ Mastering the game of Go without human knowledge . Nature . October 19, 2017. Retrieved October 19, 2017.
20. ↑ There is only one opponent left for Google's AI AlphaGo . In: Wired . ( wired.de [accessed on November 11, 2017]).
21. ↑ Michael Nielsen: Alpha Go - computers learn intuition . In: Spectrum of Science . No. 1, January 2018, pp. 22-27. In it: Kevin Hartnett: Mastery through independent learning , pp. 26–27. Both contributions are translations from English: Is AlphaGo Really Such a Big Deal? , Artificial Intelligence Learns to Learn Entirely on Its Own .
22. ↑ Artificial Intelligence: AlphaZero masters chess, Shogi and Go , heise.de from December 7, 2017
23. ↑ Smart computer plays world-class chess - after only four hours , faz.net of December 8, 2017
24. ↑ Practice after just four hours: Artificial intelligence beats the best chess computer in the world , Spektrum.de from December 6, 2017
25. ↑ Artificial intelligence ends human dominance , welt.de of December 13, 2017