Slashdot Mirror
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."
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).