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

Versions of Go

[JBMcB]

There are dozens of variations of Go, in different board configurations and rules. Many have rules simliar to cellular automata, such as Attaxx by Atari. Also the microscope game in the 7th Guest, which is based on Attaxx. I still prefer Othello(TM) or MacGO, with it's very hard to beat NerfMaster level.

Re:Versions of Go

[atdt]

Hi. I don't know what kind of Go you talking about. But there is really only one version of Go that the article was talking about.

The best pro. players of Go are from China, Japan, and Korean.

Re:Versions of Go

[Anonymous Coward]

I have to disagree with you, there are no multiple rules to GO. There are some difference in the scoring rules, but most of these differences cancel out, since it is difficult to show posistion where it affects the outcome of the game. The definitve reference site for these rules is here. Beware, though the theoretic aspect of the site might give a false sensation that the rules are complicated, but they are easily learned in a few minutes as this site proves.

Re:Versions of Go

[Anonymous Coward]

Nonsense - there are NO major variations of the game of GO (baduk, weiqi). There ARE other games that use a similar board (grid) and stones - these are NOT Go. Othello is NOT Go. These other games are NOT Go.

One of them is Go Moku - a children's game mostly - played on the same board, otherwise known as "five in a row."

There are minor rule variations in modern Go, but these do nothing to change the basis and play of the game except to a very, very minor extent.

Perhaps these other games are interesting, but don't confuse them by putting them all in the same category. They're not.

Re:Versions of Go

[c64cryptoboy]

Round Go is an interesting variant. No corners to fight over, and four liberties on every point. Print out the PDF board available here.

Re:Versions of Go

[Anonymous Coward]

I prefer minor Threat's version:
go, yes go

Re:Versions of Go

[Anonymous Coward]

I prefer fugazi.

Re:try the usual test users

[Anonymous Coward]

there is no maybe about it. you are ignorant

Go is harder or.....?

[jeffersonebell]

My question has always been is Go really that much harder for a computer to play than Chess or is Chess just more popular and more energy has been devoted to developing computers to play it?

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

[3.5 stripes]

Did you read the article?

All is explained inside, but here's a summary:

Computers don't have intuition, therefor they cannot play games like go very well.

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

[Hittite Creosote]

If you read the article, it states that from each position in Go, there are a lot more available options - Chess will have about 25-30, Go 240. So it takes a hell of a lot more computational power to look ten moves ahead in Go than it does in Chess.

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

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

[jeffersonebell]

My point is not that Go is more computationally intensive, I know it is. But, you can have a good chess program without having it be brute-force approach. I would think that the same is possible with Go, but the same amount of time researching/programming/studying, etc. has not been spent on it vs. Chess.

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.

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

[Anonymous Coward]

There are many reasons why go is harder to pogram than chess. Among them:
1. The game space is much larger, perhaps 220 half moves with typically a dozen plausible alternatives per move, compared with, say, 100 half moves and typically fewer plausible alternatives. This alone comes to dozens of orders of magnitude.
2. At various times in the game, quite different strategic issues become most important, sometimes accurate reading, sometimes strategic placement, sometimes choice of board area, sometimes choices between "attack" or "reduce area", etc. Programs tend to be bad at this sort of planning.
3. The large branching factor and the interplay between openings in different corners mean that the opening book, while vast, is much less stereotyped than in chess. A corner opening which is good in one situation can be bad in another, the difference being the presence of a stone or two in remote areas of the board.
4. The fact that the stones, once played, pretty much stay put means that it is relatively easy for humans to visualize long sequences. Even a week-end player may need to visualize the result of "ladder" sequences 50 half-moves long, and can do so in a few seconds. Forcing computers to deal with this search horizon all the time -- or figure out when not to -- makes the searches even more of a bottomless void.
In conclusion, though chess is much higher profile in the west, considerable effort here and in Japan and to some extent China has been put into go. There are many reasons why go is indeed harder to program -- much harder.
The strongest programs in the world are currently a bit better than 10 kyu on the Japanese scale. This is a level which is exceeded by more than 80% of the entrants at the US Congress. (Which will take place in Chicago next week, for anyone interested in seeing real go.)
-- David Erbach

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

[Promachus]

Chess is only more popular in the West. Go is extremely popular in Asia--more widely played and followed, I think, than chess is even in the West.

Also, for quite a while a Thai millionaire was offering a large prize to anyone who could write a program that could beat a professional Go player. That millionaire has since died, and the prize offer has expired, but still there is no lack of effort being put toward a solution. As the article pointed out, it's a rather popular topic of doctoral dissertations.

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

[Dexter77]

Difference between Go and Chess is that Chess match can be won with a good memory (like IBM's computer did). Now you can easily calculate that 19x19 Go board can have 3^361 different combination of layouts. Can you imagine a computer that could calculate all those variations!!!

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

[szpak]

Akio Morita, former chairman of Sony, famously remarked,
Chess is a game of war, go is a game of market share.

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

[mangu]

Computers don't have intuition, therefor they cannot play games like go very well.

What has one thing got to do with the other? "Intuition" is a sort of logic you cannot explain, and is, most likely, wrong.

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

[Enzondio]

But, you can have a good chess program without having it be brute-force approach

I don't think that is correct. Deep Blue was essentially just brute force as are, I think, most other chess playing programs. If someone knows otherwise please let me know. I'd be very interested to see other some other techniques as it relates to AI chess.

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

[anonymous_wombat]

To put this more succinctly, in addition to the higher branching factor, coming up with a decent static evaluation function is even more difficult. The tree size could be dealt with eventually, but it is extremely unlikely that there is a decent static evaluation function like for Chess. The DeepBlue static evaluation function only evaluates four different aspects of the game. Try that in Go.

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

[f_ckthisaddy]

It is not brute force, using advanced versions of alpha-beta pruning, with very sophisticated heuristics can lead to excellent results.

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

[Maserati]

I think you mean the US Go Congress. The Unites States Congress would fulfill the 80/20 rule.

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

[Enzondio]

But more or less, it is brute force. Sophisticated brute force, yes, but still brute force. It's about how many different branches it can evaluate in the given time period. And this method doesn't work well for Go.

Something beyond brute force would be recognizing higher level patterns, which is what human beings do when they play Chess or Go (or at least that's what I think happens). That is to say, a human player needs to consciously evaluate far fewer possible moves in order to hone in on the best one. They're not processing thousands and thousands of possible scenarios, at least not consciously.

The real question is are we processing these thousands of possibilites unconsciously (which would pretty much place us in the brute force category) or are we able to recognize higher level patterns without having to process thousands of lower level patterns. I tend to think this is not the case, but do not know enough about how the brain functions to say.

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

[mesullivan]

It's not as simple as just a larger search space. I've heard this before, but the fact remains that good chess playing algorithms are relatively simple and no similarly simple algorithms work well for Go.

The evaluation function is the critical problem. In Chess, you get a half decent evaluation function by looking *only* at material (and obviously checkmate). Assume the player who has more material is ahead. In conjunction with a standard minimax search, this alone probably gets the computer to around 12-300 Elo (good enough to beat me half the time).

Add in a few fairly easily encoded bits about the total number of squares attacked by each player, and the proponderance of center control (again, a very easy to code algorithm produces excellent, if not perfect results: just look at who has more attacks on a square as "control", and see who controls more of the key central squares. Add in a factor to judge what various amounts of center control are worth relative to material). To this general structure, add some pattern matching for a few thousand standard opening positions, and now you've got an algorithm that can play close to master level on an everyday PC.

In go, it's a whole different ballgame, because no one has *any idea* how to code an evaluation function that's remotely close to an accurate picture of who is ahead in the game. You can count territory, but unless you have a high level understanding of tactics, it's often not at all clear just what is really territory. Same for which groups are alive and which are dead, or which are connected and which are cut.

Oddly, the fact that the pieces move in chess makes it *more* tractable, not less. Because pieces move, positional advantages are transient and less valuable than material advantages in general. Which means that apart from the most fundamental ones (center control, file and diagonal control) they can be safely ignored, as long as your tactical reading is just a little bit better than your opponents.

In go, this is not the case. Because stones don't move, a positional advantage can last for most of the important part of the game. it's a standard style to let the opponent take territory and develop influence (and "thickness") with little firm territory in the early part of the game, then use these later to start fights on better terms and eventually close the territory gap, either by making a large territory yourself, or destroying through invasion what looked like territory for the opponent. Even players who use a "territorial" style, taking territory early and giving up influence, usually do so with a keen eye towards limiting the value of that influence, and great concern for their groups' "strength", meaning the ability resist later invasions/fights. They worry about this, their influence gathering opponent may be able to overwhelm them as the game progresses.

Clearly in order to execute these strategies, or keep from falling victim to them, a player needs to have some understanding of the value of various kinds of positional influence. Worse yet, all this valuation *depends* on tactical understanding. The difference between a beatiful powerful thickness and a problem group can be a single key cutting point that you don't have time to protect. People have been trying for 30 years to find algorithms which give accurate enough results to successfully end a search tree, and they haven't been able to do so. The obvious and simple versions (analagous to central square and file/diagonal control in chess) have all been tried and found wanting. Consider Bruce Wilcox's sector line concept, which was a great idea, but not good enough to make his program remotely strong.

The overall point here, is that while more time has probably been spent on chess, the search for a strong go program is not new, and a lot of brilliant people have been working on it for years. Getting a whole lot of masters in a room to encode openings, and Kasparov style into Deep Blue made a difference, because the basic, very simple, underlying brute force algorithm was already quite strong.

You could do all the same things with Go, and you would only improve go programs by a similar amount, maybe 500 elo points (the difference between Deep Blue, and a program that any decent software jockey could write after reading a paper on minimax and alpha/beta). But starting from a position of around 15kyu, that doesn't even get you close to amateur dan level, let alone world class.

The other thing to note is that a lot of this improvement is already in the best programs today. This kind of knowledge encoding is what's responsible for the difference between the best programs of today and the best of 10-15 years ago. The unstated assumption of your question is that there's been a whole lot more work done on computer chess than computer go in the last 30-40 years, and I'm not sure that's actually the case. Go has been a much hotter AI topic for at least the last 15 years. There are a lot of people producing chess programs because, being decent, they are much more marketable, but how many people are actually working on pushing the envelope of how well a computer can play chess? Nearly every writer of computer go software is seriously doing this. None of these folks is just throwing together known algorithms to get a computer player. They are doing research, and trying totally new approaches. Talk to some of them sometime.

BTW, I'd love to see these chess algorithms that are good which don't use minimax (brute force), or at least do so no more deeply or broadly than a typical human player. I don't think there are any programs like that stronger than a fairly weak amateur.

Michael

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

[duder]

It is also important to realize that 10-ply ahead is not significant enough for something like go. The go board is too big in itself to be considered wholely. Supposively go masters subdivide the board and then slowly tie everything together or something along those lines. I suspect 50-ply is not even signicant enough for go.

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

[Libor Vanek]

IIRC Kasparov has got avalaible final version (and it's previous versions) for "testing" few weeks before the match.

Re:Kasparov and IBM

[LoudMusic]

And for all you Trek fans out there - remember the great Moriarty episodes? "Computer, design a foe good enough to challange Data"

http://www.startrek.com/library/tng_episodes/epi so des_tng_detail_68364.asp

We're in deep shit when this kind of AI programming is readily available.

~LoudMusic

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

Re:Kasparov and IBM

[Paradise Pete]

programmed Deep Blue to not just play chess but more specifically play and beat Kasparov

Deep Blue was prepared for the match the same way any other chess player would have prepared for the match - by studying the opponent's games. This is not some trick, it's standard preparation. This is always done in teams, and during the match players always have seconds (as in assistants) to help them analyze and study the games played so far. And if a game is adjourned for the night the seconds stay up analyzing the position and in the morning go over their findings with the player. That's the way matches are played.

Kasparov's complaint was not that the program was prepared in this way, but rather that he did not have sufficient opportunity to prepare for the program.

Re:Kasparov and IBM

[GenetixSW]

That's a most interesting point. It reminds me of a rather amusing Star Trek: TNG episode during which the crew meets a grandmaster at some really complex 3d game. Even Data can't beat the grandmaster, and so he changes his tactic: prolong the game. Once the game lasts more than a few (extremely intense) seconds, the grandmaster loses his grip on the game and gives up. Data's goal had never been to win, but rather to annoy this specific grandmaster. Sounds quite similar to the Kasparov/IBM issue!

I just thought the parallel was fun. =)

Re:Kasparov and IBM

[AGMW]

The character playing against Data was called 'Colrami' (no idea of the spelling) and he beat Data the first time. At the end of the episode, Data played again, but this time played for a draw, and Colrami gave up as he saw he couldn't win.

Everyone laughed and patted Data on the back. Episode ends with everyone happy (as usual). All very 'Little House On The Prairie".

Re:Kasparov and IBM

[dmlane]

I think its a little bit of an overstatement to say that Deep Blue was programmed to beat Kasparov. The difficulty is that Kasparov has the ability to play using very different styles. In his first match with Karpov, he got off to a disaster start using an aggressive style. He then changed styles drastically and drove Karpov to distraction. Kind of like the way Alekhine beat Capablanca.

Re:Kasparov and IBM

[dabrowsa]

Actually the NYT reporter was quite wrong in her description of that match. IIRC, the first two games were split; the next three drawn, but Kasparov had the advantage most of the time in those three games. In the last game Kasparov blundered early in the opening, falling into a known trap, and the game was lost before Deep Blue even had to leave the opening book, i.e. before it had to make any original moves.

I'm pretty sure that in a longer match (championship matches have usually been 24 games, always at least 10) Kasparov would have won. It was certainly humiliating for Kasparov to lose, but in no way can that match be taken as proving Deep Blue's superiority.

Re:try the usual test users

[yatest5]

People generally use the same "bullshit logins" for everything. I tried test1234:test1234 and got right in! Slashdot should have a link to the NYT login generator.

It doesn't work no more, cos they put some funky referrer check in. You need to save it to your computer first. The link is here

History on Go

[RobinH]

Try this site.

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

Re:History on Go

[Anonymous Coward]

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

No, I'm not interested in teaching Go. You see, I can't even play Go, much less teach it.

Re:History on Go

[ergo98]

this pdf also offers an extremely good tutorial of the game.

Re:History on Go

[Anonymous Coward]

They got the name of the game wrong. It should be called the 'surrounding chess'.

Re:History on Go

[Tyler Durden]

First of all, this analogy doesn't work.

Secondly, even if it did work Go is far far older than chess anyways. So it would be more accurate to call chess 'tiny moving go'.

Go and movies

[paradesign]

is it just me or does any movie that has to do with number theory/ mathematics have Go in it somewhere.

the two that come to mind as striking examples are "a beautiful mind" and "Pi"

im sure ther're others. theories? other movies? is it just a trend?

Re:Go and movies

[God! Awful]

is it just me or does any movie that has to do with number theory/ mathematics have Go in it somewhere.

I don't remember any references to Go in "Good Will Hunting" or "Cube".

-a

Re:Go and movies

[Queuetue]

In my experience, most people who deal with number theory/abstract mathematics play go... It may be one of the few technical details that Hollywood gets right...

Re:Go and movies

[Anonymous Coward]

I think it has to do with the director wanting to amaze/astound his audience with the intelligence of his mathematician character(s).

"Hey, I know chess is a game for smart people, but these guys are like, beyond chess, dude. I don't even know what this game IS! Looks cryptic and hard, though."

Re:Go and movies

[GigsVT]

There is a movie named Go, it is about Amway and selling fake rave drugs, basically.

Re:Go and movies

[BiteMyShinyMetalAss]

Life mirrors art. ;) In Pi, Max and Sol aren't the greatest of Go players.

Re:Go and movies

[Anonymous Coward]

I don't remember "Good Will Hunting" having anything to do with number theory/mathematics.

I _do_ remember it sucking quite a bit, though.

Re:Go and movies

[Sherloch Hemloch]

It's not Amway, it's Confederated Products...

"Xaing Chai Check...You are going to die" the black cat

Re:Go and movies

[Squirrel Killer]

I know it's off-topic, but Confederated Products was one of the funniest, least predictable, and believable plot twists I've seen in years.

Re:Go and movies

[William Tanksley]

I enjoyed it, and it definitely was about mathematics -- the main character was a mathematical genius.

-Billy

Re:Go and movies

[Tack Hammer]

So......an old line from an oldie but goodie 80's movie would have been a bit more accurate/belivable as this?

"Greetings Prof. Faulkin. How about a nice game of Go?"

I dunno, I think it just doesn't sound the same

Re:Go and movies

[minh7749]

I see Go in Hong KOng movies. Usually with two old long-time, wise, kung fu master friends. Too old and mature to fight physically, but challenge each other intellectually over tea.

Re:Go and movies

[Anonymous Coward]

This tells me that you:

a) didn't watch the movie, or
b) didn't "get" the movie

