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

History on Go

[RobinH]

Try this site.

It also has instructions on how to teach Go, if you're interested.

A tidbit about Go

[Blind Linux]

lie in the way that the decisions are made and the differences in how they affect the playing field. The average game of Go actually lasts longer than the average chess game and is far older...
For starters, Go in its pure form is played on a 19x19 board as supposed to an 8x8 board. Chess's famous plays, games and styles have all been archived, whereas Go's strategies are largely abstract and can only be learned by repeated play. The game only begins to take structure after 30 to 50 moves. According to this site, Go has approximately 10 to the 750th power of possible board positions. This makes it a very hard game for computers to learn.
On the historical side, Go is a complex game that originated in China close to 4000 years ago and has remained constant to its' original form despite being introduced to many southeast Asian countries since.

Re:A tidbit about Go

[flipflapflopflup]

Whilst I'm personally a Go fan, not a chess fan, I don't think I agree with your arguments.

>Go in its pure form is played on a 19x19 board as supposed to an 8x8 board
So? What has the size of a board got to do with it? In chess you can move pieces around, in GO you cannot.

>Chess's famous plays, games and styles have all been archived, whereas Go's strategies are largely abstract and can only be learned by repeated play
Not really true. There are masses of games available as .sgf files that you can study to your hearts content. THere are many clasic moves to make in certain positions, etc.

>The game only begins to take structure after 30 to 50 moves.
Again, not really. THere are masses of standard opening patterns (fuseki), and also many standardised plays (joseki) that can go on during a game. A whole lot goes on in the first 20 - 30 moves to shape the rest of the game.

Go is a great game, it doesn't need imbalanced comparisons with chess to prove it, you just need to play the game a while to realise that. Maybe you should try.

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.

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

[paradesign]

im sure that is a minute fraction of it but, if you read the article,

A Go-playing computer would take about 30,000 years to look as far ahead as Deep Blue can with chess in three seconds... ... If processing power were all there was to it, the solution would be simply a matter of time, since computers are growing ever faster. But the obstacles go much deeper. Not only do Go programs have trouble evaluating positions quickly, they have trouble evaluating them correctly.

RTFA

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?

OT: Nash's game, Hex

[droid_rage]

