NYT Story On Go Programs And AI

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."

Comments

Not news at all

[bfwebster]

I took a grad-level AI class in college nearly 30 years ago; our final exam was a round-robin tournament among Go-playing programs that we had to write. (More precisely, we each wrote two routines--one to evaluate the board, one to generated a list of moves--and a minimax framework called our routines.) It was a great introduction as to why AI is hard.

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. ..bruce..

Kasparov and IBM

[natpoor]

The NYTimes is not exactly correct about the Kasparov/Deep Blue match. The IBM programmers studied Kasparov's playing style intensely, and programmed Deep Blue to not just play chess but more specifically play and beat Kasparov, which is a slightly different thing from "playing chess." (Granted the machine could still beat almost anyone, but maybe not other masters with a different playing style.) Kasparov, on the other hand, was not allowed to study how Deep Blue might play at all. I also recall that Kasparov became a bit unhinged early on. So yes, Deep Blue did beat Kasparov, but the problem for it was not just "play chess" it was "beat Kasparov."

Re:Kasparov and IBM

[God! Awful]

At one point, I was trying to improve my chess game by studying the game archive that comes with ChessMaster. After only a few weeks of practice, I discovered that I could predict each move (in the midgame) with uncanny accuracy (80%). However, my chess game didn't actually improve. All I had done was train my brain to be a fuzzy logic analyzer for predicting Kasparov moves against high quality opponents. The basic strategy fails miserably against amateur players (who tend to be less subtle in their attack). One of the ways Kasparov came back to beat Deep Blue in their original match was to suddenly switch strategies to something the machine was not expecting.

-a

Hex

[Salamander]

Actually, Hex was first invented by Piet Hein, 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?

[mikewas]

The trend towards Massively Parallel Computers, such as the STARAN developed in the 50s/60s at Goodyear Aerospace Corporation by Ken Batcher were discarded for the most part. Pipelined machines were easier to design, cheaper to build, and easier to program (i.e. could use existing languages).

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?

Good article about Go and servers

[Antity]

There was a really good article about Go on kuro5hin 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. All you need is to download the client or just play it online in your browser with others (Java required). There are usually ~100 people online in the English room (yes, chat included).

It's a wonderful game.

Re:Go is harder or.....?

[freuddot]

Go is definitively harder.

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 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

[ortholattice]

Another area that has been elusive to computers is automated proofs of theorems in mathematics. Automated theorem provers such as Otter and Isabelle typically cannot prove "deep" theorems that human mathematicians prove on a routine basis.

Only occasionally does a computer prove a theorem previously unsolved by humans, such as Robbins algebras are Boolean, 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. 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

[MtViewGuy]

In fact, there's an article from MSNBC.com in the Newsweek section specifically about the success of Hikaru no Go.

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

[MarkWatson]

I am fairly sure that I wrote the first commercial Go playing program, Honninbo Warrior for the Apple II.

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

Re:It will take a general-purpose AI to play go

[iabervon]

I think that a good AI go player will need to have a rich mental landscape, but that it doesn't need to think at all like humans think. Humans have a certain set of metaphors which are very natural simply because we've evolved the hardware optimized for them, so that we can move through the world reflexively. A computer go player definitely needs metaphors, but they do not need to be physical metaphors; humans play go with physical metaphors because that's what we have, but there may be better metaphors for go which we can't understand or use as well.

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.