Cracking Go less than a decade away

  

Back to forum


Thibault de Vassal    (2007-10-09)
Cracking Go less than a decade away ?

I just read this astonishing article in the last American Go E-Journal :

“I believe that a world-champion-level Go machine can be built within 10 years, based on the same method of intensive analysis—brute force, basically—that Deep Blue employed for chess,” wrote Feng - Hsiung Hsu (r) in “Cracking Go,” a provocative article in the October issue of IEEE Spectrum, published by the Institute of Electrical and Electronics Engineers (IEEE). (...) "with some optimization a machine that can search a trillion positions per second would be enough to play Go at the very highest level."


Looks serious... Any opinion ?


Don Groves    (2007-10-10 00:59:50)
Cracking Go?

As I've pointed out before, unlike Chess, the Go board can be made larger without seriously affecting the game for human players. Making the goban 23 by 23 (Big Go?) would multiply the number of possible games by 3.74e+50 and render brute force algorithms ineffective once again. This would also stimulate Go research as new fuseki and joseki would need to be discovered. Sadly, the day will come when the computer will dominate Go -- and every other human endeavor, except maybe for sex ;-)


Svante Carl von Erichsen    (2007-10-10 13:28:11)
Cracking Go

This statement seems to relate not so much to Go but more on projected calculation power of supercomputers. My impression is that "provocative" is the main intent here.


Thibault de Vassal    (2007-10-10 22:19:16)
Supercomputers

Definitely, I don't believe in brute force calculation. If we see in a near future a Go engine playing at a master level on 21x21 goban, it could play the same level on superior sizes...


Don Groves    (2007-10-11 01:03:35)
Cracking Go...

I don't agree, Thibault. If your statement were true, how do you explain that computers can play at nearly the highest level on a 9x9 board today, yet not on the larger sizes?


Don Groves    (2007-10-11 02:08:40)
Cracking Go

Svante Carl von Erichsen escrit: "This statement seems to relate not so much to Go but more on projected calculation power of supercomputers. My impression is that "provocative" is the main intent here." No, my intent was serious, only the small joke at the end was not ;-) By making the goban lager, Go can avoid the fate of Chess regarding brute force analysis. Even at a trillion moves per second, as mentioned in the article quoted by Thibault, brute force analysis will fail if there are trillions of trillions of trillions of possible moves!


Don Groves    (2007-10-11 02:12:45)
My mistake...

I meant to say "making the goban 'larger' in my previous post, not "making the goban 'lager'! If the goban were lager, then after a few games nobody would care about stupid computers anyway ;-)


Rodolfo d Ettorre    (2007-10-11 02:38:48)
Re.. Lager?

Instead of a lager sometimes I drink a dark ale ...


Don Groves    (2007-10-11 03:52:23)
Re: lager?

Yes, same for me. Or sometimes a glass of Pinot Noir.


Claude Brisson    (2007-10-11 09:03:58)
pinot noir

2003 for instance, I've opened a bottle yesterday evening... would such an event occur (Go cracked), that would be very impressive ; maybe a bit sad, but as Douglas Hofstadter said once : ""It was a watershed event, but it doesn't have to do with computers becoming intelligent."


Claude Brisson    (2007-10-11 09:05:06)
pinot noir

(he was speaking about the defeat of Kasparov by Deep Blue)


Thibault de Vassal    (2007-10-11 12:43:33)
pinot noir, knowledge & 9x9

I agree with that :)

Don, I mean 9x9 should be compared to checkers, it is "chess" at a size where brute force is enough, so a 'particular case' only. But just like Rybka/Hiarcs playing at master level even thinking a few seconds per move by imitating (knowledge + algorithm) an international master's way of thinking more than calculating trillions of positions, why not a Go engine built the same way, much more complex though. Actually Go engines do not calculate much, they try to 'see' already but sure these programs will be improved significantly soon and it could play about the same level (without joseki databases) on different goban sizes. I feel a Go engine could reach a 1 dan / 2 dan level on our small computers, whatever the size of the goban... But it should be incredibly harder to beat stronger players, which is great for Go :)


Don Groves    (2007-10-11 23:04:10)
Pinot Noir

Bonjour, Claude! It's been a long time since we last spoke. I'd love to have a glass of that 2003 vintage ;-) And I agree with Hofstadter also...


Don Groves    (2007-10-11 23:33:36)
knowledge and 9x9, etc...

My 0.02€: Chess has rules which make it easier to program than Go. Just one example, when the King is in check, the search tree of possible moves is pruned enormously. Go has no analog to this. Until the endgame, even when several pieces are in atari there still may be a better move than saving them. As for "playing like a master...," Chess is far more local than is Go. In Go, the whole board must be nearly always in focus, not so in Chess where losing a local battle can spell almost certain defeat. Another factor in making Go so difficult to analyze is the evaluation function which the program uses to decide on the best move. This is far easier to do for Chess than for Go. Maybe I'll start working on a Go program, just to prove myself wrong ;-)


Thibault de Vassal    (2007-10-12 01:55:21)
knowledge and 9x9, etc...

I agree :) .. Definitely chess & Go are very different games. Just like one dimension more in Go, so one doesn't know how to implement such an algorithm & evaluation function well yet, but it started and it should be possible anyway. Let's resume this discussion in about 10 years :)


Don Groves    (2007-10-12 03:05:24)
knowledge and 9x9, etc...

I'll be very happy to resume in ten years! That means I will have made it to age 80 :-)


Philip Roe    (2007-10-18 00:40:41)
Feynman on Go

In a 1985 lecture, Nobel laureate Richard Feynman said that creating an expert program for Go would be a scientific project of very high importance. His reason was that he did not believe that it could done by brute force, and that it would therefore compel researchers to grapple with the problem of just how human beings manage to do what they do with seemingly meager processing power.

Of course brute force has come a long way in 20 years, but my impression is that virtually no progress has been made of the kind that Feynman hoped to see. Does anyone know otherwise?


Don Groves    (2007-10-18 04:40:54)
Feynman on Go

Hi, Philip -- I don't know of any specific details on that sort of progress but Richard Feynman was one of my heroes. I was blessed to get to attend a lecture of his on a field trip to Caltech for high school math and science seniors and have never forgotten the experience.