Jump to content

AlphaGo

From Wikipedia, the free encyclopedia

This is an old revision of this page, as edited by Perl coder (talk | contribs) at 03:26, 29 February 2016 (Minor fix - removed extraneous "as"). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

File:Alphago logo.svg
AlphaGo logo

AlphaGo is a computer program developed by Google DeepMind to play the board game Go. 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.[1][2]

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

History and competitions

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.[1][3]

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 intelligence techniques only reached about amateur 5 dan level,[4] and still could not beat a professional Go player without handicaps.[1][2][5] In 2012, the software program Zen, running on a four PC cluster, beat Masaki Takemiya (9p) two times at 5 and 4 stones handicap.[6] In 2013, Crazy Stone beat Yoshio Ishida (9p) at 4 stones handicap.[7]

AlphaGo represents a significant improvement over previous Go programs. In 500 games against other available Go programs, including Crazy Stone and Zen,[8] AlphaGo running on a single computer won all but one.[9] 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 was using 1,202 CPUs and 176 GPUs, about 25 times as many as the single-computer version.[4] In October 2015, the distributed version of AlphaGo defeated the European Go champion Fan Hui,[10] a 2 dan (out of 9 dan possible) professional, five to zero.[2][11] This is the first time a computer Go program has beaten a professional human player in even games on a full-sized board.[12] The announcement of the news was delayed until 27 January 2016 to coincide with the publication of a paper in the journal Nature[4] describing the algorithms used.[2]

Match against Lee Se-dol

AlphaGo is scheduled to challenge South Korean professional Go player Lee Se-dol, who is ranked 9 dan,[5][needs update] with five games taking place at the Four Seasons Hotel in Seoul, South Korea on 9, 10, 12, 13, and 15 March 2016,[13][14] which will be video streamed live.[15] 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 server located in the United States.[16] The match will adopt the Chinese rules with a 7.5-point komi, and each side will have two hours of thinking time plus three times of 60-second byoyomi.[17]

The winner will get a $1M prize. If AlphaGo wins, the prize will be donated to charities, including UNICEF.[18] Besides the $1M prize, Lee Se-dol will receive at least $150,000 for participating in all the five games and additional $20,000 for each win.[17]

Algorithm

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

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.[10] 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.[1]

Style of play

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

Responses

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.[21][22] Toby Manning, the referee of AlphaGo's match against Fan Hui, and Haijin Lee, secretary general of the International 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.[23]

Similar systems

Google's competitor Facebook has also been working on their own Go-playing system darkforest, also based on combining machine learning and tree search.[20][24] Although a strong player against other computer Go programs, as of early 2016, it had not yet defeated a professional human player.[25]

Example game

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

First 99 moves (96 at 10)
Moves 100-165.

See also

References

  1. ^ a b c d e "Research Blog: AlphaGo: Mastering the ancient game of Go with Machine Learning". Google Research Blog. 27 January 2016.
  2. ^ a b c d "Google achieves AI 'breakthrough' by beating Go champion". BBC News. 27 January 2016.
  3. ^ Schraudolph, Nicol N.; Terrence, Peter Dayan; Sejnowski, J., Temporal Difference Learning of Position Evaluation in the Game of Go (PDF)
  4. ^ a b c d e f 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". Nature. 529 (7587): 484–489. doi:10.1038/nature16961.
  5. ^ a b "Computer scores big win against humans in ancient game of Go". CNN. 28 January 2016. Retrieved 28 January 2016.
  6. ^ "Zen computer Go program beats Takemiya Masaki with just 4 stones!". Go Game Guru. Retrieved 28 January 2016.
  7. ^ "「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる　初の公式戦". MSN Sankei News. Retrieved 27 March 2013.
  8. ^ "Artificial intelligence breakthrough as Google's software beats grandmaster of Go, the 'most complex game ever devised'". Daily Mail. 27 January 2016. Retrieved 29 January 2016.
  9. ^ "Google AlphaGo AI clean sweeps European Go champion". ZDNet. 28 January 2016. Retrieved 28 January 2016.
  10. ^ 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.
  11. ^ "Sepcial Computer Go insert covering the AlphaGo v Fan Hui match" (PDF). British Go Journal. Retrieved 2016-02-01. {{cite web}}: Cite has empty unknown parameter: |month= (help)
  12. ^ "Première défaite d'un professionnel du go contre une intelligence artificielle". Le Monde (in French). 27 January 2016.
  13. ^ "Google's AI AlphaGo to take on world No 1 Lee Se-dol in live broadcast". The Guardian. 5 February 2016. Retrieved 15 February 2016. {{cite web}}: Italic or bold markup not allowed in: |publisher= (help)
  14. ^ "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.
  15. ^ Novet, Jordan (February 4, 2016). "YouTube will livestream Google's AI playing Go superstar Lee Sedol in March". VentureBeat. Retrieved 2016-02-07.
  16. ^ "李世乭：即使Alpha Go得到升级也一样能赢" (in Chinese). JoongAng Ilbo. 23 February 2016. Retrieved 24 February 2016. {{cite web}}: Italic or bold markup not allowed in: |publisher= (help)
  17. ^ a b "이세돌 vs 알파고, '구글 딥마인드 챌린지 매치' 기자회견 열려" (in Korean). Korea Baduk Association. 22 February 2016. Retrieved 22 February 2016.
  18. ^ "Human champion certain he'll beat AI at ancient Chinese game". AP News. 22 February 2016. Retrieved 22 February 2016.
  19. ^ David, Eric (February 1, 2016). "Google's AlphaGo "plays just like a human," says top ranked Go player". SiliconANGLE. Retrieved 2016-02-03.
  20. ^ a b Gibney, Elizabeth (27 January 2016). "Google AI algorithm masters ancient game of Go". Nature News & Comment. Retrieved 2016-02-03.
  21. ^ 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.
  22. ^ "Google's AI beats human champion at Go". CBC News. 27 January 2016. Retrieved 28 January 2016.
  23. ^ Gibney, Elizabeth (2016). "Go players react to computer defeat". Nature. doi:10.1038/nature.2016.19255.
  24. ^ Tian, Yuandong; Zhu, Yan (2015). "Better Computer Go Player with Neural Network and Long-term Prediction". arXiv:1511.06410v1 [cs.LG].
  25. ^ 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.{{cite news}}: CS1 maint: numeric names: authors list (link)
Retrieved from "https://en.wikipedia.org/w/index.php?title=AlphaGo&oldid=707482246"