Hex was actually first created in 1942 by a Danish mathematician, Piet Hine. It was then discovered independantly later on by Nash in 1947. It is another game which has only been solved on small boards. A good beginner's game (written in java) with 7 hex to a side is available here and a better one with more info can be found here. There's also a games site where you can play this against other people, but I'm at work and can't find it now. Sadly, there is seldom anyone else there :-(.

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.

It will take a general-purpose AI to play go

[Bob Hearn]

I love go (I'm a 2 kyu player), and I'm an AI researcher. But I don't work on go-playing programs. Much as I'd like to, I don't think it would be a productive activity for me.

I think that the minute you start to write a game-playing program, you're trapped by the very natural structures you have to use to make the program even play a legal game. You can't help but start to use minimax search. With go, you add modules for life & death evaluation, influence generation functions, the list goes on and on.

But all these things are just hard-coded approximations of some of the ways people think about go when they play, ripped out of their essential representational context. Real people have rich conceptual networks linking all of these skills together, which multiplies their power enormously. Give a beginning human player a perfect black-box life and death evaluator, like go programs ideally have, and he will never become a strong player. Only by solving life and death problems yourself (to take just one example) can you integrate that kind of knowledge into your total go knowledge. I maintain that this integration is essential.

Will computers ever beat people at go? Sure. But I'll bet the first program to do so will be a general-purpose near-human level AI, that thinks of board positions in terms of physical metaphors. It will have a rich mental landscape.

Bob Hearn

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.

Hikaru no Go

[Spacelem]

I've just started playing Go recently with my flatmates and a friend. It's all because of this amazing anime series "Hikaru no Go" about a boy who meets the spirit of a thousand year old Go master from the Heian period, who teaches and encourages him to start learning the game. From there his own love of the game develops, and he heads towards being a pro.

HNG was sponsored by the Japanese Go society as a way of making Go more popular, and Japanese Go schools are currently being swamped by new players. It's up to episode 38 already, so you'll have some catching up, but the fansubs are great. This link http://www.toriyamaworld.com/hikago/ has some of the original manga if you're interested.

Go and find out more about Go!!!

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

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.

Yes, go is harder

[jo-do-cus]

In fact, there are quite a large number of reasons why Go is harder for computers than chess.

First, there is the board size and the fact that you can play (almost) anywhere on the board, which accounts for the large branching factor (number of possible moves in each position) for the search tree.

Next, there is the fact that games take more moves to finish (about 300 ply, i think, for about 80 for a chess game), which makes the search tree even more staggeringly big. Many many millions of times bigger than that of chess, even when you do a shallow search.

Then there is the difficulty of deciding when the game is over. In go, this happens when both players pass, so this means you have to know when there are no sensible moves anymore. This turns out to be a major problem, whereas in chess the end of a game is more clearly defined.

In fact, it is even very difficult to determine the score for a game when both players have passed. Especially in human expert games, end positions require a great amount of understanding of the game to determine the score.

These, and many other reasons, make Go a very difficult game for a computer. Many (brute force) search/evaluation methods we use in chess and checkers are really not up to the task of playing Go. So we try and figure out some more 'intelligent' methods...

BTW, I have not read the NYT article, but i really doubt they can say anything sensible about 'intuition'. We don't know what intuition is, and even if we would, I think the strenghts of computers lie elsewhere. Let people do what they are good at (intuition, fuzzyness), let computers do what they are good at (count really really fast)...

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.

Why Go Programming is Difficult

[mechner]

A more in-depth article on go programming, from the point of view of a programmer and a player, originally published in The Sciences: http://mechner.com/david/compgo/ Click on "All Systems Go".

Other information about Go - Links-a-plenty

[gatekeep]

For those of you interested in learning more about Go, here's some links to resources I've found helpful since starting to play 3 weeks ago.

k5 had an article about go which is what initially piqued my interest and got me started in the game.

Kiseido Go Server is my favorite place to play online, and very newbie friendly.

Some great introductions are available from Kiseido The Interactive Way to Go and Tel's Go Notes

Uligo and Goproblems.com are great places for learning how to play in common situations.

If you prefer a phyiscal board and stones check out Samarkand and Kiseido

Also, anyone in the Chicago area should check out the Evanston Go Club

A word of caution, if you decide to learn go, expect to lose most of your first 50-100 games. It's a long road, but once you start making progress, you'll grow quickly. I know I sure have. Anyone who's up for a game look for 'jjarmoc' on KGS.

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

Standing on the shoulders of giants

[dsr9996]

Hello Bob,

I respect what you are saying here and understand your reasons for not working on a go-playing program yourself, but I would challenge you with this: Even though you will probably not be the person to write the go ai program that is "near-human level", the person who does eventually write it (X number of years/decades in the future) will most definitely only be able to do it because he learned from people who came before him and attempted the endeavor. In short, it takes Newton to formulate the basic laws for physics and the calculus before Einstein can go further and discover relativity and quantum physics. And as Newton said, the only reason he could accomplish what he did was because he "stood on the shoulders of giants" that had come before him.

I am sure that this is not a new idea to you, but I present it again because I think it is very valid. We are at a very primitive state when it comes to computer ai, as anyone who has done any ai knows, both because of our lack of understanding of how our own intelligence/consciousness works, and because of our lack of good programming tools that allow us to work at a high abstraction of thought (i.e. most of the code we write is very tedious, and even though it is necesssary for our ai programs, it has little to do with actual ai). It is similar to knowing that you need a modern race-car when oil refineries, engines, and smelting have not even been invented yet. It is up to us to create those go-carts, pardon the pun, and start exploring how we might create a smelter, looking forward to the day when the infrastructure will be in place for others to continue the progress.

I know what you mean when you say that when you begin work on an ai problem like go, you are immediately trapped into things you have been taught, common procedures that you know others have used for similar types of problems, etc. However, this does not mean that you cannot be the one to think up the next innovation with respect to ai, taking the next step in creating a "rich mental landscape" that will lead to the integration you believe is essential to true ai.

I am quite positive that you are more knowledgeable about ai than me, since I have only dabbled in it here and there, but I hope you take my encouragement in the spirit I have intended to give it.

Peace to you,
Devin

Britain Go Association and the BBC

[hether]

Slightly off topic, but Britain has a Go Association. I imagine they are pretty pleased to see the game coming back in style. They have lots of info about the game, downloads, etc. available.

The BBC had a story in their CBBC kids section about Go just yesterday or the day before.
http://news.bbc.co.uk/cbbcnews/hi/world/newsid_216 3000/2163584.stm

I'd never heard of the game before I saw this story. I've obvsiously never played it, but they way they described it, it seemed like games could take a very long time when you use the larger board. I could see how this could be very complicated.

US has one too

[pls2917]

American Go Association

Re:Go on the Palm Pilot

[crisco]

GnuGo is available for the Palm. It is a relatively weak AI, even I learned to beat it as a beginner.

AIGO is a shareware Go game for the Palm. It has a stronger AI.

Download a Go program for OS X

[b1t r0t]

The program Goban is a Go client for OS X with GnuGo 3.2 packaged into it. It now also supports two internet Go servers, IGS and NNGS, so you can play against more than just the computer.