from the going-deep dept.
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)
The mission of Google’s DeepMind Technologies startup is to “solve intelligence.” Now, researchers there have developed an artificial intelligence system that can mimic some of the brain’s memory skills and even program like a human.
The researchers developed a kind of neural network that can use external memory, allowing it to learn and perform tasks based on stored data. The so-called Neural Turing Machine (NTM) that DeepMind researchers have been working on combines a neural network controller with a memory bank, giving it the ability to learn to store and retrieve information.
The system’s name refers to computer pioneer Alan Turing’s formulation of computers as machines having working memory for storage and retrieval of data.
The researchers put the NTM through a series of tests including tasks such as copying and sorting blocks of data. Compared to a conventional neural net, the NTM was able to learn faster and copy longer data sequences with fewer errors. They found that its approach to the problem was comparable to that of a human programmer working in a low-level programming language.
Additional Coverage: http://phys.org/news/2014-10-google-deepmind-acquisition-neural-turing.html
AlphaGo Wins Game 5
AlphaGo played a much more balanced game of Go in Game 5 than in Game 4. During Game 4, AlphaGo was forced into a situation in which it had no good moves left to play against Lee Sedol, and "went crazy" as a result. InGame 5, AlphaGo initially made puzzling moves in the bottom right, and useless ko threats near the middle of the game, but it played a strong endgame.
In gogameguru.com's post-game review of Game 5 is an indication that AlphaGo still has a ways to go:
AlphaGo continued to develop the center from 40 to 46, and then embarked on a complicated tactic to resurrect its bottom right corner stones, from 48 to 58. Though this sequence appeared to be very sharp, it encountered the crushing resistance of the tombstone squeeze — a powerful tesuji which involves sacrificing two stones, and then one more, in order to collapse the opponent's group upon itself and finally capture it. This was a strange and revealing moment in the game.
Like riding a bike
Even intermediate level Go players would recognize the tombstone squeeze, partly because it appears often in Go problems (these are puzzles which Go players like to solve for fun and improvement). AlphaGo, however, appeared to be seeing it for the first time and working everything out from first principles (though surely it was in its training data). No matter where AlphaGo played in the corner, Lee was always one move ahead, and would win any race to capture. And he barely had to think about it.
The simple codebreaking game Mastermind turns 50 this year. Vice goes into some background regarding the now classical game and its heyday.
If you only know Mastermind as a well-worn and underplayed fixture of living room closets and nursing home common areas, you may have no idea just how big this thing was in its early years. Invented in 1970, Mastermind would sell 30 million copies before that decade was up, and boast a national championship at the Playboy Club, a fan in Muhammed Ali, official use by the Australian military for training, and 80% ownership amongst the population of Denmark. "I never thought a game would be invented again," marvelled the manager of a Missouri toy store in 1977. "A real classic like Monopoly."
[...] If you don't know Mastermind at all, i.e. you never lived in Denmark, it's played over a board with a codemaker who creates a sequence of four different colored pegs, and a codebreaker who must replicate that exact pattern within a certain number of tries. With each guess, the codemaker can only advise whether the codebreaker has placed a peg in its correct position, or a peg that is in the sequence but incorrectly placed. According to the game's creators, an answer in five tries is "better than average"; two or fewer is pure luck. In 1978, a British teenager, John Searjeant, dominated the Mastermind World Championship by solving a code with just three guesses in 19 seconds. (In second place was Cindy Forth, 18, of Canada; she remembers being awarded a trophy and copies of Mastermind.)
Mordechai Meirowitz, an Israeli telephone technician, developed Mastermind in 1970 from an existing game of apocryphal origin, Bulls and Cows, which used numbers instead of colored pegs. Nobody, by the way, knows where Bulls and Cows came from. Computer scientists who adapted the first known versions in the 1960s variously remembered the game to me as one hundred and one thousand years old. Whatever its age, it's clear nobody ever did as well out of Bulls and Cows as Meirowitz, who retired from game development and lived comfortably off royalties not long after selling the Mastermind prototype to Invicta, a British plastics firm expanding from industrial parts and window shutters into games and toys.
The story relates a couple of tales of intrigue related to the game.
A year after AlphaGo beat the top Go player Lee Sedol, it is facing the world's current top player Ke Jie in a set of three matches (AlphaGo played five matches against Lee Sedol and won 4-1). AlphaGo has won the first match, so Ke Jie must win the next two matches in order to defeat AlphaGo. Although AlphaGo beat Ke Jie by only half a point in this match, edging out an opponent by a small margin is a legitimate strategy:
Ke Jie tried to use a strategy he's seen AlphaGo use online before, but that didn't work out for him in the end. Jie should've probably known that AlphaGo must have already played such moves against itself when training, which should also mean that it should know how to "defeat itself" in such scenarios.
A more successful strategy against AlphaGo may be one that AlphaGo hasn't seen before. However, considering Google has shown it millions of matches from top players, coming up with such "unseen moves" may be difficult, especially for a human player who can't watch millions of hours of video to train.
However, according to Hassabis, the AlphaGo AI also seems to have "liberated" Go players when thinking about Go strategies, by making them think that no move is impossible. This could lead to Go players trying out more innovative moves in the future, but it remains to be seen if Ke Jie will try that strategy in future matches against AlphaGo.
Although Google hasn't mentioned anything about this yet, it's likely that both AlphaGo's neural networks as well as the hardware doing all the computations have received significant upgrades from last year. Google recently introduced the Cloud TPU, its second-generation "Tensor Processing Unit," which should have not only have much faster inference performance, but now it comes with high training performance, too. As Google previously used the TPUs to power AlphaGo, it may have also used the next-gen versions to power AlphaGo in the match against Ke Jie.
Along with the Ke Jie vs. AlphaGo matches, there will also be a match between five human players and one AlphaGo instance, as well as a "Pair Go" in which two human players will face each other while assisted by two AlphaGo instances. This intended to demonstrate how Go could continue to exist even after Go-playing AI can routinely beat human players.
Also at NPR.
Google DeepMind's AlphaGo Beats "Go" Champion Using Neural Networks
AlphaGo Cements Dominance Over Humanity, Wins Best-Out-of-5 Against Go Champion
AlphaGo Wins Game 5, Wins Challenge Match 4-1 vs. Lee Sedol
AlphaGo Continues to Crush Human Go Players