The mathematical facility of the character isn't a/the focus of the story. It is, really, quite incidental. You could have replaced "mathematics" with "woodworking" and the main story would still hold.

Re:Go and movies

[William Tanksley]

The mathematical facility of the character isn't a/the focus of the story. It is, really, quite incidental. You could have replaced "mathematics" with "woodworking" and the main story would still hold.

Of course. In which case it would be a story about a woodworking genius instead of a mathematical one. Just as A Beautiful Mind could have been about an insane metalworking genius instead of a mathematical one.

Good movies are about people, not professions or technologies. The fact that you can replace mathematics with something else doesn't suggest that GWH wasn't a mathematical movie; it simply means it was about MORE than math.

As every good movie inevitably will be.

-Billy

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

[Anonymous Coward]

damn. The subject should be 'The differences between Go and Chess' for that to make sense. I changed it stupidly without thinking of how that affected my post.

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.

Re:A tidbit about Go

[Anonymous Coward]

>Go has approximately 10 to the 750th power of possible board positions

It should be fairly easy to calculate an upper bound on the number of Go positions. Each node can be in one of 3 states, so

3^(19*19) = 1.7 * 10^172.

Not very close to 10^750.

Re:A tidbit about Go

[Megumi_Slashbot]

I believe you misunderstand his post. He is merely pointing out differences between the games... it is not an issue of better or worse but rather differences. You cannot contests that there is a big difference between the style of play, the board and the way that the game is viewed/commercialized.
Chess has been archived so that every great master has his style emulated by a computer. Computers learn chess easier because there is more to draw on and less probability to calculate.
I agree about the last comment re: 20-30moves.
But he is not making imbalanced better/worse comparisons but rather highlighting the differences!

Re:A tidbit about Go

[ives]

>Each node can be in one of 3 states

That's true for individual nodes, but in the context of a whole board, just assigning a random state to any position will give you a lot of invalid board configurations.

Trivial example: the groups in this diagram can never occur during a Go game.

Re:A tidbit about Go

[Triv]

Go in its pure form is played on a 19x19 board as supposed to an 8x8 board

Not to be anal, but you're comparing squares to intersections. Chess is played in the squares of a board 8 squares by 8 squares. Go is played on the intersections of a board 19 points by 19 points.

You can play a fast game of go on the intersections of a standard chess board - your typical lunch break 9X9 games. Saves the trouble of carting two boards around provided you don't mind the colored squares. :)

Triv

Re:A tidbit about Go

[Anonymous Coward]

Yes.. and /4 for symmetry of the board.
4.35x10^171

and an empty board is not counted.
4.35x10^171 - 1 :P

--
anonymous, of course.

Re:A tidbit about Go

[Anonymous Coward]

I don't know what the poster's intention was, but what matters is how he came across. In the past years that I've been around Go players, there's always this smug attitude whenever someone mentions chess or playing chess. They always kinda turn up their noses, look down at you, and say, yes, my poor child, chess is a FINE game, but Go is just so much cleaner and classy. Plus, computers can't solve it (yet), and even when they do have enough computational power, humans will still win because of intuition. You see, Go is a game that pits two MINDS against each other, as they feel each other out, etc, blah blah blah. Fooey! Whatever. Those people fall into the same category as someone who says, why, some of my best friends are black. Fucking elitist pigs.

Re:A tidbit about Go

[DWIM]

Here's a nice, informative post that does a nosedive at the end by needlessly descending into a condescending attitude. Totally uncalled for. I suppose his opening line was a clue that we have someone a bit on the defensive here.

Re:A tidbit about Go

[Anonymous Coward]

>So? What has the size of a board got to do with it? In chess you can move pieces around, in GO you cannot.
Simple: the decision tree begins to take up terrabytes even if the AI logic is perfect. There are 19x19 (361) possible spaces that the first move can take. Then 361 * ((361)-2) = 129599 for the second move.

So basically for the Nth move on a M by M board has (M^2)*(((M^2)-2)^N) possibilities. Do you see now that the larger the board, the more memory and clock cycles the AI will exhaust, even if the AI has Dan level knowledge of Go.

> 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.
Yes, but there are thousands of years of games to study. Take also takes huge amounts of CPU time & memory.

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.
> The best game, IMO.

Re:A tidbit about Go

[FireWhenRady]

That assumes that no stones are ever removed from the board. the 3^(19*19)/4 is the lower bound of possible moves (of course many are senseless) but since one can re enter stones on areas where stones have been removed, each point can have have multiple states over the course of the game, increasing the possible number of moves.

Re:A tidbit about Go

[flipflapflopflup]

You are absolutely right. I re-read my post, and realised that it does indeed sound condescending towards the original poster (Blind Linux).

After reading Blind Linux's post, I got the feeling that he had not actually played Go, just read about it, so I thought suggesting he played it would be a good idea. However, things can often come across in the wrong way when typing.

So, sorry Blind Linux.

Re:A tidbit about Go

[flipflapflopflup]

Sorry Blind Linux, if my original post came across badly. I didn't mean to sound rude, I simply meant that if you have a go at Go, you will get a much better feeling for the game than just by reading about it.

Re:A tidbit about Go

[Blind Linux]

Nah, it was a good post... the last bit was a bit harsh-sounding but it's all good.
There isn't much of a go-playing community where I'm from, outside of Chinatown.
Hasn't really caught on in Ottawa. That being said, know a good freeware computer Go program?

Re:A tidbit about Go

[flipflapflopflup]

The best I know of is a cut down version of "The Many Faces of Go" - called igowin, windows only I'm afraid, and you can only play 9x9 games. After that, try GnuGo. You can compile that for anything.

