Slashdot Mirror
Computer Beats Go Champion
Koreantoast writes: Go (weiqi), the ancient Chinese board game, has long been held up as one of the more difficult, unconquered challenges facing AI scientists... until now. Google DeepMind researchers, led by David Silver and Demis Hassabis, developed a new algorithm called AlphaGo, enabling the computer to soundly defeat European Go champion Fan Hui in back-to-back games, five to zero. Played on a 19x19 board, Go players have more than 300 possible moves per turn to consider, creating a huge number of potential scenarios and a tremendous computational challenge. All is not lost for humanity yet: DeepMind is scheduled to face off in March with Lee Sedol, considered one of the best Go players in recent history, in a match compared to the Kasparov-Deep Blue duels of previous decades.
When I first read the headline, I pictured a robot's arms flailing about, whacking its human competitor upside the noggin. "So, A.I. finally got the emotion thing down."
Table-ized A.I.
What makes this especially interesting, is the victory was not achieved with the sort of brute-force approach used by Deep Blue in chess. This used a deep neural net, and algorithms similar to how we believe that humans think. Last time I heard about this, they could consistently beat humans on a 9x9 board, and were working on 13x13. I was surprised to hear that can already win on a full sized 19x19 board. I thought that was still a few years away. This is amazing progress.
I've read the paper.
It doesn't quite use a "brute-force" approach, but it certainly does use significant, and intelligently designed, Monte Carlo searches which are informed by well-trained neural networks. The neural-network alone approach, without any Monte Carlo search during play, is not as strong, though it does appear to equal a state of the art conventional Go program. See Figure 4b.
And the training of the neural networks and construction of their training sets certainly did need quite a bit of 'brute force' as well as 'efficiently wielded force in large quantity'.
No, this is not an accurate understanding of Go strategy or how it is played at the highest level.
In fact, if the game is played in the way you describe, previous computer algorithms were quite good at analyzing the local interactions of pieces, yet were roundly defeated even by top-level amateurs with handicaps. The reason is that at more sophisticated levels of play, one's skill level is correlated with how one perceives and evaluates the entire board. There is a sort of "gestalt" of Go that good players seem to grasp in ways that are very difficult to objectively describe, and sometimes a stone placement can seem arbitrary but become pivotal many, many moves later. This is reflective of a deep and global strategy that computer algorithms--at least until now, it seems--have had tremendous difficulty in emulating.
There is a name for this "not AI" comment: The AI effect. Basically, whatever can be done with a machine is automatically considered "not AI", because it's no longer magical, just engineering.
https://en.wikipedia.org/wiki/...
As wickerprints pointed out, this is completely false. A good move in a local position in Go may not be the best move overall and may, in fact, be a bad move when other areas on the board are taken into consideration. If a computer program split the board into smaller and smaller sections it could very easily get confused by a good player. Also, the number of moves possible at any given time in Go is exponentially higher than in Chess; you can brute force every possible path in Chess, you can't (not yet) in Go. It wasn't that it was more popular; it was much easier.
-SaNo
I googled Fan Hui: one source says he's 8 dan amateur, another that he's 2 dan pro. That's only a little bit better than go programs have been for several years, and much weaker than the best professional players. If he's a top player in Europe, that mostly says that go isn't played at a very high level in Europe. I think that the progress that has been made on go software is really great, but the claim to have beat a 'go champion' seems a bit of a spin.
let's play global thermonuclear war
If the computer could beat a 2-dan professional, then it's clearly even smarter than SHODAN!
Good luck with that. I mean, people have only been trying that for ...
The first computer-Go programmer I met and played against was in 1984. He was trying to do that, on IIRC a BBC Micro with 128kb of RAM.
I've been following the subject since then. Shockingly, you describe EXACTLY the process that most people have tried to implement. It was only about a decade ago that their progress crept ahead of my playing level. But since I only manage a half-dozen games a year on average, I've maintained the same strength for over 20 years.
Going up to the point that they can beat PROFESSIONAL PLAYERS, consistently ... Those people are 15 to 20 stones stronger than I am. That's somewhat comparable to comparing my 30 years of playing to someone who is literall picking up the stones for the first time in their life.
This is a huge advance, even if it is only optimising multiple moderate-depth playing engines.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
Videos are available.
a,e,i,o,u and sometimes w and y (at be if of up cwm by)
Poker is a game of incomplete knowledge - you don't know what cards are in the other players hands.
Go is a game of complete knowledge. As is chess. And draughts.
The two classes are completely different.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
That's because AI has a real definition: "computers that think like humans."
I dispute that. What a computer that definitely thinks, but not like a human? What if we could develop a computer that thought like a dolphin? Would that not be AI?
systemd is Roko's Basilisk.
Just before /. wets itself with all this comps won a go game - there is still a small difference between 2d player from France and a professional players taking part in professional leagues in Japan, China and Korea. It is indeed a respectful result beating 2p professional. I wonder how that performs with people on the top of the league tho.
We can't (and the existing AI Chess players don't try to) brute force every move in Chess. The compute resource needed would be quite extreme, and if you could do it at all, you'd _solve_ Chess and we'd be able to say confidently "White always wins" or, perhaps as likely "It's a draw" when players know what they're doing. For example we have solved Tic-Tac-Toe and Connect Four, in both those games the first player wins if they play perfectly, regardless of what their opponent does.
AI Chess players begin with an opening "book" which is a collection of sets of early moves players have found to be strong. Human players typically learn to play Chess openings this way too, but from an actual written books as learning that some openings are weak the hard way can be disheartening and also misleading. Once book moves are exhausted, or if the opponent deviates from the book and plays in an unorthodox style, the AI has a function that assesses arbitrary positions and ranks them as more or less desirable. For example, a position where you have lost a pawn is generally worse than one where you haven't, but one where you threaten the opponent's King with a Rook may be worth the loss of the pawn. It can "brute force" lots of possible plays and responses, to see which ones consistently end in good positions and favour those, but by no means enough to foresee the end of the game from the beginning.
Towards the end, what we _have_ brute forced is the endgame tablebases. These tell us how in practice a win can be forced by one side, or a draw reached, from particular positions, usually with only a handful of pieces remaining such as a King and two Bishops versus a King with one Bishop and a Knight. But there is no prospect of the tablebases eventually expanding to cover the whole game. They're already _enormous_ and they cover only an infinitesimal part of the game.
Anyway, while brute forcing Chess is implausible and will probably never happen, brute forcing Go isn't merely implausible, it would require far more compute and storage than could conceivably exist in our universe. It is _literally impossible_. Go is being attacked by AIs in the same way humans do it, by intuition. It's just that we're scared to label what the machines do as "intuition", or the same, to label human intuition as just a neutral network blindly associating certain patterns with success despite not having any communicable "understanding" of what it has done.
I never claimed that Go was popular in the west. Or even known. Unusually I had heard about it before I came to university - that was very unusual. But then I hit the proselytization trail for the next 3 years.
Significantly, I had to do far less explanation amongst the computer science students, because it was already quite well known as a really challenging case for information processing. For the corresponding case of chess, there were already commercial machines available that could take people up to something like a national-team grade player, and the topic was seen as dead from a theoretical point of view having moved to engineering. No wonderfully new insights seemed necessary to beat the rest of the world, just bigger, faster machines and/ or bigger faster ending databases.
So 30 years ago, there was a generation of CS students who were looking for AI challenges, and Go was on the radar. That it has stood as a challenge for 30 years after the fall of chess suggests that it is a genuinely harder problem.
There is also a point that John Tromp hinted at in his "we've counted L19" post of just a couple of days ago : 21x21 go has been an occasional pastime for regular players since ... well at least 1965, since it was mentioned in a text book then. But I think that it has been experimented with back into the Middle Ages. (Sensei's Library has a discussion of 21x21, about how the balance of influence against territory may be different, and the corner-vs-centre balance is changed too, but few people have the experience to really say (a few thousand games played and recorded). But the same rules will work perfectly on a 21x21, making John's technique for analysing 19x19 applicable there, but it would just be a harder problem. So there is an open-ended range of exercising benchmark possibilities there.
Birds are not dinosaur descendants;birds are dinosaurs, for all useful meanings of "birds", "are" and "dinosaurs"
You read...the...paper?!
I don't know how they do things wherever you come from, but this is Slashdot.
Next time, just read the headline and skim the summary, then spout off whatever pops into your head.
Informed commentary, sheesh!
And the training of the neural networks and construction of their training sets certainly did need quite a bit of 'brute force' as well as 'efficiently wielded force in large quantity'.
To be fair, it'd take a fair bit of brute force training for a human to beat Fan Hui too - you aren't exactly going to rock up, read a pamphlet explaining the rules and win 5-0 on your first ever attempt at the game.