Researchers from Google subsidiary DeepMind have published an article in Nature detailing AlphaGo, a Go-playing program that achieved a 99.8% win rate (494 of 495 games) against other Go algorithms, and has also defeated European Go champion Fan Hui 5-to-0. The researchers claim that defeating a human professional in full-sized Go was a feat expected to be achieved "at least a decade away" (other statements suggest 5-10 years). The Register details the complexity of the problem:
Go presents a particularly difficult scenario for computers, as the possible number of moves in a given match (opening at around 2.08 x 10170 and decreasing with successive moves) is so large as to be practically impossible to compute and analyze in a reasonable amount of time.
While previous efforts have shown machines capable of breaking down a Go board and playing competitively, the programs were only able to compete with humans of a moderate skill level and well short of the top meat-based players. To get around this, the DeepMind team said it combined a Monte Carlo Tree Search method with neural network and machine learning techniques to develop a system capable of analyzing the board and learning from top players to better predict and select moves. The result, the researchers said, is a system that can select the best move to make against a human player relying not just on computational muscle, but with patterns learned and selected from a neural network.
"During the match against [European Champion] Fan Hui, AlphaGo evaluated thousands of times fewer positions than Deep Blue did in its chess match against Kasparov; compensating by selecting those positions more intelligently, using the policy network, and evaluating them more precisely, using the value network – an approach that is perhaps closer to how humans play," the researchers said. "Furthermore, while Deep Blue relied on a handcrafted evaluation function, the neural networks of AlphaGo are trained directly from gameplay purely through general-purpose supervised and reinforcement methods."
The AlphaGo program can win against other algorithms even after giving itself a four-move handicap. AlphaGo will play five matches against the top human player Lee Sedol in March.
Google and Facebook teams have been engaged in a rivalry to produce an effective human champion-level Go algorithm/system in recent years. Facebook's CEO Mark Zuckerberg hailed his company's AI Research progress a day before the Google DeepMind announcement, and an arXiv paper from Facebook researchers was updated to reflect their algorithm's third-place win... in a monthly bot tournament.
Mastering the game of Go with deep neural networks and tree search (DOI: 10.1038/nature16961)
Previously: Google's DeepMind AI Project Mimics Human Memory and Programming Skills
(Score: 2) by Mr Big in the Pants on Saturday January 30 2016, @04:06AM
In other words playing aggressively and thus not optimally- it comes from playing...well pretty much every other game out there.
Go is about "gaining" "territory" and the THREAT of invasion while building a strong base (i.e. with two guaranteed "eyes"). It typically isn't till the end game you start the small game.
When you play aggressively you often are playing a weak move and allowing a counter move by the opponent that makes their position stronger while simultaneously ignoring a more broad move that would gain more territory.
Of course playing in a corner means this initial scoping of the territory is very short and then its down to the small game. This is also achieved on the smaller boards.