Your best bet is getting a book (I reccomend Teach Yourself Go), and playing 9x9 games until you get the hang of things. Then try one of the online servers: IGS or KGS. Have fun!

The chess player's ego factor

[Anonymous Coward]

Chess players are known to have huge egos. Check out Bobby Fisher for example. So Kasparov is probably just whining.

Re:try the usual test users

[Rhombus]

It doesn't work no more

Hmm...worked for me...

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

[john82]

Nash claims to have won the Nobel Prize too. The nerve of that guy.

Re:Hex

[Salamander]

No comparison. The work for which he was awarded the Nobel prize was verifiably original. Nobody's found a paper containing those exact same ideas published twenty years earlier, at any rate, and yet that's pretty much exactly the case for Hex.

Thanks for playing. Now get back under your bridge.

Re:Hex

[tswinzig]

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.

Me too! It's like two people from two completely different parts of the world claiming to have theorized natural selection at the same time.

Preposterous!

Re:Hex

[tetsuji]

Hrm. Looks like I should be added to the list of those who "invented" Hex as well.

Of course, that's just because I'm a gaming geek and one day I decided to see what would happen if I tried to play Go on one of my D&D hex maps.

Re:Hex

[identity0]

Actually, if you read the book "A beatiful mind", Sylvia Nassar has corroboating stories of Nash's invention in 1949 - after Piet Hein's invention, but before it was marketed by Parker brothers. It was apparently a bit of a fad there at the time.

Re:Hex

[Anonymous Coward]

Or Calculus!

Qualify

[Anonymous Coward]

The NYT (registration required, blah blah)

Why the blah, blah? Why can't you just say (registration required)?

Why do you have to qualify it?

Re:Qualify

[Anonymous Coward]

He was baiting you.

You lose.

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?

Re:Parallelism required?

[Anonymous Coward]

Hi,

I think you are right that this is a case of you having a hammer and wanting the problem to be a nail.

One of the biggest problems why computers suck at go and are pretty good at chess is the branching factor. On average in a given chess position there are about 35 possible moves someone can make. If we want a computer to look ahead 6 ply's(a ply is half a move) the computer has to look at 36^6 position to evaluate them all. There exist all kinds of techniques to elimiate about 90% of those possible positions but if you want to look ahead more moves the amount of time it take increases exponentially.

With current computer power it is very possible to look at head about 12 ply's in chess.

Now we take the same approach in go. Another poster commented that there are on average on a 19x19 board 240 different moves available. So a computer looking 6 ply's ahead would have to evaluate 240^6 positions. This is a substantial amount more than with chess.

Now another problem why parallellism doesn't help much, is that in searching the position tree it is hard to split the up tree into independant pieces so that each processor can search its own part of the tree. This is largely due to the nature of the techniques I mentioned that eliminate about 90% of the search tree.

In short adding an extra processor for searching adds about 20% extra speed in searching the tree due to overhead. Having massive parrallell computers I would guess that the speed increase would only be around 10% per processor. So to search one ply deeper you would have to have a LOT of extra processors.

Re:Parallelism required?

[laertes]

I think that massively parallel processing would be fairly maladapted as a platform for a Go AI. The basic problem in Go for deciding what move to make right now is this: given the enourmous number of possible moves that can be made right now, limit the list to a small number of moves, and pick the best one.

While generating the "short list" can be made parallelized to some extent, the much harder problem is deciding among those. Because you can't apply traditional game theory methods (where you would decide directly what move would lead to a better end game), you have to analyze each of these alternatives by comparing the goal they are trying to achieve, and the likelyhood of doing so. This, at least, is how I feel humans accomplish choosing a move. Deciding the most worthy goals seems to me to be a serialized task, largely inappropriate to MPP.

In my personal experience playing Go, I almost always see the best potential moves right away (at least, the best ones I will ever see). Then, it takes me quite a while to decide among those moves. There are a few situations (Joseki) where I attempt to construct a mental tree of moves, but computers are already okay at those anyway.

Still, there's nothing you can do on a single processor machine that cannot be done on a MPP, and vice versa. Since we can't figure out how to do the "goal juggling" I mentioned at all, it doesn't matter what architecture we use, not even if we use Blue Gene.

Re:Parallelism required?

[mikewas]

You say that "...I almost always see the best potential moves right away..." that sounds like parrallel processes happenned, even though your subsequent analysis is a serial process. the serial processes are more explicit & you're more concious of them.

A later poster mentions that he "is good at tactics" but can't manage the entire board at one time. This also sounds like fertile ground for parrallelism.

Just my opinion, it's not like I'm actually an experienced go player nor have I tried to program the game.

Re:Parallelism required?

[laertes]

The tactics vs. strategy distiction is important and enlightening. Tactical actions are those intended to kill or defend a small number of established groups, while strategic actions are intended to increase the territory controlled (my definition, so feel free to disagree with it).

Winning a tactical battle is something computers are okay at now. MPP is a useful optimization for analyzing a tactical situation. However, winning a particular battle may lead to you losing the game (and frequently it does), so the key problem is chosing the battles to fight. If there are three fights on the board, how do you choose among them? Right now we cannot answer that question, so we don't know if MPP will help or not. I was honestly just conjecturing on the topic.

Re:Parallelism required?

[mesullivan]

> Winning a tactical battle is something computers are okay at now. MPP is a
> useful optimization for analyzing a tactical situation. However, winning a
> particular battle may lead to you losing the game (and frequently it
> does), so the key problem is choosing the battles to fight. If there are
> three fights on the board, how do you choose among them? Right now we
> cannot answer that question, so we don't know if MPP will help or not. I
> was honestly just conjecturing on the topic.

Actually, in Go, computers aren't even very good at tactics. Very basic tactics yes, but at a high, or even middling amateur level, issues that have yet to be successfully quanitified, become as important as raw territory in evaluating tactical success. Capturing 5 stones while letting your opponent get an outside wall is nearly always a tactical loss.

The other problem is that Go computers don't have great life and death engines, so the ultimate tactical issue of "If I let this group get cut off, will it live or die" is not something a computer is able to answer without reading the tree out to its most bitter end, or having a very specific pattern to match.

There's a sense in which computers are *weaker* at tactics in go than in strategy. If I play a very strategic, "peaceful" game with a computer, I will often still win, even giving 9 stones, but the better programs will appear to play at a 9-10kyu level. OTOH, I or players of my level can play all of these programs at 9 stones and win by well over 100 points, if we don't play "peacefully" but start lots of complicated tactical fights.

The real key to the weakness is the intersection of tactics and strategy -- the evaluation of *what* constitutes a tactical "win". A pro player has an excellent but hardly perfect sense of this. As a low amateur dan, I have a decent but very fuzzy sense of this. Weak players have little to no sense about it beyond the most obvious question of who has more completed territory. This is the position the computer is in. This is in contrast to chess where 95%+ of what can be considered tactical success can be well defined mathematically. So when the computer goes searching through the move tree in a chess game, it will recognize any clearly advantageous positions within its search depth. In go, existing evaluation functions are likely to grossly mischaracterize the value of various positions in the same way that rank beginners do.

So maybe you're right that this is essentially a strategic weakness, but oddly it shows up most strongly in what go players would consider "tactical fighting.

Michael

Re:Computers

[flipflapflopflup]

I'd mod you down for slagging off my favorite game, but I can't cos you have the same damned IP address...

rithmomachia

[dustmote]

I was never a big fan of hex. My favorite game right now is Rithmomachia (or rythmomachia), but it's not good for AI stuff, since it's kinda based on simple number theory. Apparently, it competed with chess for a couple of hundred years as the big intellectual board game before essentially falling into obscurity. Rules are at
http://www.gamecabinet.com/rules/Rithmomachia.html

ha

[Anonymous Coward]

ha

Go programs

[Janitorial_One]

For an example of how elementary a regular Go AI is, visit kgs.kiseido.com and click "Play Go Against Your Computer". You'll notice how sometimes the computer passes for no reason, or continutally defaults the game in certain stone patterns.

Re:Go programs

[Anonymous Coward]

The "Play Go against your computer" link takes one to the IgoWin program for 9x9 Go written by David Fotland. IgoWin passes whenever the position on the board is such that makeing a move (adding a stone) will not change the outcome of the game.

