NYT Story On Go Programs And AI 246
mykej writes: "The NYT (registration required, blah blah) has a story on Go, the hardest game for computers to play. From the article: 'Programmers working on Go see it as more accurate than chess in reflecting the ineffable ways in which the human mind works. The challenge of programming a computer to mimic that process goes to the core of artificial intelligence, which involves the study of learning and decision-making, strategic thinking, knowledge representation, pattern recognition and, perhaps most intriguingly, intuition.' There are a few throwaway lines about Nash from 'A Beautiful Mind,' although they don't mention the game he invented after getting frustrated with the inconsistencies of go."
Not news at all (Score:4, Interesting)
I still play Go occasionally, and though I am a mediocre player at best, I can usually beat any Go-playing programs that I've found.
Kasparov and IBM (Score:5, Interesting)
Hex (Score:3, Interesting)
Actually, Hex was first invented by Piet Hein [ctaz.com], who is perhaps better known for the Soma cube. Nash claims to've invented the game independently, but somehow I just find that hard to believe.
Parallelism required? (Score:3, Interesting)
It would seem that a Massively Parallel Processor would be ideal for this applications, especially a STARAN with it's large Content Addressable Memory. Or do I, as a former STARAN user & developer of similar machines, just see this as a nail since I have the hammer in my posession?
rithmomachia (Score:2, Interesting)
http://www.gamecabinet.com/rules/Rithmomachia.htm
Good article about Go and servers (Score:5, Interesting)
There was a really good article about Go on kuro5hin [kuro5hin.org] maybe three weeks ago. In fact, it caused me to start playing again and it still is much fun. :-)
Just try it. There are lots of free Go servers online. I prefer the KGS server [kiseido.com]. All you need is to download the client or just play it online in your browser with others (Java required [sun.com]). There are usually ~100 people online in the English room (yes, chat included).
It's a wonderful game.
Try your hand at go (Score:2, Interesting)
Re:Kasparov and IBM (Score:5, Interesting)
-a
Re:Go is harder or.....? (Score:4, Interesting)
Disclaimer : IAAPP ( professional programmer ) and IAAGP ( go player )
The trick is not about the branching factor that is quite high in go, and small in chess.
The thing is that in go many local battle are fought on each region of the board. Each of those battle are usually fair. Fighting more for one region will make it yours. However, during that time, the opponent will secure another region.
So far, no problem, use the divide-and-conquer method, solve every region, and then use a sum-of-game technique to play the whole board. However this doesn't work. Every region has many ways to be fought over, and the way you fight in a region will affect all the other region of the board.
Professional players just *know* or *feel* that playing in a certain way will help another region. They have a very informal perception the relationship between the regions. This is something we don't know how to model. Usually people will refer to it as instinct. I tend to believe that it is the years of practice that enable pros to see those pattern.
Also, Go seems to be only a grid with either nothing, a white or a black stone. In fact, much higher-level concept are seen by go players, and as long as we don't model those in a go AI, go AI will suck.
See sensei [xmp.net] to get an idea of the high-level concepts we need to model to program a Go AI. BTW, this is a cool wiki board about Go. Great place to learn.
So, when we'll be able to model high-level stuff like that and program AI rather than do brute-force hacks like Deep Blue, we'll have a Go AI. In the meantime, we humans rule.
Automated theorem proving (Score:3, Interesting)
Only occasionally does a computer prove a theorem previously unsolved by humans, such as Robbins algebras are Boolean [anl.gov], but these tend to be problems (like this one) involving simple algebraic manipulations. Something like Fermat's Last Theorem, forget it; Wiles' proof has not even been verified by computer, much less automatically proved. The correctness of Wiles proof is at this point based on a consensus of human mathematicians, who may or may not (hopefully not) have overlooked some subtle flaw in its incredibly deep proof.
BTW don't confuse theorem provers with symbolic algebra systems such as Mathematica, Maple, or the GPL'ed Maxima [sourceforge.net]. While indispensable for complicated calculus problems etc. beyond what a human can practically do, AFAIK they cannot prove even a simple abstract result such as the irrationality of the square root of 2.
Re:Hikaru no Go (Score:4, Interesting)
It has single-handedly turned Japan into a nation of Go devotees, something that has really surprised a lot of Japanese because many in Japan recently thought Go was only played by elderly Japanese. It has caused something you'd never thought would happen in Japan: children are putting down videogames and Pokémon cards and taking up Go in a big way.
The MSNBC article can be read here: http://www.msnbc.com/news/780055.asp
I wrote the first commercial Go program (Score:3, Interesting)
It really did not play a very good game, but it was fairly well reviewed in the Apple II magazines because at least it could play (and perhaps because of the money I spent on advertising in those magazines!)
Anyway, I agree that Go is a great platform for AI research (probably only real time robot soccer is better in my opinion).
-Mark
Nice to see Go getting some press (Score:2, Interesting)
I had not even heard of it before but the mind power involved in playing drew me to it. Anyone elses brain hurt the first few times they played? Another example of an interest of mine that I didn't have in common with anyone else I knew.
I bought "Many Faces of Go" by Ishi Press, which played pretty well for someone like myself (14kyu) who only played maybe 20 games over a year.
The nice thing about a game like that for beginners is you can make a mistake (bad move) and realize it right away and go back a few moves and try a different move, in order to see what would have been best. Being able to save and go back is a very good learning tool.
I would agree with most posters here in that once you're to a certain level it's best to play against real people anyway. Not only because they're better, but they're also much more unpredictable. Many Faces of Go was somewhat unpredictable, but nothing can beat a human opponent when it comes to that area.
Moreover, being able to watch players a few notches above your playing level is IMO more useful to improving your game than even playing yourself.
Re:It will take a general-purpose AI to play go (Score:4, Interesting)
I'm fairly certain that a master go AI will have a definite intelligence, but it will be a very alien intelligence. It will have grown up in a world where turning by anything other than a right angle makes no sense, where the granularity of the world is noticeable, where the world is bounded on all sides.
Re:It will take a general-purpose AI to play go (Score:2, Interesting)
On the contrary, I'm optimistic that go is in fact interesting, that this one simple problem does somehow have something useful to say about the nature of intelligence.
I'm also optimistic about AI. I think that the average PC has enough computing power to play world-class go, given the right program, and these will be forthcoming within the next couple of decades.
My point was that trying to tackle AI through go is dangerous, because it's so easy to be led astray into inappropriate representations and algorithms. I think the general problem will be easier to solve, because the false paths will not look so inviting.