(비지니스) AlphaGo

출처: https://en.wikipedia.org/wiki/AlphaGo

AlphaGo

From Wikipedia, the free encyclopedia

This article documents a current event. Information may change rapidly as the event progresses, and initial news reports may be unreliable. The last updates to this article may not reflect the most current information. (March 2016)

AlphaGo logo

AlphaGo is a computer program developed by Google DeepMind in London to play the board game Go.^[1] In October 2015, it became the first computer Go program to beat a professional human Go player without handicaps on a full-sized 19×19 board.^[2][3] In March 2016, it beat Lee Sedol in the first three games in a five-game match, the first time a computer Go program has beaten a 9-danprofessional without handicaps.^[4]

AlphaGo's algorithm uses a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play.

Contents

  [hide] 

• 1History and competitions
  • 1.1Match against Fan Hui
  • 1.2Match against Lee Sedol
• 2Hardware
• 3Algorithm
• 4Style of play
• 5Responses
• 6Similar systems
• 7Example game
• 8See also
• 9References
• 10External links

History and competitions[edit]

Go is considered much more difficult for computers to win than other games such as chess, because its much larger branching factor makes it prohibitively difficult to use traditional AI methods such as brute-force search.^[2][5]

Almost two decades after IBM's computer Deep Blue beat world chess champion Garry Kasparov in the 1997 match, the strongest Go programs using artificial intelligencetechniques only reached about amateur 5 dan level,^[6] and still could not beat a professional Go player without handicaps.^[2][3][7] In 2012, the software program Zen, running on a four PC cluster, beat Masaki Takemiya (9p) two times at five and four stones handicap.^[8] In 2013, Crazy Stone beat Yoshio Ishida (9p) at four-stones handicap.^[9]

AlphaGo represents a significant improvement over previous Go programs. In 500 games against other available Go programs, including Crazy Stone and Zen,^[10] AlphaGo running on a single computer won all but one.^[11] In a similar matchup, AlphaGo running on multiple computers won all 500 games played against other Go programs, and 77% of games played against AlphaGo running on a single computer. The distributed version in October 2015 was using 1,202 CPUs and 176 GPUs,^[6] and Google has not publicly explained what hardware and software changes have improved its performance from October 2015 to March 2016, so the March matches may well make use of significantly more hardware.

Match against Fan Hui[edit]

In October 2015, the distributed version of AlphaGo defeated the European Go champion Fan Hui,^[12] a 2 dan (out of 9 dan possible) professional, five to zero.^[3][13] This is the first time a computer Go program has beaten a professional human player on a full-sized board without handicap.^[14] The announcement of the news was delayed until 27 January 2016 to coincide with the publication of a paper in the journal Nature^[6] describing the algorithms used.^[3]

Match against Lee Sedol[edit]

Main article: AlphaGo versus Lee Sedol

AlphaGo is currently challenging South Korean professional Go player Lee Sedol, who is ranked 9 dan,^[7] with five games taking place at the Four Seasons Hotel in Seoul, South Korea on 9, 10, 12, 13, and 15 March 2016,^[15][16] which will be video streamed live.^[17] Aja Huang, a DeepMind team member and amateur 6-dan Go player, will place stones on the Go board for AlphaGo, which will be running through Google's cloud computing with its servers located in the United States.^[18] The match will adopt theChinese rules with a 7.5-point komi, and each side will have two hours of thinking time plus three 60-second byoyomi periods.^[19] The version of AlphaGo playing against Lee uses 1,920 CPUs and 280 GPUs.^[20]

The winner will get a $1M prize. As AlphaGo has won, the prize will be donated to charities, including UNICEF.^[21] Besides the $1M prize, Lee Sedol will receive at least $150,000 for participating in all the five games and an additional $20,000 for each win.^[19]

Three games of the match have been played so far, all of which were won by AlphaGo following resignations by Lee Sedol.^[22][23]

Hardware[edit]