The default stone patterns at the start are a handicap that the computer gives the user to make the game more balanced. As you win against IgoWin the handicap is reduced until you are giving IgoWin a handicap instead!

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 :-(.

Re:OT: Nash's game, Hex

[adjusting]

Play it here

Re:OT: Nash's game, Hex

[HBergeron]

Ok, I can whup it on basic, but I cannot win at all on advanced - hell, I can see every computer move to beat me before he makes it, but I can't seem to figure out how to beat it. I also CAN'T STOP TRYING TO BEAT IT. YOU HAVE STOLEN HOURS OF MY LIFE!!! DAMN YOU DRIOD_RAGE!!!! DAMN YOU STRAIGHT TO HELL!!!!

Re:OT: Nash's game, Hex

[Anonymous Coward]

Let's all try to post more responsibly next time.

AI book recommendations anyone?

[kavau]

Computer AI is a topic that always fascinated me, but I never found time to delve into it a little bit deeper. I'm a theoretical scientist myself, so I have a pretty fair math background. Does anyone have some good recommendations on books that give an introduction to AI and particular to game AI?

TIA for any feedback

Kavau

Re:AI book recommendations anyone?

[matsukio]

Artificial Intelligence: a Modern Approach by Russell and Norvig is a very strong text. I find it particularly appealing with my background in mathematics because it is nicely organized in a formal, algorithmic way. It is generally a very "neat" book, which is why the professor for my undergrad course chose it---to offset his "scruffy" ways.

This text won't get you too far into game AI (it is an introductory text) but it will provide a very strong background, and a simultaneously comprehensive and in-depth overview of what the field entails. Plus the exercises are very good, and in abundance. Hope this helps.

Re:AI book recommendations anyone?

[kallisti]

Game AI at this point is still finite state machines and A* pathfinding for the most part. Pre-canned scripts, such as placing move-to points on the map are also used heavily. Every once in a while, someone writes something fancier like Genetic Algorithms or Neural Nets, but those generally don't do as well. Examples include Black & White and Galapagos.

Check out The Game AI page for lots of good sources of information. The series "Game Programming Gems" have some really good articles, they recently spun off an AI-specific "AI Programming Gems" which I haven't seen yet.

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:Good article about Go and servers

[guttentag]

I like this quote from the K5 article:

"The Master said, 'Hard is it to deal with him who will stuff himself with food the whole day without applying his mind to anything good. Are there not gamesters and go players? To be one of these would still be better than doing nothing at all.'"
Confucius (who had better things to do)

Which of the following seems most probable:

• Confucius actually spoke/wrote the English words "Hard is it to deal with him who will stuff himself with food the whole day without applying his mind to anything good."
• Confucius's quote cannot be translated into proper English (i.e. "It is hard to deal with he who will...").
• The error was manufactured to give the quote more authenticity/credibility. People will be more likely to revere a statement they doesn't sound right to them if it is attributed to someone like Confucius ("It doesn't sound right to me, but it must be right because Confucius said it! Golly, he's smart, that Confucius.").
• The person quoting Confucius is a big Star Wars fan and imagines that Yoda really was Confucius in another lifetime.

Re:Good article about Go and servers

[RedWizzard]

The person quoting Confucius is a big Star Wars fan and imagines that Yoda really was Confucius in another lifetime.

Or rather that Confucius was Yoda in another lifetime (a long time ago...).

Re:Good article about Go and servers

[Anonymous Coward]

Funny enough, given your username, chances are the word orfer in the sentence is a result of a german step in the translation - often eastern texts are translated by germans into german, and the english translator is "guided" by the german.

A word-by-word translation from german to english often yeilds funny, but comprehensible english sentences. Interestingly, a word-by-word translation of irish to english yields pretty much exactly "Irish dialect English" beloved of film cops - "I'll put a stop on you", "I do be doing", etc.

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

[freuddot]

I don't agree.

You can't help but start to use minimax search.

Here is the mistake. Before even thinking about putting AI in Go, you have to raise the level of the handled concept. If you still look at the move-level, you're too low.

I have a Go AI in development. However, I purposefully didn't put anything intelligent yet. For now, I'm just raising the concept level. When the program will be able to

detect life and death,
find sure territory,
find all the uncertain connections
find all the possible attacks
count all Ko ...
( much other concept go here )

Then, it should rank everything on the board and make a graph of cause and effect on trying to change those states. i.e. : killing that corner causes to not connect those two groups.

At that point, the decision is much smaller, and searching become possible. Then, only, MiniMaxing this tree wil give results.

I'm sure this would work. Now, I just need the funding to work for 5 years, and you get than amateur 1-dan level AI.

Anyone interested ?

jrainy at sympatico.ca

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

[Kintanon]

The most powerful computer in the world won't be able to run a system like this in a reasonable time frame. And if at some point a computer DOES become as good/better than the masters at 19x19 go, we'll just switch to 21x21 and then you'll need another few orders of magnitude more powerful computers to win. Seriously though, there are already Go AIs that can beat mediocre amatuer players with no handicap, the most popular one is probably GnuGo which I would rate around 4 or 5 kyu. But the processing power required to beat a pro player is massive enough that it will still be several years before it is available. Then, someone with an understanding of the game that rivals a pro will have to program it, because the 'Best' move isn't always the same in the short run and the long run, and when Pro players are reading 200+ moves ahead into the game, you REALLY have to be able to analyze well to stand a chance.
I don't think it's impossible for a computer to beat pro players, but I think it will take 5-10 more years before any computer is powerful enough to do it, and probably 5-10 more years after that before anyone develops an AI that has a complete enough grasp of the game to do so.

Kintanon

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.

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

[Bob Hearn]

From the replies, I guess I came across as pessimistic on computer go.

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.

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

[freuddot]

I tend to agree with most of your point, but the overall conclusion seems wrong.

we'll just switch to 21x21 and then you'll need another few orders of magnitude more powerful computers to win

You assume in your analysis that the complexity of the game grows faster than the square of the board size. I think there is two elements that affect the game complexity :

(a) High-level groups ( alive corner, small center moyo, ko-fight on the left side, etc.. )

(b) Network of relations between those groups.

The number of elements (a) grows with the surface of the board.

The number of links in (b) grows with the square of the number of (a).

This yelds something that seems huge O(N^4) on complex concepts. 25x25 would then be 9 times more complex that 19x19. We are a few order of magnitude short of your values.

I also feel that a human would lose its ability to grasp the whole board at a size not much larger than 25x25.

This game can be won by a computer. It just needs a lot of thinking outside the box by the programmer.

BTW, in the last competition in Edmonton, Gnu Go lost games to the 4 leading programs, and was ranked 7 th :

1 Many Faces
2 Go4++
3 Go Intellect
4 Katsunari
5 Aya
6 Neuro Go
7 GNU Go

Bottomline, we probably agree, just not on the time-frame. ;-)

J.

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

[freuddot]

Ok.

You think that developping a general purpose AI will lead to a good Go AI, and that it (G.P. AI) should happen in the next couple of decades.

I think that developping a good Go AI will help in making a general purpose AI, and that it (Go AI) will happen in the next decade.

Those two statements don't seem contradictory anymore ! The only point to argue is if its better to do some specialized work first (Go) or some general work first (pure AI). This just depends on one's field of interest.

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

[b1t r0t]

There's one other problem with 21x21. That is the point at which the center starts having more point value than the edges. If you make two squares by filling the third line with black stones and the fourth line with white stones, black wins at 19 and white wins at 21.

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

[jafac]

My impression with GnuGo - very slow. On my 450 MHz G4. It's just a matter of CPU horsepower? So if I get a Dual 1GHz, it'll be able to beat me in my lifetime?

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

[Anonymous Coward]

Reading 200 moves ahead... Surely this is not possible?

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

[Kintanon]

I didn't say GnuGo as the best, only the most popular. I think your analysis of the game is faulty if you don't believe that the complexity of the game increases by several orders of magnitude with the increase to 21x21.

With a 19x19 board you have 361 places you can make your first move, of which approximately 20 are acknowledged as the standard 'best' moves, the second move has 360 possible moves, and depending on your strategy and your strength there are around 100 moves that could be considered good playable moves. The ability to see more than 4 or 5 moves deep becomes pretty difficult for a computer, on my 850 mhz Athlon GnuGo seems to see around 11 moves in, I see around 8 moves in. GnuGo can beat me almost every time. A good friend of mine can trash GnuGo every time, easily, and I can beat my friend about half the time. Professional players see around 200 moves deep into a game, planning on a wide scale.

Increasing the board to 21x21 gives us 441 moves for the first one, and increases the number of accepted Good opening moves to approximately 60, abd with 440 possible moves on the second move, around 200 of them are considered good playable moves. AS the game develops, you'll see that the addition of those 2 rows to the game will lead to an incredibly complex new set of possible board positions. I don't doubt that a 1st or 2nd dan Go Program will come about in our lifetime, but I doubt we'll see one in the reasonable future that can beat a 9dan player. And I don't think conventional computers will ever be able to effectively play on a 21x21 board against a 9dan player.

Kintanon

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

[freuddot]

Okay, we should take that offline to email, but I'll stick one more answer here.

However many there are, there is no need to look at individual moves

When I make my first play, I don't ask myself where to play. I ask myself which of the very few opening I know I'll play. Mainly, the 4-4, 4-3, 3-3, and the 5-3 points are my only options.

Then, I don't even consider the answers. I know that the 3-3 gives me a solid corner, with no outside influence. and I know the 4-4 give me plenty of influence, but no corner. When the time comes, I'll lookup in my memory the correct answer.

An AI shoul deal with those high level concepts. Then, when the 4-4 opening is selected, the josekis saved in memory tell what is(are) the best(s) local move(s). The AI then only have to decide whether it still needs to play in this area, or if another area is more important.

Analogy: finite state machines.

Consider a system that must handle three values in the range 0-9. The analog way to do this to minimax searching in go, would be to have 1000 different states, one for each tuples of values.

The right way, analog to my idea of a go AI would be to have three state machines with ten states. This is a standard way to break problem down, bringing the number of states from 1000 to 30. In this case, the two different modules are

1) the high-level fight, namely, in what region of the board the next play should be.
2) the best local play for each region.

Now you need to add those complexities, just like you add the number of states, rather than multiplying them.

The logic will have to be much more complex than a simple minimax search, and much information will have to be given about Go to the system, but if you accept that, there is no proof that it can't be done.

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

[Kintanon]

If you load the system with the accepted opens you will be handicapping it against extremely poor and extremely good players. The openings you listed are the ones which are accepted as the most reasonable opening moves because they give the best control of the immediate surrounding territory. But play can change when someone voluntarily opens by sacrificing a corner to build life elsewhere 160 moves into the game. Unless your AI can connect the importance of a move made NOW with that moves importance 150+ moves down dozens of different possible paths then it will be defeated by master level players.

Kintanon

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

[Anonymous Coward]

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,

I think you're wrong here. Research in the field of holographic memory makes progress several orders of magnitudes faster than AI research. The 1st system to beat humans at Go (and in fact any game with no random factor) will be a system that has the complete game tree hardwired in a holocube. Whenever the human makes a move the system just refocuses some laser or changes some wavelength to bring the appropriate response into focus.

The funny thing is that shortly after the release of this system, the industry producing chess/Go/... games will suffer a recession as buyers turn away and everyone will turn to AI research not because it can produce a system that plays as good as a human but because AI is the right choice for building a system that plays as bad as a human, and thus can put the fun back into playing against a machine.

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

[mesullivan]

I think Bob might be right that it will take a general purpose AI to play Go, but I am nowhere near as sanguine as you or he about when that will come about.

I'll say flatly that there is almost *no* chance of a professional level computer Go program in the next 20 years.

I will be very impressed if computer opponents play at amateur dan level by that time, and I don't really expect it.

The problem is extremely hard and there just isn't a lot of energy being devoted to AI research. Unless that culture changes, and there starts being remarkable progress in the general state of AI research, I don't see the major breakthroughs happening in the near term (i.e. the next 50 years). If you look at the state of general AI, we're not really much further than we were 25 years ago.

There's a lot more polish, and incremental improvement, and a lot of field specific knowledge encoding, but not a great deal of general progress in the mental landscape since the AI winter of the 80s. AI is still very much out of fashion. I'm hoping it will become less so as we start to hit the wall of what faster and faster computers can do to make bad algorithms marginally acceptable, but that remains to be seen.

Of course, there's always the possibility of some crazy genius advancing things by leaps and bounds out of the blue, but I don't think you can count on that sort of thing, and without either that or a major chance in the research landscape, I'd say world class Go is at *least* a hundred year problem.

A note: There are no go programs that are actually 10 kyu measured by the same standards as humans. Computer programs get their rankings based on new opponents. Once people figure out how the computer plays, it's results get a lot worse (and certain people who tend to know how to beat computers can do this even on their first game with a program). The best programs around can only realistically play around 15-18kyu with people who know how to play them, or computers in general.

The biggest weakness of computers is in large whole board fights. They simply don't have the processing power to read them through to a conclusion, thus, the difference in a human's ability to evaluate a board position and the computer's becomes telling.

A few programs have been given fairly high ratings (like 3-5kyu) by Japanese federations based on watching a couple games and seeing that they do a lot of good normal things in their play. What is not seen is that most of those good things are just hard coded pattern matches and openings. If you draw them out of standard joseki and into big fights, they become ridiculously weak.

Michael

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

[Dr. Smoe]

There's actually an article about this on the BBC News web site today, though it doesn't say a whole lot more than the original post. It spends it's time emphasizing how this is causing a revival of Go in Japan.

Dr. Smoe

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:Hikaru no Go

[Kintanon]

WOohoo! This is the reason I started playing Go as well. A friend of mine from Korea showed it to me and I got addicted. I now eagerly await each new fansub. The latest Manga is absolutely suspensful though, driving me crazy waiting for 109!! >:)
The HNG fans from Toriyama's world also have a weekly Go night on Yahoo, but I can't remember which room or what the times are.

Kintanon

Re:Hikaru no Go

[b1t r0t]

children are putting down videogames and Pokémon cards and taking up Go in a big way.

This is a good thing, because the best time to learn to play is as a child. I think this is perhaps because it lets aptitude for the game develop in the language centers of the brain, which are in their primary development years then.

