Slashdot Mirror

← Back to Stories (view on slashdot.org)

Microsoft Research Takes On Go

Posted by Soulskill on from the narrowing-the-possibilities dept.

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."

8 of 175 comments (clear)

  1. Go is not a game by Kim0 · · Score: 5, Interesting

    Go is not a game because it does not have rules that are clearly interpretable, except the new Tromp/Taylor rules.
    One sign of this is that Japanese monks have for about 400 hundred years quarreled about how certain patterns should be interpreted.

    When I started to learn the game, I was told that it was exceedingly simple, but learned that there was a thick book of how to interpret patterns, which obviously is not simple. And after playing it a little, and thinking about it, it became apparent to me that there were end game effects that were simply ignored. The Japanese versus Chinese "rules" give very different endgames, but the practice is to simply ignore that and pretend there is no problem. One just stops when the players agree that the rest of the game would be obvious and boring, without that necessarily being true.

    Robert Jasiek has done extensive analysis of Go, and seems to be the only one actually understanding the game as it is played in practice.
    Here are a short list of the major mistakes that Go rulesets contain.
    Here are lots of short analyses of different scoring methods.
    Here are some game patterns that give different problems in different rulesets.

    When it is not even possible to analyze parts of games then true optimal play regresses to quarreling about it, which is precisely what the Japanese tradition has done for at least some hundred years. Robert Jasiek has made the only consistent interpretation of the Japanese "rules", and it is somewhat insane to read, with 3 levels of recursion. It means that instead of there just being an ordinary game tree, the rules at each node in the game tree are determined by hypothetical game trees at these nodes, and the same goes for the hypothetical game trees. Gaaahrgle!

    Those programming Go players typically do statistics on games played by humans instead of having a scoring function, or they use the Tromp/Taylor rules.

    So Go is riddled with quarrels and pretense. Not a game in practice. More like politics, or Zen.

    Kim0+

    1. Re:Go is not a game by dair · · Score: 5, Insightful

      In practice the problem you see (ambiguities in the endgame) are only really an issue for computer Go. Human players rarely disagree over when a game is "over", as typically the outcome becomes obvious long before each stone is played out to the absolute end.

      Perhaps a good analogy is poetry: it is perfectly possible for a poem to convey meaning, even if it does not conform to the rules of the language or have a literal meaning (and yet, people still understand it).

      The thick book of "how to interpret patterns" is simply a set of standard plays that people have found empirically to work well (in exactly the same way as opening books are used in chess). Like chess, you are free to ignore those patterns if you like, but typically that leaves you in a weaker position than you would be in otherwise.

      These patterns are most commonly used in the opening moves, but local instances of them pop up all the time ("if he moves there, I should move here, then he *has* to move there I'll capture these stones").

      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. Some positions lead to an infinite repeat (A captures B, B captures A, A captures B, etc) but thee plays typically don't determine the final score (if the score was equal, and there was an infinite repeat, then humans would simply call it a draw). Computers can recognise trivial cases of this easily, and do OKish with heuristics for simple cases.

      However the real difficulty in computer Go is understanding just why humans make the moves they do, as outside of the standard sequences a move is often made intuitively as a way to steer the other player even though the consequences of that move may be some way off (or may need to be abandoned, or redirected, or reused in some unplanned way).

      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).

    2. Re:Go is not a game by Anonymous Coward · · Score: 4, Interesting

      Rubbish

      Go is a great game. The chinese and aga rules are precise and assign a score to every position in a simple way with no arguement. The japanese rules are potentially complex but in practise the sort of positions in which difficulties arise rarely if ever occur. The Japanese rules are more conveniant to play with although not as mathematically complete. Still, in 10 years of tournament play I have never seen a position the outcome of which depended on the rules employed.

    3. Re:Go is not a game by Raenex · · Score: 4, 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.

  2. It isn't very strong by Anonymous Coward · · Score: 4, Insightful

    Q: How strong is the AI?
    A: The AI is strong enough that the game could challenge the vast majority of newcomers to the game. It doesn't compare like-for-like with other high performance computing solutions that have been developed for Go - which only Go experts would be able to compete with - but it does give it a more natural feel and makes the game accessible for a broader audience.

    I got excited when I saw the story. Sigh. This won't appeal to people who already play Go. It may appeal to people who have never played. I'm guessing that the game itself won't produce many more Go players. On the other hand, people may read the story on Slashdot and become curious.

    It is relatively easy to beat the existing Go games on a 19x19 board. On the other hand, the existing games are OK on a 9x9 board. On the smaller board, tactics rule. On the full size board, strategy rules. If you make a mistake on the small board, you will be ruthlessly punished.

    What does "beat" mean in Go? In Go, it is possible for an expert and a beginner to have a satisfying game. The weaker player gets to place a certain number of stones on the board before the stronger player makes his first move. The handicap system is pretty reliable and is part of Go culture. If they are properly handicapped, the weaker player will beat the stronger player 50% of the time.

    If we want to seriously talk about how strong a computer game is, we have to talk about handicap. A computer game that needs only a one stone handicap to keep up with an expert would be exciting. With a zero stone handicap, it wouldn't sound very good because it would lose most of the time. Currently, the best programs, running on heavy duty computers, can keep up if they are given a six or seven stone handicap. Wiki

  3. Go is a pretty cool game by Anonymous Coward · · Score: 5, Funny

    Go's a pretty cool game, but maybe some of you have heard of Chess? It involves pieces that can do a lot of interesting moves and some of the existing boards out there can be incredibly ornate.

    Sorry, I wanted to be the equivalent of "That Guy" that shows up to discuss Go every time there's a chess story anywhere on the planet.

  4. Re:Explanation of go AI by cheesecake23 · · 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 at the KGS Go server are now ranked up to 4 dan (like a good amateur player) in games against humans.

    You may want to read this short article in the Guardian 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.

  5. Want to play the game for free? Some pointers by Reemi · · Score: 4, 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/

    Like the problem solving, this is a good site for problems: http://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

    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/ http://www.online-go.com/

    Personally, I'm not into real-time, but KGS is an alternative: http://www.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/

    Have fun.