Slashdot Mirror
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."
Try this site.
It also has instructions on how to teach Go, if you're interested.
"I have never let my schooling interfere with my education." - Mark Twain
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.
I want 2D games back.
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 :-(.
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!!!
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)...
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".
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.
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.
6 3000/2163584.stm
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.
Most people would die sooner than think; in fact, they do.
American Go Association
AIGO is a shareware Go game for the Palm. It has a stronger AI.
Bleh!