P.S. It was the Hikaru fansubs that got me started too. I had always known I would be interested someday, and then I made a point of learning the rules so I could understand what was going on in the series.

Re:Hikaru no Go

[MtViewGuy]

I think this is going to be good for Japanese culture because to really play Go well, you have to have to be very good at sportsmanship and patience, things Japanese culture revere strongly. It's small wonder why a senior member of the Japan Go Association is a technical advisor for both the manga and anime versions of Hikaru no Go.

It's a good game for people who want to think carefully during play.

Slow news day

[abroadst]

Must not have been any fires or people trapped in a hole or anything today. That would've been more interesting. Anybody who thinks they understand how the human brain works because they can program a calculator on steroids to play chess or whatever is certainly lacking the authentic form of intelligence. For these people the artificial kind is all they can hope to attain.

Try your hand at go

[MjDascombe]

It's still far more fun (for now) to play other people online - try your hand at http://kgs.kiseido.com/

GnuGo

[Peyna]

Surprised I haven't seen this yet, but there is a GnuGo project. I've played with it a little bit, it's okay in terms of AI, but definitely needs a lot of work. I played a palm adaptation of it, and the scoring was done incorrectly, and if you figured out the quirks of the AI you could beat it everytime.

Re:GnuGo

[nagora]

I played a palm adaptation of it, and the scoring was done incorrectly,

There are two major scoring systems for Go, are you sure it wasn't using one you didn't know?

TWW

Re:GnuGo

[Peyna]

Yeah, it was real messed up, plus you had to basically score it on your own. Got linkage to the two?

Re:GnuGo

[Anonymous Coward]

There is absolutely no similarities between the current Gnu Go (which is version 3.2 stable and 3.3.5 development) and the Palm version which was based on version 1.2 I think.

I don't think you can get a go program that is anything better than pathetic for the Palm, but if you have an ordinary PC and you are not above 10 kyu, you should get a decent game from the current versions of Gnu Go.

Note that Gnu Go is engine only and you need a separate program that acts as a GUI. I use cgoban myself, but there are java program that run on almost any platform as well. These programs and many more can be found on the Gnu Go site http://www.gnu.org/software/gnugo.

I am one of the developers of Gnu Go and played it in the Computer Olympiad (http://www.cs.unimaas.nl/Olympiad2002/) where it came 2nd and 3rd on 9x9 and 19x19 respectively. To put it simply: Gnu Go is almost, but not quiet up to the state of the art professional programs. Try it out!

Inge Wallin

Re:GnuGo

[b1t r0t]

I played a palm adaptation of it, and the scoring was done incorrectly

What was it called? Was it PilotGo, by any chance? When I first started learning, that's the first program I tried. Within a week I realized how pathetic it was. I've heard it was based on GnuGo 1.2 or so. GnuGo has significantly improved its play in the 3.x versions.

A slightly less pathetic program is the one included with the Zaurus PDA. Just throw sacrifice stones in its area, and it will waste its time capturing them while you build up your position somewhere else.

Re:GnuGo

[Anonymous Coward]

I was going to post this directly, but the lameness filter won't let me.

It's a ranking of the current computer go programs. My reading of things lately is that GNU Go is doing fairly well recently. In the link for the 19x19 board, I think GNU Go is ranked 4th.

Now, that doesn't mean that it won't be easy for a strong player. It's just to show that as computer games go (he he), GNU Go really is pretty good. Not the best, but pretty damn good, and definitely has the best challenge:availability ratio.

Octi has similar properties.

[mliggett]

There are so many choices at each stage of the game that it's hard to model. The tree branches too often. See this discussion with the inventor. Octi is online. It also happens to be a lot of fun and pretty easy to teach to people.

Re:Octi has similar properties.

[b1t r0t]

Very interesting. It reminds me of the old 3M Bookshelf game Ploy, except you add the movement directions to the pieces as play progresses.

Good Book

[imta11]

Anyone interested in a good book an artifical intelligence in game playing should read blondie24 by Larry Fogel. It takes an evoloutionary computing approach to checkers and is a very accessable and interesting read. It also dispels many fallacies of AI especially the Deep Blue comment made in this article.

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

Re:Yes, go is harder

[Paradise Pete]

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.

If you're only looking ahead a half-dozen ply or so, what possible difference could it make if the game takes 300 moves or even 3000?

Re:Yes, go is harder

[jo-do-cus]

If you're only looking ahead a half-dozen ply or so, what possible difference could it make if the game takes 300 moves or even 3000? Well, i was just talking about the over-all tree size. But the depth of the tree is significant. For example, in chess we see attempts to just solve an end-game by calculating all possible positions and putting them in a database. For go, this is not possible because of both the depth and width of the tree. Still, even searching a half-dozen ply for the whole board is an extremely heavy computing task, much more so than for chess.

Re:Yes, go is harder

[Latent IT]

Well, that's kind of the whole thing. If the game is only going to have 80 moves, looking 12 ahead will mean you're looking at a large, meaningful part of the game. If a game is 300 moves, looking at the next twelve moves ahead is a lot less effective. In fact, it probably scales exponentially, but what the heck. Math ain't my thing.

Short version - it's about percentage. ;p

Re:Yes, go is harder

[djshaffer]

What you say is correct, but incomplete. Most of the reasons you give sound like they could be solved with brute force, once computers get faster.

We can say (probably truthfully) that Go is big enough that computers will never be fast enough, but people used to say this about Chess as well.

You touch on things with the discussion of scoring. Because Go is a game of points, rather than sudden death like Chess, a player MUST estimate the score to evaluate a position.

This can be very difficult. If group A is worth 20 points for Black, and group B is worth 30 then White may make a move that threatens both groups. It seems that white should play to protect group b, however there may be a move to protect group a that also attacks group C. Or, more subtley, sets things up for a future attack on either group C or D.

Even more complex may be an attack on a group of whites that is worth 80 points, is destined to fail, but changes the board configuration such that both A and B may be saved.

None of these are terribly uncommon in a high level game of go. As a 7 kyu (far from really strong) I use all of them at one time or another.

So, computers have a really hard time figuring out what to count.

Re:Yes, go is harder

[Anonymous Coward]

Or maybe each individual move is less important overall.

Go vs. Chess in Humans

[BeProf]

I'm a mediocre Go player (not bad at tactics, but too little experience to effectively manage the whole board). I'm absolutly wretched at chess. I've always been kind of interested in why Go seems to be so much easier for me than Chess but so much harder for computers. I think that what's going on is that Go uses a completely different kind of logic than chess. Any thoughts?

Re:Go vs. Chess in Humans

[Anonymous Coward]

My experience is similar. The strategy of go is much more accessible. It is also much deeper (and more fun). For me, developping an intuitive feel for go was much easier than learning chess, because playing go well mostly depends on "good shape". I love the beautiful shapes :-).

Both games use heavy calculations (reading many moves ahead). But it's a different part of the brain, maybe connected to esthetic values, that is used to evaluate a go position.

Re:Go vs. Chess in Humans

[Zach978]

I'm the complete opposite (but have played many more hours of chess than Go). In Go, I have a harder time of figuring out what my goals are, and how to achieve them. In chess, I can realize my goals by looking at my opponent's positional weakness. I know that if I played Go more I would catch on to similar strategies, but I think the learning curve is much steeper in Go. In the little Go I've played, it's harder for me to distinguish a good move because it's so abstract. Whereas in chess, you often know it's a good move because you can immediately gain material or a positional advantage.

Re:Go vs. Chess in Humans

[Anonymous Coward]

There are two things that interact to make a good program in most of the games out there - chess, checkers, othello, Lines of Action, etc:
1. A very fast evaluation function that produces some kind of score for the value of the position (positive is good, negative is bad). Many chess engines can produce 200.000 evaluations and up per second on an ordinary PC.
2. A search method that enumerates all possible moves, from the starting position, enumerates all moves from these, and so on, and then evaluate the positions at the leafs of this search tree.

Well, that's the basic theory. Of course, if you look at the details there are many many optimizations that you can do so that you won't have to look at all the end nodes. The process itself is called minimax search because you try to maximize your score and the opponent tries to minimize it. The basic optimization is called alphabeta cuts and it works by cutting of a large chunk of the tree once you have found that one move is refuted by an opponent move. You don't have to search for more refutations once you have found one. There are more sophisticated optimizations but they are not interesting here. See http://www.xs4all.nl/~verhelst/chess/programming.h tml for more details.

Anyway, the effectiveness of this search is heavily dependent on the so called branching factor, i.e. how many moves are possible to do at a certain position in the game. For chess, this is around 35, for othello somewhat lower (20ish?) and so on. Go has a branching factor of more than 200 almost all of the game. Naturally you can't search as deep when you have to take into account 200 moves as you can when you are only looking at 35.

The next problem with go is that there is no fast evaluation function. In chess everything interacts with everything else very closely. In go, the board is so big that there can be isolated small fights which don't interfere with each other. However, most of the time they do, and in very intricate ways. It is said about go that you can lose every local fight in a whole game and still win the game, just because you managed to lose the local fights in the right way. The canonical example of this is that you let the opponent invade all the corners and live small and then you get a big territory in the center.