AlphaGo was tested on hardware with various numbers of CPUs and GPUs, running in asynchronous or distributed mode. Two seconds of thinking time is given to each move. The resulting Elo ratings are listed below.^[6]

Configuration and performance

Configuration	Search threads	No. of CPU	No. of GPU	Elo rating
Asynchronous	40	48	1	2,151
Asynchronous	40	48	2	2,738
Asynchronous	40	48	4	2,850
Asynchronous	40	48	8	2,890
Distributed	12	428	64	2,937
Distributed	24	764	112	3,079
Distributed	40	1,202	176	3,140
Distributed	64	1,920	280	3,168

Algorithm[edit]

AlphaGo's algorithm uses a combination of machine learning and tree search techniques, combined with extensive training, both from human and computer play. It usesMonte Carlo tree search, guided by a "value network" and a "policy network", both implemented using deep neural network technology.^[2][6] A limited amount of game-specific feature detection pre-processing is used to generate the inputs to the neural networks.^[6]

The system's neural networks were initially bootstrapped from human game-play expertise. AlphaGo was initially trained to mimic human play by attempting to match the moves of expert players from recorded historical games, using a database of around 30 million moves.^[12] Once it had reached a certain degree of proficiency, it was trained further by being set to play large numbers of games against other instances of itself, using reinforcement learning to improve its play.^[2]

Style of play[edit]

AlphaGo has been described by the 9-dan player Myungwan Kim as playing "like a human" in its games against Fan Hui.^[24] The match referee Toby Manning has described the program's style as "conservative".^[25]

Responses[edit]

AlphaGo has been hailed as a landmark development in artificial intelligence research, as Go has previously been regarded as a hard problem in machine learning that was expected to be out of reach for the technology of the time.^[26][27] Toby Manning, the referee of AlphaGo's match against Fan Hui, and Hajin Lee, secretary general of theInternational Go Federation, both reason that in the future, Go players will get help from computers to learn what they have done wrong in games and improve their skills.^[28]

Similar systems[edit]

Facebook has also been working on their own Go-playing system darkforest, also based on combining machine learning and tree search.^[25][29] Although a strong player against other computer Go programs, as of early 2016, it had not yet defeated a professional human player.^[30] darkforest has lost to CrazyStone and Zen and are estimated to be of similar strength to CrazyStone and Zen.^[31]

Example game[edit]

AlphaGo (black) v. Fan Hui, Game 4 (8 October 2015), AlphaGo won by resignation.^[6]

First 99 moves (96 at 10)

Moves 100-165.

See also[edit]

• Go and mathematics
• Deep Blue (chess computer)
• Chinook (draughts player), draughts playing program
• TD-Gammon, backgammon neural network

References[edit]

