×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

NYT Story On Go Programs And AI

timothy posted more than 11 years ago | from the mindstones dept.

Games 246

mykej writes: "The NYT (registration required, blah blah) has a story on Go, the hardest game for computers to play. From the article: 'Programmers working on Go see it as more accurate than chess in reflecting the ineffable ways in which the human mind works. The challenge of programming a computer to mimic that process goes to the core of artificial intelligence, which involves the study of learning and decision-making, strategic thinking, knowledge representation, pattern recognition and, perhaps most intriguingly, intuition.' There are a few throwaway lines about Nash from 'A Beautiful Mind,' although they don't mention the game he invented after getting frustrated with the inconsistencies of go."

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

246 comments

First post! (-1, Offtopic)

drsquare (530038) | more than 11 years ago | (#3991364)

Yes!

Re:First post! (-1, Offtopic)

drsquare (530038) | more than 11 years ago | (#3991376)

Erm, it said my score was 0 when I first posted it, now when I reply to it the score is 1, evne though no moderations have been made. Is this is a bug or something?

Re:First post! (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991377)

I'm Second!

Re:First post! (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991386)

NO!!!!!

sloppy seconds (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991375)

Are nice, if the previous used a condom.

cherish my bawls (-1)

neal n bob (531011) | more than 11 years ago | (#3991379)

this makes me sick - some worthless fag got fp, at least he was logged in.

Next time tool, please include important information regarding dead penis birds or katz's latest pedophile adventures, perhaps even a cliched goatse.cx link would be nice.

FOAD.

Re:cherish my bawls (-1)

Anonymous Coward | more than 11 years ago | (#3991394)

links to [goatse.cx] are never cliched

Why don't you... (-1, Troll)

Anonymous Coward | more than 11 years ago | (#3991450)

chew on my penis? You worthless fag.

This post claimed by heterosexuals.
Queers will burn in hell with pedophiles and Pokemon.

Slashdot Effect (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991389)

slashdot effect n.

1. Also spelled "/. effect"; what is said to have happened when taco's anus is virtually unreachable because too many shirt-lifters are hitting it after he posts a boring pro-lunix article on the popular Slashdot news service. The term is quite widely used by /. readers, including variants like "Oh my god, my asshole has been slashdotted again!"

2. In a perhaps inevitable generation, the term is being used to describe any similar effect from being butt-fucked by a large admiring crowd. This would better be described as a flash crowd.

FREE NELSON MANDELA

Versions of Go (1)

JBMcB (73720) | more than 11 years ago | (#3991400)

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 (1)

atdt (88) | more than 11 years ago | (#3991533)

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 (0)

Anonymous Coward | more than 11 years ago | (#3991630)

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 [snafu.de]. 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 [britgo.org] proves.

Re:Versions of Go (2, Informative)

Anonymous Coward | more than 11 years ago | (#3991999)

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.

try the usual test users (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991409)

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. Maybe it does and I am ignorant.

Re:try the usual test users (0)

Anonymous Coward | more than 11 years ago | (#3991415)

there is no maybe about it. you are ignorant

Re:try the usual test users (0, Offtopic)

yatest5 (455123) | more than 11 years ago | (#3991438)

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 [majcher.com]

Go is harder or.....? (2, Insightful)

jeffersonebell (248978) | more than 11 years ago | (#3991421)

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.....? (1)

3.5 stripes (578410) | more than 11 years ago | (#3991446)

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.....? (1)

Hittite Creosote (535397) | more than 11 years ago | (#3991448)

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.....? (3, Informative)

paradesign (561561) | more than 11 years ago | (#3991498)

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.....? (1)

jeffersonebell (248978) | more than 11 years ago | (#3991646)

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.....? (4, Interesting)

freuddot (162409) | more than 11 years ago | (#3991689)

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 [xmp.net] to get an idea of the high-level concepts we need to model to program a Go AI. BTW, this is a cool wiki board about Go. Great place to learn.

So, when we'll be able to model high-level stuff like that and program AI rather than do brute-force hacks like Deep Blue, we'll have a Go AI. In the meantime, we humans rule.

Yes, go is harder (3, Informative)

jo-do-cus (597235) | more than 11 years ago | (#3991727)

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:Go is harder or.....? (2, Informative)

Anonymous Coward | more than 11 years ago | (#3991987)

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

So more or less computers suck at GO (-1, Flamebait)

Anonymous Coward | more than 11 years ago | (#3991432)

or to be more precise, they suck when they are compared to human opponents.

Because they lack intuition.

Wow.

I am underwhelmed.

Not news at all (4, Interesting)

bfwebster (90513) | more than 11 years ago | (#3991434)

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 (5, Interesting)

natpoor (142801) | more than 11 years ago | (#3991435)

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 (1)

Libor Vanek (248963) | more than 11 years ago | (#3991445)

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

The chess player's ego factor (0)

Anonymous Coward | more than 11 years ago | (#3991462)

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

Re:Kasparov and IBM (2)

LoudMusic (199347) | more than 11 years ago | (#3991465)

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 (5, Interesting)

God! Awful (181117) | more than 11 years ago | (#3991591)

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

Chess is not dead yet (2, Informative)

Anonymous God (572329) | more than 11 years ago | (#3991762)

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 !

Chess Will Never Die (2)

Transient0 (175617) | more than 11 years ago | (#3991992)

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:Kasparov and IBM (2, Insightful)

Paradise Pete (33184) | more than 11 years ago | (#3992009)

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.

History on Go (5, Informative)

RobinH (124750) | more than 11 years ago | (#3991447)

Try this site. [well.com]

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

Re:History on Go (0)

Anonymous Coward | more than 11 years ago | (#3991545)

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.

Computers (-1, Troll)

yatest5 (455123) | more than 11 years ago | (#3991454)

suck at GO because they realise it is a worthless pastime pursued by lamers and would rather do other more exciting things, like seeking to different positions on the hard disk in a funky pattern, or something.

Go and movies (2)

paradesign (561561) | more than 11 years ago | (#3991455)

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 (2)

God! Awful (181117) | more than 11 years ago | (#3991482)


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 (0)

Anonymous Coward | more than 11 years ago | (#3991744)

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 (1)

William Tanksley (1752) | more than 11 years ago | (#3992042)

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

-Billy

Re:Go and movies (2)

Queuetue (156269) | more than 11 years ago | (#3991503)

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 (1)

Anonymous Coward | more than 11 years ago | (#3991562)

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 (1)

GigsVT (208848) | more than 11 years ago | (#3991564)

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

Re:Go and movies (1)

Sherloch Hemloch (514137) | more than 11 years ago | (#3991790)

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

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

Re:Go and movies (1)

Squirrel Killer (23450) | more than 11 years ago | (#3991937)

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.

A tidbit about Go (4, Informative)

Blind Linux (593315) | more than 11 years ago | (#3991461)

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 [well.com] 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 (0)

Anonymous Coward | more than 11 years ago | (#3991477)

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 (5, Informative)

flipflapflopflup (311459) | more than 11 years ago | (#3991534)

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.

Great post! (-1)

Y2KBugs Bunny (592032) | more than 11 years ago | (#3991567)

That was an informative post... thanks.
Do you have more input? I'm trying to make a site about Go [myplace.com], but it hasn't taken off yet and I'm just a novice player. I find myself enamored with this game though, it's interesting! Plus being half chinese and all I thought I would embrace some of my asian side lol. Well, feel free to post strategy or just email me at 01-hapa-boi@asianavenue.com with some more tips about Go.

Why was this post moderated overrated twice (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991587)

crackhead mods!

Re:A tidbit about Go (0, Troll)

Megumi_Slashbot (585223) | more than 11 years ago | (#3991648)

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 (-1, Offtopic)

Anonymous Coward | more than 11 years ago | (#3991715)

You aren't a troll, you are a wanker.

Re:A tidbit about Go (0)

Anonymous Coward | more than 11 years ago | (#3991577)

>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 (1)

ives (23634) | more than 11 years ago | (#3991852)

>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 [go.art.pl] can never occur during a Go game.

Speaking of pattern recognition (-1, Offtopic)

ch-chuck (9622) | more than 11 years ago | (#3991480)

If you stare at the Canadian Flag [vexillum.com] long enough, until you get background/foreground reversal, you can see two guys butting foreheads and arguing. Lets see an AI do that.

Hex (3, Interesting)

Salamander (33735) | more than 11 years ago | (#3991481)

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.

Qualify (0)

Anonymous Coward | more than 11 years ago | (#3991483)

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 (0)

Anonymous Coward | more than 11 years ago | (#3991979)

He was baiting you.

You lose.

Parallelism required? (3, Interesting)

mikewas (119762) | more than 11 years ago | (#3991499)

The trend towards Massively Parallel Computers [216.239.39.100], such as the STARAN developed in the 50s/60s at Goodyear Aerospace Corporation by Ken Batcher [kent.edu] 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? (0)

Anonymous Coward | more than 11 years ago | (#3991795)

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? (2)

laertes (4218) | more than 11 years ago | (#3992014)

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.

rithmomachia (2, Interesting)

dustmote (572761) | more than 11 years ago | (#3991508)

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

Go programs (2, Informative)

Janitorial_One (574086) | more than 11 years ago | (#3991512)

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 (0)

Anonymous Coward | more than 11 years ago | (#3991583)

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 (3, Informative)

droid_rage (535157) | more than 11 years ago | (#3991514)

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 [mazeworks.com] and a better one with more info can be found here [earthlink.net]. 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 :-(.

AI book recommendations anyone? (1)

kavau (554682) | more than 11 years ago | (#3991522)

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? (1)

matsukio (27212) | more than 11 years ago | (#3991592)

Artificial Intelligence: a Modern Approach [amazon.com] 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.

Good article about Go and servers (5, Interesting)

Antity (214405) | more than 11 years ago | (#3991531)

There was a really good article about Go on kuro5hin [kuro5hin.org] maybe three weeks ago. In fact, it caused me to start playing again and it still is much fun. :-)

Just try it. There are lots of free Go servers online. I prefer the KGS server [kiseido.com]. All you need is to download the client or just play it online in your browser with others (Java required [sun.com]). There are usually ~100 people online in the English room (yes, chat included).

It's a wonderful game.

It will take a general-purpose AI to play go (5, Insightful)

Bob Hearn (61879) | more than 11 years ago | (#3991553)

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

Hikaru no Go (4, Informative)

Spacelem (189863) | more than 11 years ago | (#3991563)

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 (2, Informative)

Dr. Smoe (18220) | more than 11 years ago | (#3991819)

There's actually an article [bbc.co.uk] 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 (4, Interesting)

MtViewGuy (197597) | more than 11 years ago | (#3991878)

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

Slow news day (0, Troll)

abroadst (541007) | more than 11 years ago | (#3991570)

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 (2, Interesting)

MjDascombe (549226) | more than 11 years ago | (#3991580)

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

GnuGo (2)

Peyna (14792) | more than 11 years ago | (#3991588)

Surprised I haven't seen this yet, but there is a GnuGo [gnu.org] 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 (2)

nagora (177841) | more than 11 years ago | (#3991635)

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 (2)

Peyna (14792) | more than 11 years ago | (#3991703)

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

Octi has similar properties. (1)

mliggett (144093) | more than 11 years ago | (#3991593)

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 [about.com] with the inventor. Octi is online [octi.net]. It also happens to be a lot of fun and pretty easy to teach to people.

Mijn naam is Joost (-1, Troll)

Anonymous Coward | more than 11 years ago | (#3991607)

Hoe gaat get met jouw?

Good Book (1)

imta11 (129979) | more than 11 years ago | (#3991676)

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.

Go vs. Chess in Humans (1)

BeProf (597697) | more than 11 years ago | (#3991752)

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?

easy for computers, hard for programmers (1)

elsegundo (316028) | more than 11 years ago | (#3991778)

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? (1)

f00zbll (526151) | more than 11 years ago | (#3991780)

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?

Automated theorem proving (3, Interesting)

ortholattice (175065) | more than 11 years ago | (#3991831)

Another area that has been elusive to computers is automated proofs of theorems in mathematics. Automated theorem provers such as Otter [anl.gov] and Isabelle [cam.ac.uk] 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 [anl.gov], but these tend to be problems (like this one) involving simple algebraic manipulations. Something like Fermat's Last Theorem, forget it; Wiles' proof has not even been verified by computer, much less automatically proved. The correctness of Wiles proof is at this point based on a consensus of human mathematicians, who may or may not (hopefully not) have overlooked some subtle flaw in its incredibly deep proof.

BTW don't confuse theorem provers with symbolic algebra systems such as Mathematica, Maple, or the GPL'ed Maxima [sourceforge.net]. While indispensable for complicated calculus problems etc. beyond what a human can practically do, AFAIK they cannot prove even a simple abstract result such as the irrationality of the square root of 2.

Idiotic Slashdot problem (0)

Anonymous Coward | more than 11 years ago | (#3991850)

Why do the Editors bother typing:

"The NYT (registration required, blah blah)"

Each and every time? We know the drill by know. Just simply say:

NYT (reg. required)

How hard is that?!?!?!?!

Re:Idiotic Slashdot problem (0)

Anonymous Coward | more than 11 years ago | (#3992016)

Why do the Editors bother typing:
"The NYT (registration required, blah blah)"
Each and every time? We know the drill by know.


It is fair to forwarn readers that the article is encumbered with a cumbersome registration process, yadda, yadda.

Hex program (1)

game (62990) | more than 11 years ago | (#3991891)

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 [earthlink.net] . Yes, it's a windoze program but I am almost finished with a KDE one that's slightly stronger.

Nash and hex (2)

gatekeep (122108) | more than 11 years ago | (#3991931)

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 [mazeworks.com] for documentation of this.

Other information about Go - Links-a-plenty (5, Informative)

gatekeep (122108) | more than 11 years ago | (#3991998)

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 [kuro5hin.org] about go which is what initially piqued my interest and got me started in the game.

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

Some great introductions are available from Kiseido [kiseido.com] The Interactive Way to Go [playgo.to] and Tel's Go Notes [telgo.com]

Uligo [g0ertz.de] 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 [samarkand.com] and Kiseido [kiseido.com]

Also, anyone in the Chicago area should check out the Evanston Go Club [easyaspi.com]

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

I wrote the first commercial Go program (3, Interesting)

MarkWatson (189759) | more than 11 years ago | (#3992021)

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 (2)

anthony_dipierro (543308) | more than 11 years ago | (#3992052)

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 (2)

Mr_Silver (213637) | more than 11 years ago | (#3992062)

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?

Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...