Gnu Go (http://www.gnu.org/software/gnugo), a program that I have been working on, evaluates a position exactly once for each move. There is no global search with moves played and unplayed. Instead there is a big pattern database that suggests interesting things to try, like building territory, attack a weak group, defend your own groups, invade, escape, etc. But all these are local goals, and there is indeed search to see if these goals can be fulfilled. But once we know which local goals can be fulfilled and which can not, the real difficulties begin.

The program has to decide which move to actually make on the basis of the global side effects of the moves that satisfy the local goals. In the end, something called Combinatorial Game Theory (invented by a guy named Berlecamp) can be used, but early in the game you have to use thousands and thousand of hand crafted lines of code just to try the combinations that the programmers anticipated.

So to summarize:
1. There is no fast evaluation function in go
2. Minimax search is difficult because the branching factor is too high.
3. Local fights interact in non-trivial ways to create a mess of threats and possibilities that nobody yet has managed to sort out.

Inge Wallin
Member of the Gnu Go team

Chess is not dead yet

[Anonymous God]

I was at Game 2 of the 6 game Deep Blue-Kasparov series and felt that perhaps Kasparov was making moves to throw off DB. Maybe this cost him the game eventually.

It was a great day for AI but in retrospect a sad day for chess. However it's going to a long time before Chess engines play chess with attitude, emotion and an individual style. If Chess engines just used minmax, alphaBeta pruning, the quality of play would not be very high. Storing opening lines and end game rules makes it a much tougher opponent.

However when these programs are able to store every combination of every possible game and then based the outcomes move up the tree to decide what move to make Then chess will truly be dead.

That will take more than a few EMC boxes! - More like (~35 options per move (starting with 20), ~100 moves per game) = 35^100 = ~2.55e+154 positions. Roughly assuming each position uses 64 bits = 1.85e+143 TB (> a googol Tera bytes!) When you have this 'database' 'populated' you can tell what moves ensure sucess by looking at the end node outcomes.

But for now Go play chess !

easy for computers, hard for programmers

[elsegundo]

what's simple to you is incredibly difficult for a computer

I think what's difficult is writing the actual program. It's easy for the computer once you give it the correct instructions.

One caveat, however, being processor speed.

I wonder what Dr. Richard Wallace would say?

[f00zbll]

Not revive a dead horse, but what would the good doctor say about this. Could his approach do any better at Go than current attempts?

Re:I wonder what Dr. Richard Wallace would say?

[Anonymous Coward]

About this? He would probably say something about how he has a mental disability and how the University of California is out to get him. Of course, he would use several more pages than I just did.

Re:I wonder what Dr. Richard Wallace would say?

[Anonymous Coward]

He probably would tell you that you only need a sufficiently big database of moves to make illusion.

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:Automated theorem proving

[Zurk]

computers cant program themselves either. if they could solve the deep theorems as you prove it they would be able to program themselves pretty easily -- all computer programs are essentially deep theorems.

Hex program

[game]

Hex is indeed a beautiful game. It has very simple rules, yet it is a very deep game. You can try yourself against the computer champion . Yes, it's a windoze program but I am almost finished with a KDE one that's slightly stronger.

Nash and hex

[gatekeep]

Actually, hex was invented in 1942 by Piet Hien. Nash independently invented virtually the same game in 1948, but he was a little late. Kind of like Thomas Edison and what's his name's race with the telephone. Funny how in one case the second inventor is virtually unknown while in the other, it's Nash who gets the credit.

Look here for documentation of this.

Re:Nash and hex

[TheShadow]

Umm... I think most people know that the telephone was invented by Alexander Graham Bell. Hence Ma Bell and all the Baby Bells.

Re:Nash and hex

[gatekeep]

D'oh! I knew that, just had a lapse in thinking.. haha.. Ohh well, my point is still valid even if the facts are obviously messed up.

I guess I'll probably get modded down on that one.. *shrug*

Re:Nash and hex

[stephanruby]

"On the past June 15th, 2002, the US Congress officially recognized that the italian inventor Antonio Meucci is to be credited for the invention of the telephone, and not Alexander G. Bell, as so far claimed."
http://www.popular-science.net/history/meucci_bell .html

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

Chess Will Never Die

[Transient0]

Estimated number of Atoms in the Universe: 1.00E+81

Soo.... If you show me:

1. A way to make a single atom store 10 to the power of 62 terabytes of information

2. A government-stamped letter of permission to turn the known universe into a chess computer

then I'll admit that chess is dead.

Note 1: Deep Blue is no longer the most powerful chess computer, that honour has passed to Deep Fritz which is capable of running on an i86 architecture(unlike th proprietary machine that ran deep blue). Also, Deep Fritz was not designed to beat anyone in particular, yet it has succeeded at defeating both Deep Blue and Kramnik(the current world chess champion).

Note 2: I know that my 10E-81 figure does not include free subatomic particles(photons, free electrons, mesons, etc.), but you get the idea.

Re:Chess Will Never Die

[SubtleNuance]

"I too am a savage; owing no allegiance but to the King of the Cannibals; and ready at any moment to rebel against him"

Can you pls provide some context to your .sig?

Re:Chess Will Never Die

[Reality Master 101]

and Kramnik(the current world chess champion).

Unless you know something I don't, the match between Kramnik and Fritz isn't until this October.

Re:Chess Will Never Die

[Transient0]

my mistake, i had somehow gotten confused, you are right.

Fritz has however beaten both Viswanathan Anand
and Kasparov(albeit in blitz, not slow chess).

an earlier version of Fitz did meet with Kramnik incidentally. Kramnik won 1.5-0.5

Re:Chess Will Never Die

[mxnmatch]

A couple of points:

#1 You can prune all the losing moves. That undoubtedly makes up the vast majority of those positions.

#2 That 1.0E+143 number is the raw number of positions. That information is probably very compressable.

#3 You wouldn't need to store all the positions simultaneously. The computer could just recompute the positions when you get far enough into the movement tree.

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.

Re:Other information about Go - Links-a-plenty

[Anonymous Coward]

While we're providing useful links, here's some more:

Go, An Addictive Game A good all around site for Go news and links.

Jago Jago is a Java go client. It's actually really nice. You can set it up to connect to any server, including the major go servers, as well as local servers (e.g., GNU Go) if you want to play against a computer.

Go Problems The parent mentioned this, but I thought a hyperlink and a bit more of a pitch would be good. Go Problems is a site of archived go problems (Joseki, Fuseki, etc.) that you can play through with your browser using Java. People submit scenarios, and you get to play through them. You can sort by difficulty, type of problem, and have the solution displayed in a number of ways. Youc can also post comments on the problems and rate them and the solutions. It's a very fun site if you're looking to improve your game a bit or just play around without getting into a full game. I've had some issues with the problems and the solutions (unrecognized solutions, multiple solutions, etc.) but like the site a lot.

Oh well. I think I've rambled enough about that site. Enjoy!

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

This isn't so much about AI

[anthony_dipierro]

All are very strong Go players, and it takes a strong Go player to write even a weak Go program.

I think that line captures the problem I have with the article. The purpose of AI is to produce a computer where the programmer doesn't even have to know that the game of Go exists. Yes, an intelligent computer can play Go half-decently, but a computer which can play Go half-decently isn't necessarily showing any intelligence.

So yes, writing a good Go program is challenging, but I wouldn't exactly call it research, unless you're using a method completely different from all the successful ones out there (basically a pruned tree search).

Go on the Palm Pilot

[Mr_Silver]

I fancy learning Go and I've got a Palm Vx. Does anyone know of any Palm Pilot versions of Go that have some sort of AI and configurable board sizes (since I'm told beginners should start with 9x9 and work upwards).

I looked on PalmGear but they only have apps that give you a Go board which can record and replay games. I need someone to play against!

The AI doesn't have to be that great as I'm only a beginner.

Any ideas?

Re:Go on the Palm Pilot

[Anonymous Coward]

try AIGO:
http://www001.upp.so-net.ne.jp/iizuka/

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.

Re:Go on the Palm Pilot

[jumpingfred]

I have played both of these on my palm. They are both incredibly weak in terms of their ability to play GO to the point of being worthless. I beat the handily spotting 9 nine stones and I am not a very good player.

Re:try the usual test users

[ergo98]

As he mentioned, the NYT does referral checks now. By disabling referral forwarding in Opera the site worked perfectly, but when it was enabled the NYT denied it.

How can you be sure?

[yellowstuff]

Remember that Douglas Hofstadher made just that claim about Chess in the 60's. Humans may use a large part of their intelligence to play Go, but that doesn't mean a computer has to.
It seems like there must be some task so hard that it requires general intelligence, but so far I haven't heard of anyone really good at predicting that.

Re:How can you be sure?

[Bob Hearn]

You make a valid point. However:

I'd been under the impression that Hofstadter had made that claim, in Godel, Escher, Bach. But I just looked it up. Here's what he had to say in 1979:

"Perhaps someday, a look-ahead program with enough brute force will indeed overcome the best human players - but that will be a small intellectual gain, compared to the revelation that intelligence depends crucially on the ability to create high-level descriptions of complex arrays, such as chess boards ..."

If he did in fact make a stronger claim earlier, I'd be interested in a reference.

Of course I can't be sure there won't be a good go program that's not a real AI. But it is pretty clear that Moore's law alone will not be enough for a brute-force search go program to beat humans in the next century. The branching factor is just too high, and decent static evaluation is almost impossible.

If the first good go program is not a general AI, it will at least be much more interesting and sophisticated than Deep Blue.

telephone invention

[Transient0]

this is off-topic, but i need to say it.

thomas edison did not invent the telphone.

he had nothing to do with it,

It was Alexander Graham Bell, a Scotsman living in Canada, who invented the telephone.

There WAS a race for the patent, because at least four different researchers were indpendently working on the same project at the same time.

Nice to see Go getting some press

[BlackMesaResearchFac]

I've been a big Go fan for several years now, ever since I started playing it online in the early 90's on The Sierra Network (TSN) aka ImagiNation Network (INN).

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:Nice to see Go getting some press

[pyrrho]

I wrote that (GO on TSN, that is).

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

Download an intro to Go program for Windows

[big_debacle]

Here's a neat little (9x9) free version of The Many Faces of Go. Download Go

It provides a nice taste of go for noobs.

My only thought is that if computers are no good at Go, then I must really stink since I can't even beat the free intro version most of the time.

New York Times Article from 1997

[Jadsky]

This link seems to show pretty conclusively that little has changed in the past five years...

http://www.anusha.com/times-go.htm

It's an article originally from the New York Times, more or less about the same thing.

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.

Re:Britain Go Association and the BBC

[hether]

More importantly I guess is that they already have Go games to download: http://www.britgo.org/gopcres/gopcres1.html

IGS is also good

[nyri]

I prefer IGS server. Client is way worser than with KGS, but it easier to get to play in IGS. Also pros hang out in the IGS.

-- nyri

US has one too

[pls2917]

American Go Association

Re:US has one too

[Sanga]

Avant's Go Association
Indi's Go Association

Inconsistencies?

[strombrg]

What inconsistencies?

The movie Beautiful Mind kind of made it sound like the guy was just miffed because he lost a game, and justified his loss with "the game is flawed".

As someone who's been studying go avidly for about 3 or 4 years, I can say it's quite beautiful.

Ok, maybe ko isn't The most graceful thing ever, and I'm not wild about the bent-four exception in the Japanese rules.

It wasn't even Bell

[crisco]

It was an Italian named Antonio Meucci. He first demonstrated a system in 1860 but couldn't raise the money to file a patent. Supposedly Bell even shared a lab with him.

First referece I found was this. You can google from there.

Re:It wasn't even Bell

[rmohr02]

I know Bell beat someone else to the Patent office by half an hour, perhaps that was the guy he beat.

Massachuetts Go Association

[limekiller4]

If any Slashdotters are interested in Go and reside in the Boston area, there is a 24-hour Go club (only two exist in the US) in Somerville (Davis Sq. stop off the Red Line T, about 5km or so away from Harvard) is the Massachuetts Go Association. While I'm not a member any more (moved to Rhode Island), they're a great club and very much interested in helping new players become familiar with the game. Their book selection in the library is quite impressive as well, covering all the obvious topics (fuseki, joseki) as well as strategy, tactics, theory, etc.

Generally, a newcomer would start off on board with a 9x9 grid and progress from there to a 13x13 and then a 19x19. The great thing about go is that since each piece (stone) is precisely the same as any other stone, it is quite straightforward to handicap a strong player so that an equitable game can be found vs. almost anbody simply by giving the weaker player position on the board before the game begins.

It's a fantastic game, and without being too bombastic (I hope), it can teach the player quite a number of things entirely outside the scope of the game itself.

Re:Computers

[Anonymous Coward]

Do what I do, VNC into your work machine (or at work VNC home).

---
BAS

Definition of "intuition"

[Anonymous Coward]

Actually, "intuition" is not that hard to define: intuition is the ability to leap to useful conclusions with inadequate data.

A bit longer winded: An intuitive person senses patterns and potentials inherent in a situation, and is able to formulate a probable solution to a problem or plan a probably successful course of action, though there is no rigorous line of logical argument that will prove the correctness of the conclusion.

Intuition and and reasoning are not mutually exclusive. Indeed, one is often used to support the other. You may sense a weakness in an argument, then use your reasoning to determine precisely what that weakness is. The value of intuition is that it allowed you to narrow your focus and avoid wasted effort in following dead ends.

