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:When are they going to get it? (Score:5, Insightful)
Breaking News (Score:5, Insightful)
misleading title (Score:5, Insightful)
Re:Beating nerds at their own game? (Score:5, Insightful)
No, it's not - the computer is running an algorithm designed by at least one nerd. By designing that algorithm, not the computer, but the programmer beat the other player, by using his intelligence for writing a program that plays for him.
As long as computers cannot think for themselves, no computer will beat a human player, but a human-designed algorithm will. Humans beat humans (using technology).
800-Core? (Score:4, Insightful)
Re:ignorance (Score:4, Insightful)
Go is often seen as the last bastion of human superiority over computers in the domain of board games.
That's just plain ignorance. Games usually employ a discrete set of rules and a discrete playing environment. If there is something a computer is good at it would be working with things like this.
You're right, and that's exactly what the text says. In the domain of games, computers do failry well, except for Go. Go's the last bastion of human superiority in that domain.
Re:ignorance (Score:5, Insightful)
In the words of the novel Shibumi, "Go is to chess as philosophy is to double-entry accounting."
Trying to teach a computer to play Go has, up to this point, been about like trying to teach a computer how to evaluate a painting. And, judging by the computing resources required, it sounds like all they did here was brute-force it, so they really haven't "taught" the computer anything.
Moore's Law? Irrelevant (Score:5, Insightful)
Oh, for Christ sake... (Score:5, Insightful)
...just like what happened with Kasparov, the headline is completely backwards.
How about this one: Computer needed 800 processors, at 4.7 Ghz, 15 Teraflops to beat a professional Go player.
We're talking about a computer needing gargantuan processing power to beat a human and we are impressed at the computer? Seriously?
If I am to be impressed by something, it's definitely by this Myungwan Kim guy.
Re:When are they going to get it? (Score:5, Insightful)
Less than a hundred years ago scientists believed the brain worked a bit like a mechanical device and analogies were made to levers, cogs etc. The brain has always been likened to the most advanced piece of technology available at the time, and it's always turned out that it's way more advanced. I see no reason why that shouldn't be the case with all the silly computer analogies people come up with these days...
Re:ignorance (Score:3, Insightful)
Re:Beating nerds at their own game? (Score:5, Insightful)
Up until you use genetic programming to design the algorithm that wins.
Unless you believe that the creator of the human race is 100% responsible for all human action, of course.
Re:When are they going to get it? (Score:4, Insightful)
A good Go method is one that wins - not (necessarily) one that wins the way you would play.
Re:When are they going to get it? (Score:5, Insightful)
Re:When are they going to get it? (Score:4, Insightful)
Because today we actually know a lot more about how neurons work, compared to a hundred years ago? Just because a few clueless people made a wrong analogy a hundred years ago doesn't mean we should generalise that and say that all analogies involving the brain will be wrong (that makes no sense at all). Obviously the brain can't be infinitely complex, so if we keep refining our models of how the brain works we're bound to get it right at some point in the future.
Re:When are they going to get it? (Score:2, Insightful)
Yes! I've got it. All we have to do is teach computers intuition which is how quite a few good players I know play. [/sarcasm]
I suspect playing go well is related to creativity. Show me a program with creativity. Randomness doen't cut it, and you can't model a brain with a computer. Its not the "too complex" problem - it's the too different problem. Brains!=computers.
Re:Beating nerds at their own game? (Score:3, Insightful)
Re:When are they going to get it? (Score:0, Insightful)
Re:800-Core? (Score:5, Insightful)
The history of computer chess is the history of building brute force engines and then refining them by identifying where processing power is successful at winning. Brute force allows you to look at a lot of moves, but how the programs scores the outcomes of those moves as desirable is a different matter that has nothing to do with processing power (e.g., scoring for area of control).
What humans seem to do well is radically pruning the search tree to the small number of viable lines of play, and spending our limited processing power analyzing those in depth. Once you've got a computer searching a large search space in depth, you can work on pruning it by teaching it to recognize useless lines.
With a 9 stone handicap! (Score:5, Insightful)
Well, while theoretically I see your point, sometimes that's harder than it sounds. And in this case it just didn't happen. The computer did _not_ in fact even play at master level at all.
I think what everyone seems to miss is that the computer was given a 9 stone head-start there.
That's not exactly identical, but similar enough for a bad analogy, with being allowed to move 9 times in a chess game before the opponent even starts. So with that huge advantage, your program managed to beat a chess master. Yay. Big f-ing deal.
No, seriously. A 9 move advantage is _immense_. The first moves are where you stake your claims and influence over whole quarters of the board. If you look at the start of that game, white from the start had to challenge relatively strong positions of the computer. (For that stage of the game.)
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.
To give a chess comparison again, it barely ranks above winning a chess game against your high school's prom queen. Ok, ok, a little higher than that, but not by much.
Mind you, it's still an achievement that they managed to program it to even play at intermediate level. Kudos and all that. But let's get not get too carried away with the "OMG, it beat a go master" line of thought. We can celebrate that when it beats one in an even game. We're still _far_ from that.
Re:Holy esoteric, Batman (Score:3, Insightful)
Re:When are they going to get it? (Score:5, Insightful)
I think you are approaching the problem wrong. I can't, ever, calculate as fast as a computer can. forget a modern computer, I can't calculate as fast as the oldest computers out there (and I'm betting you can't either). I have no doubt about your inability to beat computers at raw calculation speeds either (and if you could, more processors means you don't).
the problem is, when I play chess (or the coule times I've tried go), I don't sit there and randomly think of each and every move out there. inthe beginning of the game I don't think about taking my queen out and making 4 moves with her in a row and returning her to where she started.
according to the description, that ist he equivalent of what this computer is doing. monte carlo simulations of the game from current position and look for the move with the most winning nodes. but that is worthless if you can't build logic to ignore useless moves.
I am amazed at the number of possibilities a computer can look at in a second and astounded that something has the excess computational ability and memory to waste time considering such moves.
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 (not always, but almost never in an algorithmic way). the need for such massive computational power simply implies we don't understand the dynamics of the game in a rational way (rather, we understand it on a more creative level).
Re:PAY ATTENTION: Go is not like other games... (Score:2, Insightful)
Gee, thanks for that sneering, condescending enlightenment. I'm sure everyone is feeling better at having Go explained by someone so vastly superior to the rest of us.
Re:When are they going to get it? (Score:5, Insightful)
Fine. Your brain consists of a finite number of neurons, each of which can make connections with a finite number of other neurons. The way each neuron works is defined by a finite set of rules in your DNA, and since each neuron is made out of a finite number of molecules, the number of states it can be in is finite.
Now all the above numbers will be extremely large, and will overestimate the complexity of the brain a LOT, since large parts of your neurons will be irrelevant to the workings of your brain, and so are many neurons and their connections (I lose tens of thousands of neurons each day without getting significantly more stupid than I already am). Still, they are all finite.
Please explain how the thing could be infinitely complex, and why it would be?
Re:Oh, for Christ sake... (Score:3, Insightful)
800 processors? That computer is a toy compared to this Kim guy's brain, when doing a massively parallel task like Go.
That computer is seriously impressive.
Re:misleading title (Score:3, Insightful)
The thing about a nine+ stone handicap is, as the number of handicap stones goes down, the difficulty increases disproportionately for the weaker player.
There's a much bigger difference moving from four stones to two than there is moving from nine to seven.
Nine stones is still a pretty enormous handicap (the maximum normally allowed), so moore's law or not, I dount we'll see a computer beat a pro in an even game anytime soon.
not a serious game (Score:3, Insightful)
Re:I'm not impressed (Score:5, Insightful)
You seem to be saying the computer and the human both succeed due to the "the sheer size of the network of simple elements it consists of". Therefore you're not impressed by one of them?
"but there's never any real thought behind it."
Why do you assume there is thought behind you? If the machine plays Go, it plays Go. I think it's highly doubtful AI research will ever do anything at all in the judgment of critics who insist it must not only achieve things, but achieve them in ways that are not defined or understood.
Re:Bah! (Score:3, Insightful)
Knowledge about the complexities of the game is not required for the machine to win with this method, and that makes me call bullshit.
Actually, this is a good thing. Before Monte Carlo methods started to dominate Go (about 2 years ago), all the top programs were written with human-coded expert knowledge. Progress was extremely slow and didn't keep up with advances in computer hardware. It took decades of man-labor to achieve a moderate success, which was all surpassed in a couple of years by MoGo.
Furthermore, hardly any advances were being made in Artificial Intelligence, since most of the work involved adding specialized domain knowledge that only applied to Go.
What's really exciting here is that such a simple method works in a game that people thought was beyond brute force. Tactics, strategy, "expert" knowledge can be discovered without hand-coding them. With computers going the massively parallel route this is a very big deal.
Re:When are they going to get it? (Score:3, Insightful)
You've got it backwards. Make it work, then make it efficient. How the hell can you make an efficient and correct algorithm if you don't know how to make a correct algorithm?
It's the old software engineering saw on optimization: "To amateurs: Don't do it. To experts: Don't do it yet."
Re:With a 9 stone handicap! (Score:2, Insightful)
Re:When are they going to get it? (Score:4, Insightful)
1) You assume that the number of states of a neuron is finite. Neurons are analog and not digital, so this is a false assumption.
Neurons act by pumping finite numbers of predictably charged molecules through membranes to build up or reduce potential differences across those membranes. Other chemical reactions vary the balance of proportions of molecules in different areas of the neuron, making this action harder or easier. The number of such molecules available to each neuron is large but finite. Therefore the number of possible states of a neuron is finite.
2) Related to the above, neurons are continually exchanging chemicals through their walls. The level of excitation of a neuron is not a single number, but a series of traveling waves. These depend on its inputs and also the chemical makeup in the local area around the axon. Again, infinite variation is quite possible.
No, it isn't. There are a finite number of points where the various chemicals involved in neural activity can cross the walls, and again each of these molecules represent a finite and quantifiable change to the behaviour of the nueron. The number of possible variations is extraordinarily high, but not infinite.
3) No neurons are irrelevant to the workings of the brain. Every neuron lost causes minute, possibly undetectable changes in thought patterns and personality.
If it is undectable, it is irrelevant. Yes, there must logically be some maximal set of neurons that could be lost from a particular brain before a measurable change would occur, but that set is not empty. It is theoretically possible to reduce the complexity of the problem by removing this set (or a larger one, given that some maximum allowable change can be defined).