Slashdot Log In
Computer Beats Pro At US Go Congress
Posted by
kdawson
on Fri Aug 08, 2008 08:52 AM
from the going-going-gone dept.
from the going-going-gone dept.
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.)
Related Stories
This discussion has been archived.
No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
Full
Abbreviated
Hidden
Loading... please wait.
Computer Beats Pro at a go for US Congress? (Score:5, Funny)
Breaking News (Score:5, Insightful)
misleading title (Score:5, Insightful)
Re:misleading title (Score:5, Informative)
Parent
Bob (Score:5, Funny)
Read below for more details in Bob's account of the match.
Bob's account of the match:
The guy placed a stone, and we were like 'Whoa!', and then the computer placed a stone, and I was like 'No way!', and then the guy placed another stone, and the crowd was all 'Oh! WOW!' and they continued to take alternating turns like that.
It was Go-riffic!
Ease (Score:5, Interesting)
That's the thing that's always fascinated me about Go. It is essentially an extremely simple game gone terribly, terribly wrong. It's got about as many rules as Yahtzee, but is played on a 19x19 board. Compare that to Chess which has a pretty large (8x8) board, but has far more rules.
I'm no expert on computer game programming, but I think that's where some of the difficulty comes into play when building these guys. Chess has a nearly unlimited number of outcomes, however having those sets of rules helps. For example, of the 32 pieces, 16 of them are essentially limited to one space in front of them. In Go, however, the lack of rules means that you're left with the simple mathematical monstrosity of an enormous board.
The book The Immortal Game [amazon.com], aside from being an excellent read, goes into depth about computer programs playing chess, as well as Go and Checkers.
Re:Ease (Score:5, Interesting)
Parent
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.
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:When are they going to get it? (Score:5, Insightful)
Parent
Re:When are they going to get it? (Score:5, Interesting)
I don't think you understand the complexity of the game if you're making statements like that.
That's an interesting thing becasue it's starting to look like we aren't solving these sorts of problems in the simplest way possible. A human going flat out is running on 200W maximum. That super computer is probably using 200W per-processor (when you take into account all the addition equipment needed for memory, switching, cooling etc) and not even playing as well as the human. What that says to me is that we probably aren't approaching the problem correctly.
I suspect that we will need to develop a completely different type of hardware in order for machines to be able to perform well at this type of task. Humans are poor at what computers are good at and vice versa and the two take completely different approaches to processing - perhaps that's a hint to look elsewhere.
Parent
Re:When are they going to get it? (Score:5, Interesting)
The brain has a lot of engineering that puts microchips to shame. If you were to pack transistors as densely and with as little cooling as human neurons, they would melt. On top of this, of course, the amount of processing a neuron can do vastly exceeds that of a transistor. Modeling even a single human brain cell is a major task for a computer.
Furthermore, the connectivity of neurons is much greater than electronic components; each one is connected to thousands of other neurons, nearby an far away, in a way impossible with wires.
A lot of guesses about the equivalent FLOPS of a human brain have centered around naive counting of cells and comparing that with the rather slow switching speed (about 10Hz IIRC). Some estimates came out at about 1 TeraFLOPS but that seems ridiculously small in light of what humans can do that computers still struggle with.
Parent
Re:When are they going to get it? (Score:5, Insightful)
Parent
Re:When are they going to get it? (Score:5, Interesting)
Read a bit on Go algorithms. This one isn't using a dumb search. If it were, the Go program playing this good wouldn't be finished calculating it first move yet... No, this one must have used an extremely advanced search algorithm, very smartly removing unlikely branches of the search.
Unfortunately we're stuck with algorithmically searching for the right move until we have sufficiently large quantum computers, that they can run a go algorithm and do it all at once. This may be impossible in our current universe, due to practical limitations caused by laws of physics (just like building a space elevator on Jupiter may be impossible due to practical limitations of physically possible materials in our universe).
Parent
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...
Parent
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).
Parent
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.
Parent
Re:Moore's Law (Score:5, Informative)
Parent
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.
Parent
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.
Parent
Re:Who cares about 9x9? (Score:5, Informative)
Parent
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.
Parent
Re:ignorance (Score:5, Interesting)
Its mathematical in the same way the weather is mathematical - there is certainly amount of maths that can be done in regard to it, but it won't give in to brute force computation because its just too complex.
If you don't believe me, try and write a Go playing program that plays better than a 6 year old. I did attempt this as part of my AI degree, and it is was one of the hardest things I ever attempted. To think, when I began the project I couldn't understand why my supervisor was laughing at me...
Parent
Re:Holy esoteric, Batman (Score:5, Funny)
How about "computers"?
Parent