5

Anyone knows the algorithm of AlphaGo? I heard that it's related to neural networks. But don't know the details? So it does not find the solution to win in a deterministic way, right? I think so, because Lee Sedol won one game. Is it true that in chess the DeepBlue solves for the unique solution to win, so there is no way human beings can beat her?

3
  • 2
    Check this Nature's article : nature.com/news/…
    – Kii
    Commented Apr 19, 2016 at 9:20
  • 3
    No, neither of them solves for complete solutions (If they did, that would mean the games were solved!). --- By the way, computers are "it", not "she" (even though the female form has mistakenly been propagated recently.)
    – mafu
    Commented Apr 20, 2016 at 8:43
  • @mafu My automata have genders! (Of course, I'm strongly in favor of aggressive anthropomorphization of algorithmic intelligence;) On a more serious note, I do believe that a distinction can be made between automata that produce other automata (either by recombination of functions, or parthenogenesis), and such automata may be termed "female" to distinguish them from non-reproducing automata.
    – DukeZhou
    Commented Aug 17, 2017 at 23:54

2 Answers 2

Reset to default
11

Here's the AlphaGo team's paper that has all of the details (behind a paywall): http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html

I gave a couple of tech talks about this recently. This one is about how AlphaGo works and the match with Fan Hui 2p: https://www.youtube.com/watch?v=HTDxpxmFRGo

I gave another talk last year about why it's hard to create a good Go AI. This one also briefly explains the rules: http://blog.fogcreek.com/go-and-artificial-intelligence-tech-talk/

5
  • Thank you! And thank you again, to make it more than 15 characters in length.
    – velut luna
    Commented Apr 19, 2016 at 10:21
  • It was so weird reading on the last article, which is only a year old this: "It looks like we’ll probably see a computer than can compete with the best professionals in the next 10 or 15 years."
    – SztupY
    Commented Apr 19, 2016 at 17:06
  • The Deepmind website had the paper without a paywall, but it seems it was removed (or I missed it) - too bad!
    – mafu
    Commented Apr 20, 2016 at 8:45
  • @SztupY : really, what Deepmind did is just adding a lot of hardware thanks to being bought by Google. It's not that much. All algorithms already existed.
    – Kii
    Commented Apr 20, 2016 at 8:57
  • The paper is now freely available: willamette.edu/~levenick/cs448/goNature.pdf (The paywall thing was frustrating!)
    – DukeZhou
    Commented Aug 17, 2017 at 23:58
3

AlphaGo relies heavily on Monte-Carlo Tree Search (MCTS), which is a form of decision making that utilizes random choices as an analog for creativity. Specifically, it allows the algorithm to "think" beyond the bounds of it's rational evaluation procedures. (The random choices are subsequently analyzed and weighted in order to determine which random choices are potentially useful.) Ability to successfully utilize this method to beat the strongest human players is partly a function of supercomputing, in that DeepMind has very fast processors and virtually unlimited memory.

This is quite distinct from solving a game in the Combinatorial Game Theory context.

Specifically: we cannot know if AlphaGo played optimally, only that it played more optimally than Lee Sedol in 4 out of 5 games.

Chess also remains unsolved, but the game has been so intensively studied, and DeepBlue so well developed, that it now seems impossible for a human to prevail.

The unsolved status of these non-trivial games, which are further termed partisan, sequential, deterministic (non-chance), and perfect information, is a function of intractability.

In the case of Go, this means if you converted every atom in the universe into a computing device, and had the entire timespan of the universe to calculate, you still could not express the entire Go gametree. Chess is less complex, but still generally regarded as unsolvable.

The DeepMind paper published in Nature: Mastering the game of Go with deep neural networks and tree search is now freely available.

1
  • Given that Alpha Zero was stronger than Alpha Master, which was stronger than Alpha Go (Lee), we now can be confident that this Alpha Go did not play optimally against Lee Sedol.
    – PJTraill
    Commented Dec 16, 2018 at 23:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .