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