Microsoft Research Takes On Go

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

Comments

Go is not a game

[Kim0]

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+

Re:Go is not a game

[dair]

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

Go is a pretty cool game

[Anonymous Coward]

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.