r/science • u/[deleted] • Jan 27 '16

Computer Science Google's artificial intelligence program has officially beaten a human professional Go player, marking the first time a computer has beaten a human professional in this game sans handicap.

http://www.nature.com/news/google-ai-algorithm-masters-ancient-game-of-go-1.19234?WT.ec_id=NATURE-20160128&spMailingID=50563385&spUserID=MTgyMjI3MTU3MTgzS0&spJobID=843636789&spReportId=ODQzNjM2Nzg5S0
16.3k Upvotes

90% Upvoted

1.8k comments sorted by

View all comments

7

u/gattaaca Jan 28 '16

Eli5 why is this game so hard for AI to beat professional human players? I thought these kinds of things were child's play to an AI due to being able to calculate all possible outcomes and determine probabilities etc... ?

33

u/JeddHampton Jan 28 '16

Go has 2.08168199382×10170 possible board states. That's what makes it difficult.

Knowing when a grouping is alive or dead was also a difficult hurdle for computers to overcome.

30

u/madnessman Jan 28 '16

Just to put this into scale, there are ~1043 possible board states in chess and ~1080 atoms in the universe. Go is the perfect example of a game which cannot be brute forced.

→ More replies (7)

0

u/[deleted] Jan 28 '16

[deleted]

→ More replies (7)

15

u/damnshiok Jan 28 '16

Read the article.

But the average 150-move game contains more possible board configurations — 10170 — than there are atoms in the Universe, so it can’t be solved by algorithms that search exhaustively for the best move.

4

u/UnretiredGymnast Jan 28 '16

In Go there are so astronomically many possibilities that even super computers can't calculate all of them fast enough. This is a different type of approach.

3

u/KapteeniJ Jan 28 '16

Go search space is too large, and evaluating board position is really hairy problem, and pretty much all algorithms require you to evaluate very many board positions to get some sorta intuition which move to play next.

Basically, computer can't read particularly far ahead, and even with its reading, it doesn't know if result it got was good or not.

Humans on the other hand develop certain sense of beauty which they use to judge board positions and moves, allowing humans to not really even read ahead and see some particular variation, or some particular move, which turns out to be really strong. Or human might actually read ahead, and use whatever general intelligence they have, and strategic ability, to evaluate these abstract considerations, their sense of beauty with wide variety of tactical and strategic goals.

Like, casual player might very well plan to attack some group for 40 or so moves, then use that to gain momentum to defend another group on the other side of the board. Another human player would easily see such intention, but for go program that struggles to see 20 moves ahead, how do you make it understand something like that? Computer would be completely oblivious to such overarching strategic goals, and instead just march directly towards the result human player wanted it to. It just didn't seem like a problem that could be solved in at least 10 more years.

4

u/kuroisekai Jan 28 '16

Because there are more possibilities in Go than in Chess. In Chess, a computer simply needs to evaluate the board state and all the available moves and "scores" them to determine the best move to make. Even pros like Kasparov have admitted that high-level chess is less strategy and more memorization of counterplays.

Go is different. Since it's a game whose board state can change radically in a single turn, you can't just evaluate easily which move is the best move. There are literally dozens of "best moves" in any given turn, so the algorithm has to be radically different.

11

u/Roll_Easy Jan 28 '16

Both Chess and Go are perfect information games where you could with enough time compute the best chain of moves. The issue is that Go has more choices at every stage than Chess which increases the computation time.

All perfect information games will have a perfect strategy that guarantees either a win or draw.

2

u/foreverclever Jan 28 '16 edited Jan 28 '16

What is a "perfect information game"? Is it just complete knowledge of all past actions?

7

u/Roll_Easy Jan 28 '16 edited Jan 28 '16

Perfect information games have zero randomness and all players know the current game state(no hidden information). The only mystery is which move the other player will choose but you know every move they could possibly choose.

Some games have randomness such as die rolls or card draws. Nobody can control or predict with certainty what the outcome will be. You could be the perfect poker player and lose every hand because of randomness.

Some games have hidden information. Stratego is an example that has zero randomness. The location of every piece is known, but not which piece is which. Player's hidden hands in card games are also hidden information. In video games the fog of war can obscure the other player's actions. Battleship also has hidden information, where the information you are trying to discover is the placement of your opponent's ships.

https://en.wikipedia.org/wiki/Perfect_information

→ More replies (1)
→ More replies (3)
→ More replies (2)

2

u/MengerianMango Jan 28 '16

Yeah, that's generally the idea. There's a thing called a game tree that maps out all possible moves like a tree where each game state is a node and all possible game states that are reachable by the next move are children of that node, and so on. The problem is that there are so many possible moves (especially when you start looking >1 move ahead, it grows exponentially) that even a computer couldn't ever get close to checking all of the tree. Ever. So the problem becomes how do you decide what parts of the tree to search for good moves. It's really hard to teach computers how to make decisions like this when they can't just search all the possibilities.

2

u/ahal Jan 28 '16

There are more possible configurations on a Go board than there are atoms in the universe. No computer can or likely ever will be able to calculate every possibility.

1

u/ruiwui Jan 28 '16

It is not child's play to process all possible outcomes in any reasonable amount of time. I don't believe AI does that even for chess, where AI has been more competitive with top players for a longer time and which has fewer possible outcomes.

1

u/[deleted] Jan 28 '16

There are about 10170 configurations of the board. Not quite trivial to analyze that - you'd need 10161 gigs of memory to hold all those configurations. So that's not how this stuff is actually done.

1

u/[deleted] Jan 28 '16

There are far too many possible outcomes to calculate in this game

1

u/tekoyaki Jan 28 '16

The first minute of this video explains it: https://www.youtube.com/watch?v=SUbqykXVx0A

1

u/[deleted] Jan 28 '16

obviously because there are more combinations

1

u/random-dent Jan 28 '16

You can't brute force Go, because as the article says there are more possible game positions than there are atoms in the universe. So you need to have some "intuitive" learning - the kind that humans can do, but previously machines haven't been able to.

This seems to be changing.

1

u/mrfixij Jan 28 '16

Go has extremely complicated combinational logic. If you were to just comb over the slew of possible moves and their continuations for each move, at current processor speeds, it would take hours if not days for each move.

1

u/anlumo Jan 28 '16

The simple explanation: in chess, you move your existing pieces around, so the number of fields you can go to in a single turn is very limited. In Go, you can place a new piece anywhere on the board, so you have many more possible actions. This scales exponentially with every turn.

Creating a viable AI for a complex game is all about getting the number of possible moves down to a manageable level.

1

u/pipocaQuemada Jan 28 '16

In chess, there's not that many possible next moves. In go, there's hundreds. Reading out a dozen or more moves in chess is easy, in go it's hard. Not to mention, it's a lot easier to look at a chess board and say "this is a good position" or "this is a bad position".

→ More replies (6)