Microsoft Research Takes On Go 175
mikejuk writes "Microsoft Research has used F# and AI to implement a consumer-quality game of Go — arguably the most difficult two-person game to implement. They have used an interesting approach to the problem of playing the game, which is a pragmatic cross between tree search with pruning and machine learning to spot moves with a 'good shape.' The whole lot has been packaged into an XNA-based game with a story."
Microsoft spam (Score:1, Informative)
Re:WTF? (Score:3, Informative)
XNA is effectively a game specific library that lets you develop for the xbox and windows. When they say XNA they really mean XNA + .net which combined has a pretty extensive library for game development. While XNA has a lot of helper libraries that let you work with DirectX and managed code, it does not really have anything specific related to AI and since this is an AI project primarily that statement seems to be an advertisement for XNA.
Re:Explanation of go AI (Score:4, Informative)
Monte Carlo
Yes, it's just a variant of Monte Carlo, but don't knock it. Recent programs implementing the algorithm have improved their handicaps by up to 5 stones, which is huge. The top bots [xmp.net] at the KGS Go server [gokgs.com] are now ranked up to 4 dan [gokgs.com] (like a good amateur player) in games against humans.
You may want to read this short article in the Guardian [guardian.co.uk] about these recent improvements in the MoGo go bot. In October 2009 (6 months after this article appeared) a version of MoGo finally beat a top-ranking (9 dan) professional in an even game on a 9x9 board [over-blog.com].
Want to play the game for free? Some pointers (Score:5, Informative)
This article reads like a commercial without any scientific background w.r.t. the algorithms used. They even state it does not perform as well as other available programs.
Still, interested giving the game a try? It is really simple.
Start here to learn the rules: http://playgo.to/iwtg/ [playgo.to]
Like the problem solving, this is a good site for problems: http://goproblems.com/ [goproblems.com] Note, 30kyu problems are the easiest, then 25kyu etc. Hardest are the dan problems. (Believe me, they are really difficult)
Want to play against the computer? GnuGo is your friend> http://www.gnu.org/software/gnugo/gnugo.html [gnu.org]
Playing against real oponents on the web, there are 2 options: Turn-based (the slow progress variant) or real-time. I can recommend for the turn-based variant Dragon Go Server and Online Go Server: http://www.dragongoserver.net/ [dragongoserver.net] http://www.online-go.com/ [online-go.com]
Personally, I'm not into real-time, but KGS is an alternative: http://www.gokgs.com/ [gokgs.com] Note, people might not always be in the mood for chatting here.
Getting hooked, try to find a local club or check for players in your neighbourhood: http://igolocal.net/ [igolocal.net]
Have fun.
Re:Go is not a game (Score:4, Informative)
Not under Japanese rules, or Korean rules, or any ruleset lacking a superko rule. What dair(210) says is also wrong: The corner cases are NOT a problem for computer go, because programs rarely play with the traditional, informal rulesets lacking superko. (When they are forced to, such as in certain tournaments, they perform slightly worse, but not disastrously so).
A more common problem for Go programs is bugs in the superko handling. Nick Wedd runs monthly bot tournaments at KGS, if you take a look at his reports, you'll see hardly a tournament goes by without some program crashing, or timing out due to wanting to play an illegal move (forbidden by superko)
Re:It isn't very strong (Score:4, Informative)
Really. When you say such a thing, it can mean one of two things: You're stronger than European 1 Dan (corresponding to Japanese/AGA 4 Dan, KGS 2-3 Dan) or you haven't been playing computer Go much lately. Many Faces of Go, Zen, Fuego, Aya play on a level it will take years of serious club play to beat (for most of us).
Re:Go is not a game (Score:4, Informative)
You only see these kinds of "problems" with the game when you haven't played long enough to understand the game. There really aren't any problems along the lines you're thinking. Nearly everything you said is incorrect. The Chinese vs Japanese rules do sometimes differ by a few points here and there, but rarely, and if you know which ruleset you're playing under it really shouldn't matter. In fact, if you include stone passing (see AGA Rules) then Chinese and Japanese rules work out the same. Oh, the horror.
As to the Ko rules, ... yes, I've personally fretted over the dreaded triple Ko and I've been frustrated over 4 in the corner, but the triple ko never really comes up and you can play out 4 in the corner if you're obstinate. There are complicated solutions to the tripple ko, such as Ing rules, but nobody cares. It just doesn't matter.
I've also played many new players, presumably like yourself, that can't tell when a game should end. That's normal when you're starting out. What we do with those new players is keep playing until they feel like stopping and sometimes comment on why their plans don't work or why they're losing points. You see, if you keep playing in Japanese rules, you will lose points. Under Chinese rules, you simply keep playing until you get really bored, so you only need to point out that the score isn't changing and isn't likely to change. Problem solved.
The thing that really puzzles me more than anything is why you'd take the time to claim Go isn't a game. Clearly it is, people play it all the time; millions in fact. It's even televised in many Asian countries. Is it some kind of grudge? Are you a chess player that's really jealous? I don't get it. Weird.
Re:Go is not a game (Score:5, Informative)
In practice the problem you see (ambiguities in the endgame) are only really an issue for computer Go.
Wrong. New players frequently have a hard time understanding Japanese rules. This is why people like Kim0 exist. On their own, the Japanese rules logically don't make sense. You have to know how to play to end the game, and you have to know how to end the game before you can learn how to play.
Instead, new players should be referred to Chinese-style rules. The Japanese rules are fine for experienced players.
Perhaps a good analogy is poetry
No, that's a terrible analogy. There are no rules to poetry, and there is no winner and loser. You're just adding confusion.
The rule is that game is over when both players agree that it is over: if there is a disagreement, the game is played on.
That's the problem with Japanese rules. It is not easy to "play on" and determine the score. It is trivial with Chinese-style rules.
Go is a truly fascinating game, and also a very human one (computers will play it well one day, but probably about the same time that they get good at writing poems, playing tricks, or asking why).
Computers already play the game well. They have reached dan status.
Re:Circular reasoning (nothing is obvious) (Score:2, Informative)
What you point out is a problem of Japanese rule, which is inherently flawed. Basically it replies on the agreement of both parties on the live/death of each group, and do not support playing out the actual result, because by playing out the result (like actually killing a group) can change your score and may alter the game winner. However, it's only a problem with the Japanese rules, not with the Chinese rules. In Chinese rules, all stones and territory are counted together, and if there's a dispute, the game can go on without affecting the score. Under Chinese rules, theoretically the ultimate end game is the entire board being filled up withe stones, except the empty spots you need to keep your groups alive. So, from this view, in practice all games did not actually end, but the rest of the game is too obvious to be played out. It's like entering check mate in chess, you don't need to really capture the king to know the game has ended.
It's a long story how the Japanese 'misunderstood' the rules when they imported Go into Japan at around 700AD. Since Japan dominated the Go world in the past 100 years up to the 1990s, and Go is introduced to the west mainly by the japanese, thus their rule set became the most taught and known to westerners. Ideally, the japanese rule set should be abandoned, but then nationalism and pride makes it very hard to do. The lucky thing is these issues are mostly theoretical, and do not affect practice much.