Jump to content

AlphaGo

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Dcirovic (talk | contribs) at 19:25, 2 February 2016 (Reverted 1 edit by Whazzzup421 identified as test/vandalism using STiki). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
File:Alphago-logo.png
AlphaGo logo

AlphaGo is a computer program developed by Google DeepMind that plays 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]

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]

After IBM's computer Deep Blue beat world chess champion Garry Kasparov in 1997, it took almost two decades for programs using artificial intelligence techniques to be capable of achieving parity with amateur human Go players.[1][2][4] In 2012, the software program Zen, running on a four PC cluster, beat Masaki Takemiya (9p) two times at 5 and 4 stones handicap.[5] In 2013, Crazy Stone beat Yoshio Ishida (9p) at 4 stones handicap.[6]

AlphaGo represents a significant improvement over previous Go programs. In 500 games against other available Go programs, including Crazy Stone and Zen,[7] AlphaGo running on a single computer won all but one.[8] 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.[9] 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 matches 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[9] describing the algorithms used.[2]

AlphaGo is scheduled to challenge South Korean professional Go player Lee Se-dol, who is ranked 9 dan, in March 2016.[4][needs update]

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.[9][1] A limited amount of game-specific feature detection pre-processing is used to generate the inputs to the neural networks.[9]

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, using a database of around 30 million moves from recorded historical games.[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]

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.[13][14] 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.[15]

Similar systems

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

Example game

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

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 "Computer scores big win against humans in ancient game of Go". CNN. 28 January 2016. Retrieved 28 January 2016.
  5. ^ "Zen computer Go program beats Takemiya Masaki with just 4 stones!". Go Game Guru. Retrieved 28 January 2016.
  6. ^ "「アマ六段の力。天才かも」囲碁棋士、コンピューターに敗れる　初の公式戦". MSN Sankei News. Retrieved 27 March 2013.
  7. ^ "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.
  8. ^ "Google AlphaGo AI clean sweeps European Go champion". ZDNet. 28 January 2016. Retrieved 28 January 2016.
  9. ^ a b c d 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.
  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. ^ 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.
  14. ^ "Google's AI beats human champion at Go". CBC News. 27 January 2016. Retrieved 28 January 2016.
  15. ^ Gibney, Elizabeth (2016). "Go players react to computer defeat". Nature. doi:10.1038/nature.2016.19255.
  16. ^ Tian, Yuandong; Zhu, Yan (2015). "Better Computer Go Player with Neural Network and Long-term Prediction". arXiv:1511.06410v1 [cs.LG].
  17. ^ 90210, HAL (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}}: |last= has numeric name (help)
Retrieved from "https://en.wikipedia.org/w/index.php?title=AlphaGo&oldid=702977132"