Computer Beats Pro At US Go Congress 496
Bob Hearn writes "I was in attendance at the US Go Congress match yesterday where history was made: the go program MoGo, running on an 800-core supercomputer, beat 8-dan professional go player Myungwan Kim in a 9-stone handicap game. Most in the audience were shocked at the computer's performance; it was naturally assumed that the computer would be slaughtered, as usual. Go is often seen as the last bastion of human superiority over computers in the domain of board games. But if Moore's law continues to hold up, today's result suggests that the days of human superiority may be numbered." Read below for more details in Bob's account of the match.
Computers are still a long way from beating the best human players in an even game; nevertheless, today's performance represents a huge stride forward. In the last such high-profile matchup, in 1997, Janice Kim (then 1-dan professional) beat then-champion program Handtalk with a 25-stone handicap. In fact, most of the improvement in the level of computer-go play has happened in just the past few years. Today's top programs, including MoGo, use a Monte Carlo approach: they simulate thousands of random continuations per second from the current position to the end of the game, accumulating statistics in a tree on which moves lead to wins most often. One of the strengths of this approach is that it is highly amenable to parallelization. Thus, today's 800-core incarnation of MoGo is by far the strongest go computer that has yet existed. After the game Myungwan Kim estimated the strength of MoGo as 'two or maybe three dan,' corresponding to a reasonably strong amateur player. (Professional dan ranks are at a much higher level than amateur dan ranks.)
Re:Moore's Law (Score:4, Informative)
Re:Moore's Law (Score:5, Informative)
Re:Who cares about 9x9? (Score:1, Informative)
'scuse me wtf are you talking about a "9x9" game? Can't you read?
Shit, i must be new here
Re:When are they going to get it? (Score:3, Informative)
Re:Moore's Law (Score:5, Informative)
Go is an open game; you have few rules and a lot (that is, A LOT) of possibilities for each move.
That means that predicting moves raises exponentially the more steps you try to predict. In this case, MoGo used borrowed power from some supercomputer and a network to distribute the effort sufficiently, so that the game would be played in a humanly-reasonable time (if I understood correctly).
Moore's law states that computing capabilities grow exponentially also (though probably much slower than the growth in possibilities, required with each subsequent predicted step in the MoGo algorithm).
In this context, it would be reasonable to consider that there will come a time when a supercomputer (by future standards) will not be necessary to generate the same amount of effort.
I don't think he mentioned Moore's law just for the sake of it.
Re:Who cares about 9x9? (Score:5, Informative)
Re:misleading title (Score:5, Informative)
Re:Moore's Law (Score:5, Informative)
Computers that play chess, go, and similar games can't hope to make the best possible move during each turn - there isn't nearly enough time to run through all possible combinations. Instead, they run through many possible moves, propagating it through many additional turns, and eventually pick the best move from that subset that they have considered. Getting the computer to decide on a good move in a reasonable amount of time is a tricky part of tuning the algorithm.
A faster computer, suggested by Moore's Law, would be able to run more iterations or branches of the algorithm per second, which suggests it will be able to come up with better moves that it would otherwise not have time to think up.
Re:9-stone-handycap means what? (Score:4, Informative)
The comparison isn't viable. In chess, a three move head start completely changes the tactical nature of the game. In three moves, a bishop could put the king into a position where it has to capture to get out of check, and now he cannot castle and the whole game falls apart. Go doesn't substantially change its tactical nature by allowing the black player to play initial stones, just makes white's job harder (black always plays first in Go and is always played by whichever opponent is believed to be the weaker player).
The big news here is that 5 years ago, no computer could take on a pro with a *25* stone handicap. That's huge progress.
Re:When are they going to get it? (Score:4, Informative)
PAY ATTENTION: Go is not like other games... (Score:5, Informative)
The difference between Go and other games you may know where computers have surpassed the best human players is the immensity of the search space. On a standard 19x19 board there are 381 spaces, all of which are in play at every move, often including spaces currently occupied but not yet safe from capture. Therefore, within a handful of plies a computer player may be looking at trillions of possible branches. Go is NUMEROUS orders of magnitude more complex than chess from an algorithmic viewpoint.
p.s. Those of you saying "Go what?" are merely revealing your own ignorance. There are at least as many Go players in the world as chess; most of them are in Asia.
Re:ignorance (Score:3, Informative)
Re:Perhaps a little more exposition on this "game? (Score:3, Informative)
There's a professional, who's an expert in programmable metronomes, at the University of Sussex.
The rest is a cheer, "Go Congress!"
At least that's how I parsed it...
Re:what is this game? (Score:3, Informative)
Re:what is this game? (Score:5, Informative)
It's very simple, and very interesting.
In standard form, it's played on a 19x19 board. There are two players, black and white, who each have a large number of stones--small round markers in their color. They take turns placing stones on the intersections of the lines, anywhere on the board. If one player's stones surround another player's stones, the surrounded stones are 'captured' and removed (the basic case of this is that, for a black stone on an intersection, it's surrounded if there are white stones on the immediate neighbour intersections in each cardinal direction--larger groups are surrounded in the same way). At the end, there are no more intersections where a player can place a live stone (i.e., one that is not immediately subject to capture for being surrounded), and the players count the number of live stones of their color on the board; whoever has more live stones, wins.
Handicaps, as mentioned above, are a number of stones already placed on the board at the beginning of the game.
Strategy involves building up formations of stones that cannot be captured. The complexity of it comes from the fact that there are so many different places to put a stone, in so many different sequences--the search space is phenomenally large. Like chess, there are accepted opening strategies and miniature battles that are frequently seen, but overall a game of go is much more varied and fluid.
Re:By the way... (Score:2, Informative)
I wonder if the people who develop these chess and go algorithms ever considered a "training first" approach
Deep Blue was trained by professional Chess masters before it was put up against Kasparov. Learning from previous games is one of Deep Blue's design principles.
Re:Breaking News (Score:2, Informative)
Re:Breaking News (Score:3, Informative)
Re:SGF file? (Score:1, Informative)
Re:SGF file? (Score:3, Informative)
Re:800-Core? (Score:3, Informative)
In Go, you can move nearly anywhere at any time. This means that the possible number of possible board states grows wildly faster than chess (to pick a game with well-known AI techniques). A brute force approach to this problem is like trying to crack a rand() sequence with a brute force approach--the search space is far too large.
Re:ignorance (Score:3, Informative)
Go is a game with a few clear rules and a board with a clear layout. The only reason we humans have to approach it "artistically" is because we lack the processing power to brute force it.
The computer the article talks about also lacks the power to brute force the entire game, so it uses certain rules to parse a search tree. Those rules are pretty directly comparable to the human's "artistic" sense.
Someone who's entire post consists of fuzzy quotes about ill-defined analogies should be careful when calling others ignorant.
Re:Oh, for Christ sake... (Score:1, Informative)
For clarity's sake, lets point out that this is no where near on the level of what happened to Kasparov.
The handicap involved suggests that, at best, the computer was playing at a 1 dan level.
The game itself was also nothing really special for Myungwan Kim, he made a silly mistake early on, playing an old kind of anti-computer go, expecting the computer to keep following him around the board. If anything, it was a win based on the pro underestimating the computer.
That's not to say that this wasn't a huge accomplishment for computer go. However, the general understanding (based on win percentages, etc...) is that ranks in go are exponentially separated.
And even with this new evidence, I've still heard numbers of between 15-30 years bandied, in order to reach the relative level of chess programs.
Re:When are they going to get it? (Score:4, Informative)
I think this is best explainable by analogy. The nematode (C. elegans) is a worm that is about 1 millimeter in length. It has 302 neurons and about 7000 synapses. These are mapped out, its genome is known, it is a very easy species to study. Yet its brain is barely understood in practical terms, e.g. why it would move left as opposed to right.
Now look at the human brain, which has, we believe 100 billion neurons, and even more synapses connecting those neurons together.
If we don't understand the nematode with its 302 neurons, why are we going to understand the complexity of the human brain with its 100 billion neurons? Especially since some scientists believe evolution has help design the brains architecture so that it is getting a large amount of efficiency from those neurons?
Re:When are they going to get it? (Score:2, Informative)
strong computer chess players stopped going at the game randomly and learned to score each position as it stood for strength. go computers still can't do that because people don't fully understand why one position is stronger than another
Apparently, you know very little about chess engines. They have gotten much better at positional evaluation, but brute force is still their primary strength. Also, no sucessful chess engine "goes at it randomly." They generate the entire game tree for a number of plies using various tricks to prune the tree. For example, null-move... what if I got two or three moves in a row? If I can't do anything interesting starting with that pawn push, it probably isn't worth looking at more deeply.
What's interesting is that the latest, greatest commercial chess engine, Rybka 3, *does* use Monte-Carlo analysis quite a bit, because it statistically reveals long-term positional advantages that most engines get wrong. E.g.: sacrificing a piece to open the kingside just looks like material loss to a computer. But then, Monte Carlo analysis looks at random positions resulting from the sac and sees a lot of mates, so the sac is evaluated better than it would be otherwise.
Re:Moore's Law, Best possible move (Score:3, Informative)
This depends on the definition of "best possible move" - is your best choice the one that is the best possible move assuming perfect play by both sides or is the one that maximizes your chance of winning (or degree of winning for those games which have multiple levels of "winning") against this opponent?
If the former, it's a fairly standard result of game theory that in every position there exists a move (or a subset of moves) which maximize the player's expected outcome and/or which pose the most difficult problems to the other player assuming perfect play by both sides. If the latter, then what you say is correct, however if you opponent plays better than expected then your expected outcome may suffer.
Re:When are they going to get it? (Score:2, Informative)
The brain is a fantastic example of a molecular-scale parallel processing machine.
Its a hologram--or a harmonic resonator--or a collection of harmonic resonators--with billions of resonant frequencies. You give it a stimulus, and it the stimulus induces one or more resonances. This is pattern recognition, and that's how we are good at chess without melting our skulls using energy. All of the precalculation has been done when the patterns were put in--our brain just needs the stimulus to recognize them. Some patterns we are born with, like the pattern of a face. Others we acquire (or not), like the Sicilian Scheveningen variation. In this sense, its not a parallel processor. The best chess players don't move pieces around in their heads too much, just like we don't spend a lot of time shuffling letters when we read.
Re:With a 9 stone handicap! (Score:5, Informative)
At any rate, at professional levels ("dan"), it's played with 1 handicap stone for every 3 ranks! So a 2 dan player would only get 2 stones head start against the master in TFA. The computer got 9. Assuming that the game was relatively even matched, that would put the computer's skill barely above the line between casual player and intermediate player.
Mmm. I think you're conflating amateur dan ranks and professional dan ranks. Amateurs are supposed to start at about 30-kyu, then rise up to 1-kyu, after which they enter the amateur dan ranks. 7-dan is usually the highest rank given to an amateur.
A weak or new professional would be ranked at 1-dan, but this is on the professional scale. A 1-dan pro is probably better than a 7-dan amateur.
The game record (Score:2, Informative)