"...and despite the long-standing offer of a $1.6m reward for a winning program, no computer has yet been able to outwit a clever ten-year-old."
What is the main reason behind this? Is it just about CPU cycles due to there being so many possible combinations of moves? Or is there something in the game that makes it inherently hard to program a winning strategy?
Also, as to whether it is harder: I think we will see a complete analysis of go before we see one of chess because of its simpler structure. Reason is that go is mathematically simpler. Because of that, there actually is math on go. For example, http://www.amazon.com/Mathematical-Go-Chilling-Gets-Point/dp... talks about math that proves the value of some endgames that had been discussed for years by pro go players. Yes, that is a fair stretch from making good moves in the beginning of a game, but it's way better than the exhaustive searches we need to prove anything about chess endgames.
>I think we will see a complete analysis of go before we see one of chess because of its simpler structure. Reason is that go is mathematically simpler
This is a false issue I think. Actually, the complexity of chess allows us to reduce the search space a lot more, whereas in go the inherent simplicity in the game itself is built in a way where the entire search space is "potentially" useful, meaning the search space is really big.
This is just my intuition, but I feel like the simplicity makes the game irreducible in itself.
I think you are misunderstanding what "complete analysis" means. As soon as one uses a heuristic like "don't move your king on move 2", one gives up the possibility of a full analysis.
For go (technically: the mathematical variant), we can fully analyze some endgames where there still are 40 or 50 possible moves without an exhaustive tree search. For chess, almost all we have are databases storing the results of tree searches, and little of that helps when looking at slightly different positions (example: let's say you know how to win with knight and bishop against a lone king. If I have an extra pawn, does that affect your first move?)
From December 2004. Is it that hard to put a date in the title? I was psyched to read about some sort of new development in the realm of computerized go, only to figure out half way through I was reading a nearly nine year old article for little to no reason.
For such simple rules, Go is an amazingly complex game. In the years that I've played, I've never gotten to an amateur dan level, and of course have never been close to a professional level. I think the highest I've ever achieved was a 4kyu on www.gokgs.com, though I haven't gone back for a while.
As I've played, I've noticed that my mentality on how to play the game would change. It's much like how for a kids hockey match, everyone will crowd around the puck in one big clump all over the ice, but as they mature, they'll learn passing, strategy, breakout plays, defensive schemes, etc.
My evolution of gameplay went something like this:
1. Play wherever the other person is playing. Conquer the board one section at a time by winning one battle at a time.
2. Spread out to try to cover more of the board at the same time. Depend on coverage to win, with skirmishes here and there as borders clash.
3. Battles on one side of the board influence and impact battles on the other side of the board. Strategy still hinges on staking territory, but individual skirmishes depend on brute force calculations to choose the correct path of stone layout to win each skirmish.
4. The entire board is contested, whether territory has been staked or not. Any location on the board can become a point of attack. Identify critical points that would make the other player's defenses collapse. Rip them apart from the inside out and own the whole board. At this point, it's no longer trench warfare along large borders. It becomes more like sending in special forces into the heart of enemy territory to blow up seemingly secure fortifications. Brute force calculations into the future are no longer always possible due to the complexity of the branch prediction, so rely more on intuition and experience if necessary.
Of course, I am easily humbled whenever I play an amateur hobbyist who is actually truly good (usually from South Korea). They are able to execute my #4 style of play at a level far higher than anything I can imagine. It is mindblowing to see them slice up my defenses like hot butter, while I can do nothing to even remotely damage their defenses, even if they are handicapped at the beginning of the game.
It makes me have a lot of respect for the game when I can have exciting complex games when playing with people at my own level, but still be decimated by others who are still only amateurs themselves. The game can be fun at any level of play, which I think some games aren't able to do.
I cannot even imagine what it would be like to play against actual professionals. I imagine it would be like a Diamond level Starcraft 2 player going up against MC or MVP (ironic that both the top Go players and Starcraft 2 players are from South Korea?).
Sadly, though the game was invented in China, I do not find many Chinese people who are interested in this game, despite the article's claims (I currently live in China today). I wonder why that is. Maybe I'm just not meeting enough people.
I'm currently around 10k AGA, despite having played for seven or so years now. So you were (or are) a stronger player than I. :-)
A lot of what you're describing is "philosophical" Go, which for me is the most interesting aspect of the game. The game is so expansive, with so many different winnable strategies (and, it seems, every strategy being vulnerable to at least one other strategy), and that makes it the most intriguing game I've ever played. That's why, despite being so offensively bad at it, I'm still playing it -- it feels like the game teaches life lessons.
For instance, a dan player during a recent analysis said I was too aggressive (for my rank). I was taken aback, I thought I was playing defensively. But, I was playing defensively everywhere on the board, not leaving enough room for my opponent to live comfortably anywhere, and this was causing life-or-death skirmishes. I got to be a slightly stronger player by giving my opponent a little bit of breathing room.
If anybody on HN is interested in trying it out, drop me an email. I'll get you started on KGS, one of the major international Go networks.
Go is never popular among ordinary people in China. I guess one reason is it takes a lot of time to finish a game. However, most chineses know how to play Xiangqi, the chinese counterpart of Chess.
My favorite part of the article was how they replaced replaced 100 chess players with only 2 Go players. But then the article degraded into yelling about how the Go players were not generic enough to play anything but that one specific game whereas the chess players could also be dropped directly into a bunch of other games.
What is the main reason behind this? Is it just about CPU cycles due to there being so many possible combinations of moves? Or is there something in the game that makes it inherently hard to program a winning strategy?