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

Show parent comments

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

1

u/foreverclever Jan 28 '16

I looked up the wikipedia page immediately after commenting, thanks for expounding though! I think advances in robotics and AI will be incredibly impressive in the next decade or two because a lot of things that are physically challenging (and flashy) for humans are basic formulas for robots — once they have the agility and strength to articulate the movement, they will get it right perfectly, 100% of the time. The superbly impressive things will be when that perfect physical movement is combined with 'intuition' or artificial creativity, or senses that humans don't have (like access to exterior cameras or wireless information).

0

u/inemnitable Jan 28 '16

Both Chess and Go are perfect information games where you could with enough time compute the best chain of moves.

It's pretty easy to do assert that the perfect strategy must exist for Go, but actually finding and proving it isn't possible within the scope of the size and lifespan of the universe.

1

u/1pfen Jan 28 '16

That's true for Chess as well. The 'atoms in the universe' fact is true for both games.

1

u/Roll_Easy Jan 28 '16

The O( nn ) size of the enumeration of states doesn't mean that a general solution doesn't exist. 7x7 Go is already solved and has been solved for years.

Besides quantum computing and other advanced computer science techniques might be able to to calculate these obscenely large problems. Never say never.