Peter (who never registers for anything on principle)

Re:Definition of "intuition"

[jo-do-cus]

Actually, "intuition" is not that hard to define: intuition is the ability to leap to useful conclusions with inadequate data. Yes, and I could define God like "someone with the ability to create a universe", but that doesn't mean I know _what it is_, right?

great go resource

[k2enemy]

if you're interested in starting out with go, try samarkand. sorry for the blatant plug, but i started playing go a few months ago and this site was very helpful. the link goes to their equipment guide, but they also have an excellent online store. its founded by Janice Kim, one of the best go players in america and author of several go books.

Topic Drift Funnies

[crisco]

While searching for the above, I came across this grade school report on Bell.

To be a kid again...

Shibumi

[kird]

Trevanian wrote a book back in the late 70's that got me interested in go about 15 years ago. Actually, that whole book got me interested in a bunch of different things, spelunking, basque, kicking cars, go, and tantric sex.

good stuff!

I used to play hex with mom when I was a kid

[Sunnan]

I just got my first go board a few days before the article on K5. Coincidence. I didn't know it was in "a beautiful mind". I like go better than hex because hex is frustrating when you fall behind. (I felt that) there's often a clear leader. Sure, the leader can "slip up", do a mistake, and the game is good again, but...

I've played a lot of Othello but never mastered it really. Fiddly to flip those pieces. I played gAttaxx some, too, when I was playing with the old Gnome.

Go is bad if you're clumsy at finger work, at least the board I have. Unlike Gomoku or Hex you have to pick up stones occasionally, when they DIE.

Go is a really nice game, I prefer it over Shogi. I've never won a shogi game in my life. Shogi is like trying to learn chess all over again.

Another Great game - Sherlock

[budalite]

If you like logic games or puzzle games, check out "Sherlock" at Kaser Software . (It's all shareware.) It first came out in the early 80's, I think, and I have been playing ever since. (I have purchased every new version.) It's a very simple game that, at the higher levels of difficulty, can be very, very challenging. As each game is randomly generated, every game is unique. Beyond the ideas of level of difficulty, the images used (or created by the player) can add considerably to the ultimate difficulty level. He also makes a bunch of other logic and puzzle shareware games, but this is my favorite. (If you ever heard of KASM, KLINK, & KINT, this is him.) Enjoy.

Have fun.

MadDad32

OT-sig

[Transient0]

It's a quote from Moby Dick. Unfortunately, the character limit to Slashdot sigs left me with the choice of attributing the source or cutting the quote short.

Data does a Microsoft

[Tablizer]

(* And for all you Trek fans out there - remember the great Moriarty episodes? "Computer, design a foe good enough to challange Data" *)

Another interesting one is where a grandmaster of a certain game (don't remember name, had air-finger connectors) came on board and was giddy and pompous about beating the famous Data.

Data eventually realized that he could never beat the grandmaster, at least not by "winning" the game. Instead he learned ways in which to increasingly postpone his loss. Eventually the grandmaster would physically tire, which androids allegedly don't do, and thus win by attrition.

The frustrated grandmaster stormed out of the room in a Kasperov-like fit, and Data was cheered by the crew for rattling his chain.

(In reality, the rules would probably eventually be altered such that the discovered attrition pattern does not work any more. Or, some way to get a score after a set period of time.)

Anyhow, it was one of my favorite episodes.

Re:Data does a Microsoft

[LoudMusic]

Oh yes, one of my favorites as well. How could I have forgotten this episode?

I've used the 'win by attrition' method a number of times in StarCraft, Red Alert, and the like. When you know you're beaten, curl up in your shell and don't die.

~LoudMusic

Star (related game)

[jbennetto]

Star is a game related to Hex but much more intricate. It was created by Craige Schensted (a physicist) and popularized in Games Magazine back in '83.

Star is similar to Go and Hex in the simplicity and consistancy of the rules. The play and tactics are those of Hex (connect stones on a hexagonal board), but there's an additional strategic element involving groups of connected stones that touch the edges at as many points as possible.

A Free Program on 9x9 Board

[Triones]

A free version of "Many Faces of Go".
igowin
The computer player is pretty good on this small board. You'd be surprised.

For those who jockey the complexity of their games

[Anonymous Coward]

For those who want to jockey about the complexity of the games they play, here's a link that gives the computational complexity of a variety of games, along with references.

Of course, if you're really going to get into arguments, you might want to research it a bit more, but it's an interesting site nonetheless.

a fun, difficult game of my own invention

[option8]

while everyone is mentioning go-like and chess-like games of recent invention, i thought i'd throw a plug out there of a game i came up with (though it's similar to several) a couple years ago, called the Aggravator.

of course, i failed to check my spelling at the time, so the game is acually called "aggrivator" which only adds to my aggravation.

anyhoo, it's a fun little game on a 5x5 board. you can play it online (requires shockwave plugin) here: http://www.niftee-tron.com/shock/aggrivator.html.

i've managed to beat it - once. the rules are fairly simple, but the goal is to get all the squares on the board to look the same, which is fiendishly difficult.

the sequel, aggrivator 2.0 is also online, http://www.niftee-tron.com/shock/aggrivator2.html. i've never beaten it, and i don't know anyone who has. it has several levels, each with their own "goal". i tend to think that some of them are impossible to attain, but a math major friend of mine tells me that, using the progression rules in the game, it's possible to attain any board state, but then, he's just a grad student, so what can he know?

anyhoo, maybe some of the distributed might of the slashdot crowd can solve A2.

Re:a fun, difficult game of my own invention

[curril]

I am too lazy to figure out how to contact you, so I posting here. The puzzle/game you created does in fact have unreachable positions.

The rules for the puzzle are associative, in other words you get the same result if you click on cell A then cell B as you would if you click on cell B then cell A. Since each cell rotates through 3 states, then any reachable board position is achieved by clicking on any particular cell at the most 2 times, and the order in which the cells are clicked does not matter.

Since the order of clicking does not matter, there are 3^25 ways you can click on the cells. There are also 3^25 different board positions. If every possible clicking combination resulted in a unique board position, then it would indeed be possible to reach every possible game position. But there are duplicates. It is easy to see this by clicking once on each of two adjacent cells. The end state of the two cells remains the same as the starting state, even though other surrounding cells change. One would suspect that there are ways to have the same affect on the whole grid, and there are. Since there are duplicate states, that means that clicking on cells will result in less that 3^25 unique board positions, which means that there are unreachable positions.

For example, if you click on the appropriate cell the indicated number of times as shown below,
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
0 0 0 0 0
1 0 1 0 1
you will have the same result as if you had done this:
0 2 1 1 2
0 0 0 0 0
2 1 1 2 0
0 0 0 0 0
0 2 1 1 2
I leave it as an exercise for the reader to prove that the A2 puzzle is unsolvable ;-)

Re:a fun, difficult game of my own invention

[option8]

just as i thought. it seems a little countuerintuitive, but i won't argue with you.

i'll have to pass this on to my mathematician friend, who came to the opposite conclusion. of course, he had a convoluted way of coming to his conclusion. i'll see if i can find the email he sent me...

he and i were never able to come up with a "pattern" to beat A1 (and never really bothered with A2 :), despite our best efforts, and we each could only stumble on a solution after some frenzied clicking and much "aggrivation"

as for contacting me, my email is plastered all over the site with the aggrivator on it. or, you could put my slashdot id together with the URL and have a pretty good idea...

Elementary, Dear Data

[brer_rabbit]

IBM programmers... programmed Deep Blue to not just play chess but more specifically play and beat Kasparov

IBM needs to be careful with their wording! Did IBM detect a power surge on the bridge? They're lucky Deep Blue didn't call the "arch".

Re:Elementary, Dear Data

[Anonymous Coward]

I'm sorry, I don't get it.

IGS rocks a**

[rodentia]

Competition is far superior on IGS. The ratings on IGS were recently adjusted by four stones and are still a stone or two stronger than AGA ratings. IGS is good for your game; the others are for kicking the weak around the board.

Computers not solve 19 go in this universe qjkx

[Anonymous Coward]

I suppose it's natural that the usually crowd here thinks it's just a matter of time before "ai" triumphs over humans. One too many sci-fi books read I guess. Humans are good at go through their free will and infinite nonquantized storage of previous quantized input. Computers will have to solve the entire game to be good, and that's only possible in later universes that have more energy.

How to build a Go program

[anonymous_wombat]

I have been considering starting an open-source Go project in a few months (after I get laid off and have some time). Here are some of my thoughts.

Writing a Go program may not be exceptionally difficult. It is just a very large problem. Most previous attempts were done by one or two people, in an attempt to have a commercial success. A large team of people would be required. Probably, this could only be done within an open-source framework.

There might be some things that can be learned from Chess programs, for example how to solve Life and Death problems, but a completely different approach will be needed.

I believe that people have attempted to solve the wrong problem. The problem is not

How can I find the next move on an arbitrary board with n stones?

but,

How can I find the next move from a board with n stones which I have already analyzed?

If you are a Go player, you know that in the middle game, you can usually come up with a decent move within a few seconds, but if you walk over to a game being played by other people in the middle game, it would probably take you several minutes of intense thought to analyze the board, figure out what is alive and what is dead, and who is ahead. Therefore, the program needs to save its state between moves. Figuring out the next move should then be MUCH easier.

Most open-source programs are designed by one or a few people, and then outsiders either just fix bugs, or add additional functionality within the current design. For a Go program to have a decent chance of achieving dan level play, not only does it have to be open-source, but open-design.

Assume that a framework exists, and that modules which perform discrete tasks can be plugged into this framework. A standard interface is defined for each module. There would be modules for fuseki, joseki, life and death, etc. The overall framework which would perform multi-threading, saving of state, communication between modules and the client could be designed and coded by one person. But each of the Go specific modules could be designed and coded by a different person. Modules such as Life and Death are probably straightforward, but what about a module that determines good and bad shape? Many different people would have different ideas of how to do this. The framework should allow multiple competing shape modules to be written. They should be interchangeable, so that any of them can easily be plugged into the framework. In this way, many people can take part in the design of the system. There would be no political fights over how a shape module should be implemented. Different people can write their own, and the one that performs the best within the framework would be used.

Using this set of ideas, I believe that a small subset of the many people who both play Go and are software developers could develop software far better than anything now existing.

I intend to have such a framework implemented by the spring of 2003. I have not posted anything online yet. If you might be interested in participating, feel free to email me at dweiss51@yahoo.com.

Re:How to build a Go program

[Anonymous Coward]

Have a look at GnuGo, it's exactly what you want to
do and it plays pretty good already.

Sorry for posting as anonymous but i'm too lazy to create a new account now ;)

Re:How to build a Go program

[anonymous_wombat]

I have used GnuGo, and examined the source code. Although it does not play a bad game, it is certainly not an easy program to modify. It would not be an easy task for a casual developer to come along and add additional functionality. It is certainly not designed to allow the same functionality to be coded in different ways, or to allow different building blocks to be assembled differently. My main reason for rejecting GnuGo is that, unlike most other problem domains, people don't really know how to build a good Go program. The ability to try different techniques and experiment will be vital. I do not believe that GnuGo provides this, but I do not mean to disparage that project in any way, because they have done extremely high quality work given the limits of coding in C.

Minute fraction? Sure...