1. Jump up^ http://www.bbc.com/news/technology-35785875
2. ^ Jump up to:^{a b c d e} "Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning". Google Research Blog. 27 January 2016.
3. ^ Jump up to:^a b c d "Google achieves AI 'breakthrough' by beating Go champion". BBC News. 27 January 2016.
4. Jump up^ "Match 1 - Google DeepMind Challenge Match: Lee Sedol vs AlphaGo". 8 March 2016.
5. Jump up^ Schraudolph, Nicol N.; Terrence, Peter Dayan; Sejnowski, J., Temporal Difference Learning of Position Evaluation in the Game of Go (PDF)
6. ^ Jump up to:^{a b c d e f g} Silver, David; Huang, Aja; Maddison, Chris J.; Guez, Arthur; Sifre, Laurent; Driessche, George van den; Schrittwieser, Julian; Antonoglou, Ioannis; Panneershelvam, Veda. "Mastering the game of Go with deep neural networks and tree search". Nature529 (7587): 484–489. doi:10.1038/nature16961.
7. ^ Jump up to:^a b "Computer scores big win against humans in ancient game of Go". CNN. 28 January 2016. Retrieved 28 January 2016.
8. Jump up^ "Zen computer Go program beats Takemiya Masaki with just 4 stones!". Go Game Guru. Retrieved 28 January 2016.
9. Jump up^ "「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる　初の公式戦". MSN Sankei News. Retrieved 27 March 2013.
10. Jump up^ "Artificial intelligence breakthrough as Google's software beats grandmaster of Go, the 'most complex game ever devised'". Daily Mail. 27 January 2016. Retrieved 29 January2016.
11. Jump up^ "Google AlphaGo AI clean sweeps European Go champion". ZDNet. 28 January 2016. Retrieved 28 January 2016.
12. ^ Jump up to:^a b Metz, Cade (2016-01-27). "In Major AI Breakthrough, Google System Secretly Beats Top Player at the Ancient Game of Go". WIRED. Retrieved 2016-02-01.
13. Jump up^ "Sepcial Computer Go insert covering the AlphaGo v Fan Hui match" (PDF). British Go Journal. Retrieved 2016-02-01.
14. Jump up^ "Première défaite d’un professionnel du go contre une intelligence artificielle". Le Monde (in French). 27 January 2016.
15. Jump up^ "Google’s AI AlphaGo to take on world No 1 Lee Sedol in live broadcast". The Guardian. 5 February 2016. Retrieved 15 February 2016.
16. Jump up^ "Google DeepMind is going to take on the world's best Go player in a luxury 5-star hotel in South Korea". Business Insider. 22 February 2016. Retrieved 23 February 2016.
17. Jump up^ Novet, Jordan (February 4, 2016). "YouTube will livestream Google’s AI playing Go superstar Lee Sedol in March". VentureBeat. Retrieved 2016-02-07.
18. Jump up^ "李世乭：即使Alpha Go得到升级也一样能赢" (in Chinese). JoongAng Ilbo. 23 February 2016. Retrieved 24 February 2016.
19. ^ Jump up to:^a b "이세돌 vs 알파고, ‘구글 딥마인드 챌린지 매치’ 기자회견 열려" (in Korean). Korea Baduk Association. 22 February 2016. Retrieved 22 February 2016.
20. Jump up^ "Showdown". The Economist. March 12, 2016.
21. Jump up^ "Human champion certain he'll beat AI at ancient Chinese game". AP News. 22 February 2016. Retrieved 22 February 2016.
22. Jump up^ "Google’s AI beats world Go champion in first of five matches - BBC News". BBC online. Retrieved 9 March 2016.
23. Jump up^ "Google AI wins second Go game against world champion - BBC News". BBC online. Retrieved 10 March 2016.
24. Jump up^ David, Eric (February 1, 2016). "Google’s AlphaGo "plays just like a human," says top ranked Go player". SiliconANGLE. Retrieved 2016-02-03.
25. ^ Jump up to:^a b Gibney, Elizabeth (27 January 2016). "Google AI algorithm masters ancient game of Go". Nature News & Comment. Retrieved 2016-02-03.
26. Jump up^ Connor, Steve (27 January 2016). "A computer has beaten a professional at the world's most complex board game". The Independent. Retrieved 28 January 2016.
27. Jump up^ "Google's AI beats human champion at Go". CBC News. 27 January 2016. Retrieved28 January 2016.
28. Jump up^ Gibney, Elizabeth (2016). "Go players react to computer defeat". Nature.doi:10.1038/nature.2016.19255.
29. Jump up^ Tian, Yuandong; Zhu, Yan (2015). "Better Computer Go Player with Neural Network and Long-term Prediction". arXiv:1511.06410v1 [cs.LG].
30. Jump up^ HAL 90210 (2016-01-28). "No Go: Facebook fails to spoil Google's big AI day". The Guardian. ISSN 0261-3077. Retrieved 2016-02-01.
31. Jump up^ http://livestream.com/oxuni/StracheyLectureDrDemisHassabis

External links[edit]

• Official website

Categories: 

• Artificial intelligence
• Computer Go
• Go software
• Machine learning
• Google
• 2015 software

• This page was last modified on 12 March 2016, at 15:54.