[freeBill]

...if you define "minute fraction" as "less than 99 percent, but greater 0 percent."

The truth is we won't know whether it was easier to solve or harder until either:

• somebody solves it and writes a program which beats the best human Go players
• we have spent the same amount of (and quality of) effort trying to play Go that we did to get to Deep Blue and failed to get close to a solution

It has been my observation that this kind of article is written about each hard game as programmers try to get a grip on the strategy. I can remember 25 years ago when similar things were said about chess: too many combinations for brute force; too much of great play was intuitive; chess players cannot describe just what they do.

Ten years ago we heard similar things about bridge. Now, it's Go. As in most journeys, we won't know what it's like until we get there.

As far as Reading The Fine Article, the poster may well have read the article, WHICH DID NOT DEAL WITH HIS POINT to any significant degree. Chess proved to be a very hard problem, which required decades of concentrated effort by some of the best programmers in the world. It was a classic problem which attracted huge amounts of effort. While Bridge and Go afficiados may love to think of their games as more difficult that Chess, neither has had a fraction of the theoretical effort lavished on it that Chess had.

The article was a very superficial treatment. Not only did it fail to deal adequately with the question of the relative amount of effort put into Chess and Go, but many of the facts it presented are either wrong or misleading.

Take the combinatorial questions, for instance: At the beginning of a game of Go, there are 19^2(=319) possible legal moves. If a programmer uses brute force, the combinations go up very quickly (319 x 318 x 317 ...). However, a Go master only considers four of those legal moves for his first stone.

At the beginning of a chess game, there are 20 possible moves, but a good chess player must have a thoroughgoing understanding of at least six of them, with another six being in the realm of possibility. So, over half of the moves must be considered in any brute-force algorithm. Most chess-playing programs do not consider all branches of all trees to the same depth. The ratio of likely-to-be-considered-moves-to-legal-moves is much higher in Chess than Go. Indeed, in Go there are many situations when only one possibility need be considered as the consequences of failure to respond to a particular attack can be so catastrophic.

Another difference between Go and Chess is the degree to which moves open up new possibilities. Most moves in Chess create the possibility of new moves on the following turn which were not legal on the present turn. Indeed, one could argue that one of the key strategies in Chess is opening up as many possible moves as possible. Most moves in Go reduce the number of legal moves (for both players).

Go players are much more likely than Chess players to follow out long sequences of moves without considering alternatives at each step along the way. Chess players find they must consider branches as they think ahead in most such situations unless responses are forced.

I find it interesting that Danny Hillis thinks Go is more intuitive than Chess. But we may be talking about an intuition about intuition. Hillis' intuitions about how computers can be taught intuitive processes are probably worth considering. Other than that, the article offered very little accurate information about programming Go.

Re:Minute fraction? Sure...

[mahk]

>Take the combinatorial questions, for instance: At the beginning of a
>game of Go, there are 19^2(=319) possible legal moves

Except that 19^2 is 361, and that the starting board has 8-way
symmetry, so the number of first moves is closer to 90.

>Most moves in Chess create the possibility of new moves on the
>following turn which were not legal on the present turn.
>[snip]
>Most moves in Go reduce the number of legal moves (for both players).

Well, once you take the symmetry into account, chess and go are very
similar. The first move of go erases one or more axes or symmetry,
causing the number of second moves to jump from 90 to 180 or 360.

It's still true that the branching of Go is more front-loaded than in
chess, but that just makes the tree bigger.

>Indeed, in Go there are many situations when only one possibility need
>be considered as the consequences of failure to respond to a
>particular attack can be so catastrophic.

Except that to really see the "consequences of failure," you have to
look ahead. Most "move here or the giant group dies" moves aren't
ever even ALLOWED to happen by good players, except during ko fights.
And ko fights are strategically complex by nature; with each player
forced to choose between two different battles.

>While Bridge and Go afficiados may love to think of their games as
>more difficult than Chess, neither has had a fraction of the
>theoretical effort lavished on it that Chess had.

I just don't buy this.

How much of the "theoretical effort" we put into chess was really
Chess-specific? I'm sure that in the process of making Deep Blue,
someone came up with some good chess heuristics, but that is a mere
footnote in the greater scheme of everything we've learned about game
AI in the last few decades. And even without good heuristics, Moore's
law would have caught up to chess sooner or later.

From a purely theoretical "what if you had unbounded computing power"
perspective, Go and Chess are equally difficult. They are both just
search trees, giant but finite, with completely public information.
If you can search to infinite depth, you don't need heuristics at all.

From a practical "which one would Moore's law catch up to first?"
perspective, Chess is clearly the simpler game.

Bridge, on the other hand, has hidden information, which makes
it a different (though not necessarily harder) problem.

inconsistencies of go?

[Anonymous Coward]

Go is a beautiful game that his 'beautiful' mind couldn't handle :) There are no inconsistencies about it.

Solution?

[Anonymous Coward]

If the computational problem with go is so huge, then maybe a quantum computer would be the solution.

Go Scoring

[Anonymous Coward]

I understand the split as Traditional/Chinese versus Modern Reformed/Japanese. The split includes a few other rules.

Chineses scoring counts your enclosed territory AND all your stones on the board. Japanese scoring counts your enclosed territory and captured stones.

If you consider the case of a throw-in into your territory, and the stones you use to kill the attack, versus the prisoners you take, you should see that the methods are roughly equivalent.

Specific handling of Ko and repeat configurations (meta-Ko), allowable suicide (I never understood that one...), and the amount of komi (points 'paid' for going first) are among the other differences I recall.

(MetaSlashdot: Knowledge on a topic that makes for good moderation makes for good posts... I'm torn. Knowing the abuse of post&moderate, does anyone have any ideas for a third choice? (Anonymous posting is just a cludge...)

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.

Yes, it has a strategic level

[Anonymous Coward]

As I understand it, Chess programs need not have any concept of strategy. They can use opening dictionaries and brute force searches to work their magic.

Go has a true strategic level and there's no obvious way around it. Three issues contribute to this strategic level:

1. The Go board starts empty (in an even game) and the only restrictions on piece placement are strategic and tactical considerations. Chess starts out fully-populated with many restrictions in the opening moves.

This open-board, open-possibilities start to Go creates a huge branching factor and puts a premium on strategic thinking.

2. An individual Go piece has essentially no value. Value is created by pieces being placed in groups. Groups radiate influence, the amount depending on the group's configuration, its position on the board, and its relationship to most or all of the other groups on the board.

Even defining "group" is hard. In fact, every game of Go will feature at least one battle that rages around whether what one player feels is a "group" is actually a group and if so whether it is a viable group.

3. Go is played on a 19x19 board and the pieces don't move, while Chess is played on an 8x8 board and some pieces can move entirely across the board. This makes Chess a rather small, tactical game, IMHO, while Go has a large-scale, strategic aspect to it.

The larger board means that you essentially start with four separate tactical skirmishes that eventually spill into the sides and then into the center, where they all collide in a rather chaotic way. It's difficult to quantify why a good dictionary opening in one corner of the board ("joseki") doesn't work with another good dictionary opening in another corner.

And this means that brute force and dictionaries don't work so well as in Chess, where there is essentially one tactical skirmish.

Go Masters

[sambo99]

I am a Go player (3kyu) and Computer Programmer.

Some random thoughts

Professional Go players can remember every game they ever played professionaly. I talked to a professional player about that once, and he explained that as a beginner you can see lots of options for every move, but as a master you only see 3-4 options for every move (sure you see a bit more at fuseki). Remembering a game becomes much simpler when there are less options. Keeep in mind there are 19x19 legal positions at the beginning of a Go game.

For quite a while there was a 1 Million dollar award for the first Go program to beat a professional human. Interestingly I can consistently beat the best Go AI out there, and if I played a pro I would probably lose with a 10 stone handicap. (in rough chess analogy that would probably be like playing with no queen, bishop an rook)

As posted earlier I do not think standard minmax search does much good with Go AI. It appears that a whole new set of non traditional techniques are required to solve this problem.

I think that if any AI researchers want to get closer to solving this program they will have to spend lots and lots of time with professional players

Computation Theory versions of Go and Chess

[Scouras]

I'm sort of surprised no one approached it from this perspective yet:

Go and Chess are EXPTIME-complete. (when generalized to an nxn board). http://www.ics.uci.edu/~eppstein/cgt/hard.html

EXPTIME = Union (over k) TIME(2^n^k). This means that, were we to expand the the number of spaces on a chess board from 8x8 to 9x9 to ... to nxn it would become exponentially more complex with every step. All problems in EXPTIME are equally complex, so can be reduced to each other. So, if Deep Blue were generalized to play nxn chess, you could write a program that could (very quickly!) convert each Go move to a Chess move and ask Deep Blue what to do.

There are several basic classes of complexity: POLYNOMIAL TIME, Nondeterministic POLYNOMIAL TIME, POLYNOMIAL SPACE, EXPTIME, etc... The easiest way to understand these is to see what kinds of problems they each contain.

Checking if something is alphabatized is in P - you can just go straight through and do it.
Factoring Primes is NP-Complete -- you have to try every combination to find a factorization
Checkers and Othello are PSPACE-Complete -- every possible move leads to a completely different set of subsequent moves, but pieces can't be removed (othello) or game play is just too simple (checkers).
Chess and Go are EXPTIME-Complete -- spaces can be filled, emptied, and refilled. Something about KO in Go makes it EXPTIME-Complete (and not just PSPACE-Complete).

Hopefully all that made some sense. If not well, it took a whole class (possibly the hardest CS class I've had) before it all made sense to me.

So Go is only harder for the computer because it has a higher branching factor, or basically because it's on a 19x19 board instead of 8x8. The article says the branching factor is 25-35 for chess and around 240 for go.

A couple questions I have is
1) How many possible games are there? I'd guess Go has on the order of 361!. I think the number for chess has been figured out... anyone know?
2)More interestingly, is Go a harder game than Chess for humans? Or are they both so obscenely complex that our pattern-matching/heuristic skills take over and perform the calculations necessary to play well in either game?

Wording...

[psychofox]

There is a slight difference between being "the hardest game for computers to play" and "A hard game for computers to play; one that is harder than chess".

Go is indeed harder

[Anonymous Coward]

Noone can deny that more scientific effort has been put into programming chess than has been put into programming go. Still I am sure go is harder.

The reasoning that Go has a higher branching factor than chess has been mentioned a couple of times here. I don't think this is so relevant.

Much more important is the fact that it is impossible to write a quick evaluation function that gets it approximately right. In chess, the programs do a couple of moves of quiescence search (i.e. only trying captures) and then evaluate the position statically with a couple of heuristics. In Go, if you wanted to write a minimax search, you would have to make a complicated "life-and-death"-search (analyzing local battles) just to evaluate each end node. And existing programs cannot even do this life-and-death search reasonably.

To answer your question differently: If the same effort that has been put into GNU Go, had been put into a chess program, you might have a programs that is a lot worse than the top programs, but it could still beat a good amateur. In Go, a beginner can beat GNU Go after a few months.
To beat a similar beginner at chess, it might be enough to set up an alpha-beta search with 2 or 3 well-known pruning algorithms, and spend a week or so on tuning the evaluation function.

Finally, be warned that I am definitely not objective, as I have spent some time on improving GNU Go :-)