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

Hikaru no Go

[Anonymous Coward]

Hikaru no Go will slap this game around silly.... on a serious note, from what I've read previously on the Go AI attempts, if this is at all a good AI, then kudos to MS research.

Re:Hikaru no Go

[Anonymous Coward]

Watashi ha Hikaru. Why I no go? I must know. Naze da! Naze da! Sabedu ka!

Please, Hikaru is good. Hikaru go, OK?

Re:Hikaru no Go

[BitterOak]

For those of us who do not speak Japanese, anyone care to explain what the above two comments actually mean?

Re:Hikaru no Go

[ChromeAeonium]

At one point, there was even a Linux distro based on that: Hikarunix.

Re:Hikaru no Go

[Anonymous Coward]

I don't speak Japanese, but I can sort of explain.

"Hikaru no Go" is the name of an anime - it means "Hikaru's Go" or "The Go of Hikaru"

The comment above yours is somebody interpreting "no" (possessive participle in Japanese) as "no" (negative in English) - so "Hikaru doesn't go" or something.

I know just enough to know that "Watashi ha Hikaru" means "I'm Hikaru" (usually I see "watashi wa" - don't know the difference, but maybe masculine/feminine articles), so he/she wants to know why he doesn't go. Don't understand the rest, but it's probably continuing the joke.

Microsoft spam

[Anonymous Coward]

Needs an Xbox 360 to play. Microsoft spam.

Confusing title

[PhrostyMcByte]

When I saw "Microsoft takes on Go", I thought of Google Go. It only adds to the confusion that both F# and Go attempt to solve some concurrency issues, though I thought it odd to compete with an imperative language using a functional one. I had to do a double-take to understand it was talking about a game.

Sheesh, I need sleep. And perhaps to stop learning so many useless programming languages.

Re:Confusing title

[PolygamousRanchKid]

And perhaps to stop learning so many useless programming languages.

FORTRAN, ALGOL, COBOL ... Forth ... ? Hey, if you can make money programming it, it's not useless.

Re:Confusing title

[Sulphur]

Sheesh, I need sleep. And perhaps to stop learning so many useless programming languages.

Useless programming languages are for useless programming.

--

Sigfault

Re:Confusing title

[gl4ss]

well, if you read to "arguably the most difficult two-person game to implement.", you know that the writeup is about the boardgame.

and you also know that it's bullshit, since it is not notoriously difficult to implement, to make an ai to play it well is an another story though.

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

[Anonymous Coward]

Sir, I think you should re-read what you just wrote.

Since when is Go not a game? Because it's just complicated?

Have you ever actually played go? If so, you'd know it takes alot of skill and even more practice to master.

Anything that takes practice, skill and involves fun is a game.

Red Rover does not have any 'rules' or 'regulations'. Yet, I bet you played it when you were little.

~Valk

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

Re:Go is not a game

[qmaqdk]

The Japanese versus Chinese "rules" give very different endgames, but the practice is to simply ignore that and pretend there is no problem.

That's because it would destroy the harmony of the game if you start discussing all the problems with the rules.

Re:Go is not a game

[Anonymous Coward]

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.

Re:Go is not a game

[Anonymous Coward]

Do you actually play the game. From your post it seems like you are trying to program it without any insight as a player. Sorry, but that will fail.

Go is not a game because it does not have rules that are clearly interpretable, except the new Tromp/Taylor rules.

Wrong, the rules are simple and clearly interpretable for humans. There are some odd cases, in which the different rule sets disagree, but they are very rare and it practice the game in exactly the same regardless of which set of rules you use.

The Japanese versus Chinese "rules" give very different endgames, but the practice is to simply ignore that and pretend there is no problem.

Wrong. Except a few rare situation they are equivalent.

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.

Jasiek has done a nice job of cleaning up the rules text, but again, in practice it is no difference at all. I've been playing for ten years and I have never ever made a different move because of the rule set.

Please try to learn the game a bit deeper before making judgements. Go is a hard game for beginners to grasp, and you will have to play many games before the confusion starts to clear.

Re:Go is not a game

[shentino]

Infinite capture loops are illegal moves because of the rule of Ko.

Re:Go is not a game

[Anonymous Coward]

There's some instances of multiple Ko which the standard Ko rule fails to resolve, as noted in the links provided by the grandparent. These are a rare corner-case, mind you, but they can arise. And they're taken care of by all standard rule sets, not sure what the grandparent is trying to complain about.

Re:Go is not a game

[outsider007]

Games evolve. There's a new computer variant that koreans are playing where you can place hidden stones that your opponent doesn't know where they are until he surrounds it. It's like a cross between go and battleship but it looks like it makes it more interesting.

Re:Go is not a game

[Demonoid-Penguin]

Sir, I think you should re-read what you just wrote.

Since when is Go not a game? Because it's just complicated?

Have you ever actually played go? If so, you'd know it takes alot of skill and even more practice to master.

Anything that takes practice, skill and involves fun is a game.

Red Rover does not have any 'rules' or 'regulations'. Yet, I bet you played it when you were little.

~Valk

Everything is a game. There's always a winner, and a loser, the trick is to determine when you are the latter, to become the former. All games have consequences. In the end the only guarantee you have is, that sooner or later, you lose.

Wake up Jake!

Re:Go is not a game

[Vintermann]

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:Go is not a game

[Vintermann]

It's just wrong. The endgames are the same. They are just typically played out a bit further under Chinese rules, that's all.

Re:Go is not a game

[spottedkangaroo]

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

[Kim0]

Thanks for telling me a little more about the book.

I have done deep game theoretical analyses for some years, and gotten some interesting results. One of them is that if one appears to be on the losing side, one can decrease the chance of that by making the game more random by running into more complicated fields of game space.

Wether those fields exist or not depends strongly on the end game, and in Go there seems to me likely to be the possibility of impenetrable almost infinite thickets. I do not know yet if that really is the truth, but there are some powerful hints of that, like John Tromps work in the direction making Go boards that are universal computers, and in the construction of infinite draw situation patterns.

The upshot of this is that endgames of almost maximally strong Go players may be almost infinitely long and complicated.

Re:Go is not a game

[PopeRatzo]

Go is not a game because it does not have rules that are clearly interpretable

That makes Go a great game.

Re:Go is not a game

[PopeRatzo]

It would be like saying tàijíquán is not a martial art because nobody gets knocked out (well, seldom).

Re:Go is not a game

[nloop]

Computers play it well right now. It would take a beginner years of practice to rival gnu go and that is by no means the strongest one out there. The best engines are playing at 4 dan, or borderline pro, currently. Deep Blue isn't far off.

Re:Go is not a game

[shadowofwind]

This is like saying that real numbers are political and not mathematical because of the funny way that infinities are defined and handled.

Re:Go is not a game

[FiloEleven]

Not in my experience.

I got into Go several years ago and was holding my own against gnu go in easily under a year. Then I logged on to Yahoo Games and lost every game except two, even when playing people with lower (chess-style) scores than mine and those who were too new to be ranked.

Re:Go is not a game

[nloop]

19-10 kyu is a casual player. gnu go is 5 kyu, beyond the casual range, actually getting pretty close to a dan rating. A few months gets you within spitting distance of dan? Perhaps you haven't seen beginners play gnu go. The reputation of go engines seems stuck in the 90s while their gameplay isn't. Watch them play, especially against someone with less experience.

Re:Go is not a game

[zacronos]

Go is not a game because it does not have rules that are clearly interpretable, except the new Tromp/Taylor rules.
[...]
When it is not even possible to analyze parts of games then true optimal play regresses to quarreling about it
[...]
So Go is riddled with quarrels and pretense. Not a game in practice. More like politics, or Zen.

So are you saying anything that has any ambiguities or regional variations in the rules (even if just in edge cases) cannot qualify as a game? Or that only games where the concept of "optimal play" is valid can qualify as games? I would disagree strongly with either of those positions.

I have played PLENTY of board games where not-so-uncommon edge cases are not adequately handled. That doesn't stop me from playing, and it doesn't stop me from having fun. Every time I sit down with a new group of people to play, say, Hearts or Euchre, I preemptively ask how we're going to handle certain situations. Different people play slightly different ways, and that's fine with me.

There is also such a thing as games which are played for the enjoyable experience of playing them, and so "optimal play" makes no sense. The children's game "patty-cake" is a pretty clear example, or any number of children's games, especially the ones that children make up on the spot. What about improv games such as on the TV show "Whose Line is it Anyway?" My friends and I sometimes have improv parties, where we exclusively play games like that. Or what about pencil-and-paper RPGs? Optimal play is often not the most enjoyable way to play, if it is even a concept that can be defined for a given game.

Maybe more importantly, I'd like to point out that quarrels, pretense, and politics are central tenets upon which many games are built -- I would argue that those things are likely the most prolific inspirations for games that one could find. Formal game theory is very useful for analyzing politics and quarrels, and has also been used to study the effects of pretense and lying. Aren't chess and Go both likely inspired by war?

The only way I can make sense of your post is if I conclude that when you use the word "game", you mean something very much more specific than the rest of us, containing only a tiny subset of what is generally referred to as a game in common language.

Re:Go is not a game

[nloop]

Fuego playing 9x9 has a 5d rank on KGS, looks like 2k for 19x19. I'm pretty sure crazystone can also play that well.

It was crazystone that used a 9 stone handicap to beat a 9p player with a 9 stone handicap if I'm not mistaken.

Re:Go is not a game

[Raenex]

The upshot of this is that endgames of almost maximally strong Go players may be almost infinitely long and complicated.

No, it isn't. You need to get your head out of the clouds and actually learn Go. The game simplifies greatly the closer it gets to the endgame. That's why experienced human players can almost always agree on what stones are dead under Japanese rules without using Jasiek's precise definition of Japanese rules.

Re:Go is not a game

[Raenex]

Interesting, can you name any such software that can play go and has a 4 dan rank?

http://www.gokgs.com/graphPage.jsp?user=zen19

Re:Go is not a game

[Raenex]

I got into Go several years ago

As you state, your experience is several years out of date. Go programs went through a great leap from 2006 to present, due to the technique of Monte Carlo Tree Search.

Re:Go is not a game

[PopeRatzo]

If so, you should go and play some art.

That's how I make my living, friend.

Re:Go is not a game

[Raenex]

In fact, if you include stone passing (see AGA Rules) then Chinese and Japanese rules work out the same.

As if by magic? You're confused. The AGA rules are just Chinese rules in disguise. They let you mechanically count the board as you would with Japanese rules, but the winner would be determined as if played under Chinese rules, not Japanese rules. Dame is worth 1 point and needs to be strategically considered.

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.

A smart and logical student will plunk a stone done in the middle of his opponent's territory and point out that it takes 4 stones for their opponent to kill the stone, thus causing the opponent to lose points. The student is then berated and made to feel ashamed for being "stubborn" for trying to apply logic.

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.

Yes, Chinese rules actually make sense when you try to play the game out. That's why new players should learn them first.

Re:Go is not a game

[Raenex]

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:Go is not a game

[Anonymous Coward]

Rather than making wild speculation, why not take a week to learn the basics of the game?

Yes, in Go one can make structures that are "unconditionally alive", meaning they cannot be captured anymore (unless the owning player suicides them, however this is never optimal play).

I believe the work of John Tromp that you're refering to is based on capture problems. That is, can player A capture this group of Player B. Like similar problems in many interesting games, this problem has high computational complexity.

With regards to the "endgame", usually that word is reserved for after the status of all the group is resolved (i.e. it's known which groups can be captured and which cannot), and the remaining play is squeezing the last few points of territory out. In other words, the game has stabilized, and there are not that many moves left. Playing the endgame optimally is a very interesting computational problem, and the field is known as "combinatorial game theory".

With regards to complicating the game, yes, like almost any strategy game, a player has the ability to pick complicated variations. Dare I say, pros often do this just to expose weaknesses in their opponent. However, it's nearly impossible to delay the number of moves until game completion by a significant amount. There are only 361 points to play on the board, and they only free up with captures, and there's only so much capturing you can force. The best way to delay the game is probably with ko-fights (indeed, setting up kos is a required skill of advanced players), which involve repeated captures of the same square, although these can rarely last more than a few dozen moves before it is settled.

Re:Go is not a game

[Anonymous Coward]

Certainly Monte Carlo go engines are a lot stronger than their predecessors, and it takes a lot of practice (I don't think _years_ of practice is fair to claim- it'd depend on how much of your time you were devoting) to be able to play against a good engine on today's fast multicore hardware. But I don't think the stable version of GNU Go uses UCT/Monte Carlo by default.

It's also certain that getting to where you can play at the same level as Fuego on today's machines is a very realistic goal for a newcomer while being able to do the same with one of the better chess engines is beginning to be out of reach of those who have committed their entire lives to chess.

Re:Go is not a game

[Scryer]

I saw this played at the University of Wisconsin in 1970 - Paul Purdom was on one side, but I forget the other player - maybe Ralph London? It was called Go-spiel (by analogy with Kriegspiel), and required a referee to tell the players whether their proposed move was legal, using his master board between the two players with screens to keep them from seeing the other boards.

The one game I saw played didn't have nearly the depth and interest of Kriegspiel, which I played and refereed often in the years before that at the RAND Corporation. Perhaps 9x9 Go-spiel would have worked out better.

Re:Go is not a game

[sam0vi]

And let's not forget that you play with a given number of stones, so one of the players will eventually run out of stones. That's an objective end for the game if there ever was one.

Re:Go is not a game

[jvkjvk]

A smart and logical student will plunk a stone done in the middle of his opponent's territory and point out that it takes 4 stones for their opponent to kill the stone, thus causing the opponent to lose points.

Perhaps, perhaps not.

If that stone is unable to kill anything, or make shape, and I pass, then I have just gained a point, as White. In fact there are a number of scenarios where all stones you play I can just pass.

It may be that after enough passes I actually have to act. In that case, I am only up by the number of stones up until my action.

However, there are worse things to do than try and cause trouble, even if you don't read out the situation. It is surprising how much trouble a "stubborn" player who "doesn't know when they are beat" can be.

Regards.

Re:Go is not a game

[Demonoid-Penguin]

Wake up Jake!

Never thought I'd ask to be modded down!. But seriously, it's a joke - a reference to the movie Revolver. I agree the movie is "insightful", but my post was "off-topic", maybe "funny"...aw.. whatever, I'm going back to doing some work, continue as you were.

Re:Go is not a game

[Raenex]

If that stone is unable to kill anything, or make shape, and I pass, then I have just gained a point, as White.

The problem, though, is that to prove that the stone is dead, it would take 4 stones to kill it, which would end up losing points. You can tell a beginner that it is "dead" and can be removed without play, but then you just leave the beginner confused about how grossly unfair and arbitrary the rules are.

Japanese rules don't define an easy procedure to continue play without changing the score. Chinese-style rules do.

Re:Go is not a game

[sarkeizen]

Meh, it's kind of an idiot argument and "riddled" with holes. Why do games have to conform to your particular definition? Even so for seemingly the majority of played go sequences it does in fact have rules that are clearly interpretable. There are literally thousands of historical kifu where the board state is completely unambiguous.

You are also equivocating. When someone says the "rules are simple" they mean that the rules for valid placement of stones what is complicated is optimal placement of stones. Even given that competition has required the creation of "superko" rules (which TT includes) these are actually rarely used even in competitive play. The idea that players agree that the outcome is obvious causes the termination of the game is really a non-issue. Even if some play exists which would entirely reverse the game - the fact that the opposing player doesn't recognize it is really no different than someone resigning from Chess even though they had a chance. Besides this only matters to one of the players if they disagree. In which case, you simply play it out until there is agreement.

Your conclusion is also flawed. In practice would imply that in most plays there is quarrel and pretense and yet that doesn't seem to be the case.

Re:Go is not a game

[spottedkangaroo]

Nobody I know berates the new player. We simply pass until we have to act (like the reply before last said). If they try to leave the stone there, we point out that it doesn't have two eyes, so it's dead. It's not arbitrary at all, it was explained before we began play. This just proves my point. Only beginners see this as a problem because they don't understand life and death yet. It is most certainly well defined.

Re:Go is not a game

[lonecrow]

I have to agree with those that are disagreeing with you.

It is a game and it does have rules. A very small number of very simple rules.

1) Black goes first
2) play on the intersections of the game board grid
3) each line extending from a stone or group of stones is called a 'liberty'
4) any stone, or group of stones, that has no liberties at the end of a players turn is removed from play
5) you can not play a stone in a place where it would have no liberties
6) you can not recreate how the board looked on your last turn (The Ko rule). Hard to describe in writting but exceedingly simply to understand when demonstrated.


6 of the simplest rules creating a wonderfully diversity of game play. Easy to learn hard to master, arguably the best type of game and one of my favorites.

I have never had to quarrel with another player about the legality of a rule nor about the current balance of play, nor about who has won or lost.

Perhaps there is a game that is similiar to Go but not Go that you are talking about.

Re:Go is not a game

[Raenex]

Only beginners see this as a problem because they don't understand life and death yet.

Which is entirely the point. What is alive or dead should be determined by the skill of the players and simple rules, not appeal to authority.

If they try to leave the stone there, we point out that it doesn't have two eyes, so it's dead.

A simplistic and incorrect rule. First, you have to precisely define what an eye is. What you really mean is that two eyes *can* be made, which depends on skillful play. Second, seki doesn't conform to that rule.

It is most certainly well defined.

If you consider hypothetically perfect play, then maybe it's well defined, but now you're getting into Robert Jasiek territory. Japanese rules require Go skill, to acquire Go skill you have to understand the rules so you can play, resulting in the absurd Catch-22 situation.

Now compare all of the above to Chinese-style rules. What is alive or dead? Just play and find out.

Re:Go is not a game

[Kim0]

You have no rule about winning.

Kim0+

Re:Go is not a game

[gl4ss]

if it was simple, you could have described the rules in the space used for the post.

I think the original not a game rant was about that before you start a game of go, you need to decide which game you're playing, so you're not playing go, but starting the game with another game that decides what go is. I guess some people like that, adding magic to the mix and making people who've played previously with the same set of rules have an advantage.

so it's a great way to waste time even without playing.

Re:Go is not a game

[spottedkangaroo]

There is no appeal to authority. The rules are very clearly defined. You're simply choosing to not follow them. At tournaments, there are sometimes 200 people none of which would ever disagree about what is dead and what is not.

The problem is (and I can agree that this is a problem, but only for the first few games at most), that Japanese rules require that you understand alive and dead.

In games with beginners, I explain that you need two eyes and then encourage them to try to live or kill my shape. It's all quite clear after the first few times. And there's no ambiguity at all; no matter how hard you try to create some, there simply isn't any.

In any game, even amongst the most skillfull, players are encouraged to try to kill things they think are dead. There is always an ahh-hah moment were you see why you were wrong (or right). In that sense, there's no difference between the Chinese and Japanese rules. The only practical difference is that in the Japanese rules the attempt will change the score -- so you have to consider whether it's worth the attempt.

If you are unable to see what I mean, then it's clear to me you still don't understand the Japanese rules. Trust me on this: there is no ambiguity and no appeal to authority. We all understand what is alive and what is dead. But you do have to know the basics and it takes a few days to master.

Re:Go is not a game

[spottedkangaroo]

It is not simple. It is rather complicated because it requires a complete understanding of alive and dead. It really only takes a few games to master, but it is indeed rather complicated.

It is a concept that the Japanese (or Korean, or Chinese, etc) would learn when they're 6 or 8 and the Japanese rules are unapologetic about being complicated. But they are not ambiguous and they are very clearly defined.

If you came to my go club, I could demonstrate and have you ready to play under Japanese rules in a matter of an hour. There's a lot to it, but it's simple once you get over the hump. Hell, you don't even need to go to my club. Hang out on KGS for a couple hours and you'll gain a complete understanding.

Re:Go is not a game

[umghhh]

With all due respect for Robert: his work mostly concernes rules and faults built within and is most useful for coders of GO software and professional players. Other than that majority of players in Europe does use a system of counting that they think is based on Japanese rules yet it is not. Fascinating is that it still works for them so maybe the problem is not so widespread as some people like to think.

Re:Go is not a game

[umghhh]

You mean confusion stops at the point when you realize that the full understanding is impossible?

Re:Go is not a game

[Raenex]

There is no appeal to authority. The rules are very clearly defined.

No, they aren't, and that is why there is a very long history of failed attempts at formalizing them. They work well enough among experienced players.

At tournaments, there are sometimes 200 people none of which would ever disagree about what is dead and what is not.

Disagreements are rare, but not the zero concurrence you indicate here.

The problem is (and I can agree that this is a problem, but only for the first few games at most), that Japanese rules require that you understand alive and dead.

Many people give up on the game because they don't understand the Japanese Catch-22 logic. Beyond that, disputes still occasionally occur beyond the first few games, which results in players usually verbally disputing the position, and then appealing to authority to resolve it if that doesn't work. I play on KGS. I've seen this happen many times.

In games with beginners, I explain that you need two eyes and then encourage them to try to live or kill my shape. It's all quite clear after the first few times. And there's no ambiguity at all; no matter how hard you try to create some, there simply isn't any.

Bullshit. I've already explained that your "two eyes" is simplistic and wrong. It doesn't work for seki. Let's also hear how that explanation works for bent-4 in the corner. Even 20-kyu players, who have played dozens of games, have trouble with certain life and death situations. I can even show you examples from players near 10-kyu, or even dan players, all from games that I have personally played. These are not common situations, but they DO happen now and then. I estimated it at a 1% occurrence of my games.

The only practical difference is that in the Japanese rules the attempt will change the score

Which means that they are not practical to apply.

Re:Go is not a game

[lonecrow]

Every game CAN be played out to it's ultimate end. It would be tedious to do so but there is nevertheless a rule about how to count points and determine a winner.

However I suppose I see where you might be going. It may be easy for human players to determine at a glance that a corner or area belongs to a certain player and that fighting it out further would gain nothing. It could be a lot harder for a computer to determine the same.

Re:Go is not a game

[spottedkangaroo]

It's not bullshit, the rules are fine. You don't understand them yet or you're being intentionally obstinate. I no-longer care which. Whatever man. They're definitely complicated. Nobody's arguing that.

Yes, the two eyes thing is simplistic but it's easy enough to explain the long version. The game is fine and it's survived thousands of years, hundreds with the rules they use now and few have problems with it. Certainly you and Ing and a couple others, but with the exception of certain edge cases, the rules are just fine and don't require the kind of crazy head games Ing wanted to play (they were academic anyway).

Sometimes disagreements come up at tournaments, it's true, but it's easy enough to look up in the rules and convince both players. It's pretty rare though.

Re:Go is not a game

[Raenex]

It's not bullshit, the rules are fine. You don't understand them yet or you're being intentionally obstinate.

I've already explained a couple of times why your explanation is bullshit, yet you completely ignore all the details. You are the one being obstinate.

The game is fine and it's survived thousands of years, hundreds with the rules they use now and few have problems with it.

Maybe you can explain why the Go associations for the United States, Britain, New Zealand, and France all moved away from Japanese rules. If you want the answer, look here:

http://www.cs.cmu.edu/~wjh/go/rules/AGA.commentary.html

See the section under "Transmittal letter". In particular:

"the American Go Association has for several years been working toward a "simplified" set of rules for use among amateurs--a set of rules at once simple enough to be understood by beginners, clear and comprehensive enough to guide tournament play among amateurs--when the tournament director (and the strongest players present) may not even be of dan level"

"For amateur players in the West, where professionals are few and far between, and entire cities and regions may lack even dan-level amateur players, however, such rules present difficulties. We believe that our "simplified" rules are more appropriate for use with amateurs, especially where no very strong players are available as arbiters or referees."

"The status of disputed groups is to be settled by playing out the full-board situation.

Playing out the situation allows players of varying levels to resolve complex life-and-death situations according to their abilities, without depending on outside authorities or exhaustive analysis, and hence is most suitable for amateur play. While the new Nihon Ki-in rules are carefully crafted to resolve most of the difficult cases which used to require exccptional handling, and are probably very appropriate for professional play, they depend on a high level of sophistication in analyzing each position based on rules which are slightly different from normal play (due to the special handling of kos). In principle, resolving such end-of-game disputes requires the players--or some competent authority in attendance--to have the capacity to resolve life-and-death problems of arbitrary complexity! Rather than attempt to resolve each local situation "in principle" in the ideal fashion through extensive analysis, playing the position out achieves a fair result (it is based on the relative reading strengths of the players themselves) in potentially bounded time without the need to appeal to outside authorities or make use of special rules."

Re:Go is not a game

[spottedkangaroo]

K, fine. You win. Nobody could ever play under Japanese rules. They make no sense. Although, I think it's Ing's fault. Their primary source of funding was the Ing foundation. Also, nobody I have ever met plays under any other rules than Japanese rules, except at AGA tournaments anyway -- where people play under Japanese rules and pass a stone at the end without understanding why. But I suppose you're right. Nobody could ever comprehend Japanese rules.

Re:Go is not a game

[Raenex]

I never said nobody could play under Japanese rules. I just said there were problems with them, as opposed to how simple and problem-free you were painting them. Beginners struggle with them, and for a very small percentage of games, even experienced players can run into trouble. They are hard to define precisely, and you can't blame Ing for that. Even the Nihon Ki-in tried and came up short. It's just the nature of the rules.

As for the pass stone, you don't really need to know why it's used. All you really need to know is that AGA rules are Chinese/area-scoring rules, where dame is worth 1 point. The pass stone is used as a trick to let you count using the Japanese method, but AGA rules are just Chinese rules in disguise, and you could forgo the pass stone if you counted using the Chinese method instead.

Re:Go is not a game

[spottedkangaroo]

I'm not blaming Ing for the Japanese rules being difficult, I'm blaming him for screwing up AGA rules. I don't know anyone who actually likes those rules. They may be easier for beginners (although that is not my experience); but they're irritating for seasoned players.

Re:Go is not a game

[Raenex]

Ing had his own ruleset. As far as I know, he had nothing to do with AGA rules. AGA traditionally took money from the Nihon Ki-in, but they moved away from Japanese rules despite the funding, because Japanese rules have a complex and imprecise playout. All the Go associations that moved away from Japanese rules did so for practical purposes, as clearly stated in the Transmittal Letter I linked to and quoted from.

Re:Go is not a game

[spottedkangaroo]

Whatever. You already won, I said so. Japanese rules suck or whatever.

We should play a game some time. I figure you probably play, otherwise I can't figure why you'd care.

Re:Go is not a game

[Raenex]

I'd take your replies a lot more serious if they weren't filled with "whatever", didn't look so sarcastic, and didn't make incorrect statements like those regarding Ing.

As I mentioned earlier, I do play on KGS. I care more than most because like Kim0 and many others, I had a bad experience trying to learn the Japanese rules.

Re:Go is not a game

[spottedkangaroo]

They're filled with whatever because I don't agree with the AGA or you and never have. I've read the literature on the subject and I simply don't agree with it. The only problems with the Japanese rules are silly edge cases that rarely come up (not including bent-4, which we usually just ignore and play through at my club). The edge cases are normally resolved through discussion or by playing them out. So whatever. Hate on the rules, but they're still best.

I do have a problem with AGA and Chinese rules. They encourage players to keep going when they should really quit. I'm not aware that I've ever played anyone that seriously preferred AGA rules to Japanese rules. It's probably happened, but I'm not aware of it. We've had a few Chinese people stop by. They prefer the Chinese rules and Chinese counting... needless to say.

When the non-Japanese rules have rules to discourage people from playing impossible situations just to see if you make a mistake, maybe I'll like them a little more.

Re:Go is not a game

[Raenex]

They're filled with whatever because I don't agree with the AGA or you and never have.

Then cut the passive/aggressive bullshit like "You already won, I said so."

The fact is I did win. You started out with ridiculous claims that nobody ever had problems at tournaments, that Japanese rules were easy to apply, and that after a few games (or a couple of hours on KGS) life and death issues at the end of games weren't a problem for beginners.

You've made incorrect arguments concerning Ing, made incorrect arguments concerning the history and application of Japanese rules, failed to understand that AGA and Japanese rules weren't somehow miraculously the same, and gave simplistic and wrong advice concerning what is dead and what isn't. Anybody who read just your statements alone would have been completely misinformed on a whole host of issues.

I backed up my claims, after being told I was naive or obstinate, with observations from KGS, data from my own personal games, and an official letter from the AGA. I pointed out how the Go associations for the United States, Britain, France, and New Zealand all moved away from Japanese rules for practical reasons.

So, "whatever" yourself. I'm done replying to you.

Re:Go is not a game

[spottedkangaroo]

You won, you definitely won. No question. You're fully documented. But I still don't agree that there are any problems with Japanese rules and I don't think I misinformed anyone on any point. I definitely firmly believe the AGA switched to Ing-resembling rules because of Ing and not because Japanese rules are too hard despite the public documentation. The problems are so rare they just don't matter very much.

So, whatever man.

Re:Go is not a game

[RockDoctor]

And let's not forget that you play with a given number of stones, so one of the players will eventually run out of stones.

Not true.

In informal play, it's not true because any real (i.e. routinely used) set of stones will have had some stones disappear under the sofa, others will have been shattered by a vigorous opponent (Dave Hall - I'm talking about YOU!).

In formal play (e.g. tournaments), it's not true for exactly the same reason. Plus, if one player finds that they're running low on stones, then it's because there have been a lot of prisoners captured. So there are a lot of prisoners in each player's bowls. So, you take 10 stones from each player's prisoner collections and put them back into the player's bowls. The score DIFFERENCE at the end is preserved, so it doesn't matter.

It is not impossible that with an extremely stubborn learner then you might possibly run out of stones. But that wouldn't last more than a dozen games until the stubborn learner starts to learn how to develop light, resilient groups. At which point, they're well down into the 20s of kyu, and are not beginners any more.

The British championship final game had the running out of stones problem about 5 years ago, solved as described above. The other dozens of sets in the tournament room had been packed away into people's cars, and it was quicker to shuffle stones than to crowbar a spectator out to go and get more stones. There were enough high-end players around that the solution was uncontroversial.

Re:Go is not a game

[RockDoctor]

Go programs went through a great leap from 2006 to present,

This is true.

due to the technique of Monte Carlo Tree Search.

This, however, is much more controversial.

True, around about then (I'd have thought a couple of years earlier, but it's not terribly important) a number of game engines did start to incorporate MC engines into their game play, but it was as part of a package of measures. Some used the MC in their move generating engines ; others used MC in their move scoring engines (if you've got a billion plausible moves to analyse, you'd better have a quick engine for assessing the results of those moves, and MC is quick to generate). But all the reasonably effective engines used other algorithms in different parts of their gameplay.

In fact, IIRC one of the big bears of Computer Go (it may have been Nick Wedd - I'll try to remember to ask him next time he beats me at the board) built a pure MC Computer Go engine precisely to use as an opponent for computer Go engines. It's a pretty stupid player, but it does allow other ComputerGo designers to get some sort of benchmark to try their different modules against, because it's a consistently stupid player. And it's computationally very lightweight for Nick's server to run dozens of instances of.

No one has used the "Imagine a Beowulf cluster of those" Slash-meme yet? Shame, SlashDot, shame!

Re:Go is not a game

[Raenex]

due to the technique of Monte Carlo Tree Search.

This, however, is much more controversial.

There's nothing controversial about this if you follow computer Go development. Before Monte Carlo, programs were stuck in a rut. They were improving, but very slowly. After Monte Carlo, they quickly went from something like 8k to 2k, and have now reached 4d on KGS. Every strong bot today uses Monte Carlo Tree Search as it's fundamental algorithm (as opposed to alpha-beta).

But all the reasonably effective engines used other algorithms in different parts of their gameplay.

Not really. The heart is Monte Carlo Tree Search, like the heart of most chess programs is alpha-beta. The stronger programs add more Go knowledge to the search process, just like a chess engine might have knowledge about pawn structure, but it's still Monte Carlo.

In fact, IIRC one of the big bears of Computer Go (it may have been Nick Wedd - I'll try to remember to ask him next time he beats me at the board) built a pure MC Computer Go engine precisely to use as an opponent for computer Go engines.

It sounds like you're thinking of Don Dailey and CGOS. He runs a dumb Monte Carlo bot as a standard player, true, but it's intentionally dumb and not very advanced. Actually I think the benchmark players have been upgraded recently, because the old one was falling too far behind.

The interesting thing is that GnuGo (without Monte Carlo) was used as the benchmark player when people started coming out with Monte Carlo bots. Early programs would get something like 20% win rate against it. Monte Carlo programs now completely dominate it.

Re:Go is not a game

[RockDoctor]

It sounds like you follow Computer Go much more closely than I ever did (I lost the password for my KGS account several years ago, but I'd not bothered to use it for several years before that. Give me a board and a bowl of stones any day.). But the implication that Monte Carlo methods were new to Computer Go in the early 'noughties simply isn't true. One of the people who taught me Go in the mid-80s was using some form of Monte Carlo on his BBC Master Go playing engine back then. Or at least, that's what he claimed - I never saw the program running, and he admitted that it was stuck in the 20s of kyu. As was everything else in the Computer Go world in the mid-80s.

What is a 4D on KGS out in the real world? This week? I do recall getting hit by a couple of the mass down-grades during the couple of dozen games I played on it in the several years that I had an account. So it seems that the problem of grade inflation still persists.

Re:Go is not a game

[RockDoctor]

RULES FIGHT !

OK everyone, we know how this works out. We throw the participants into the pit along with the scorpions, then divide the crowd into four parts who scream "Vi", "EMACS", "Gnu/Linux" and "Linux" at each other until we've all got sore throats.

Then we go to the pub. To attend to the soreness. It's purely medicinal.

Except for the scorpions. They don't come to the pub ; they stay in the pit. That's an important rule.

Re:Go is not a game

[Raenex]

But the implication that Monte Carlo methods were new to Computer Go in the early 'noughties simply isn't true.

I never said Monte Carlo was new. I said "Go programs went through a great leap from 2006 to present, due to the technique of Monte Carlo Tree Search.". In your first post, you denied that Monte Carlo was the main component. After I refuted that, you now argue argue about the date.

Yes, absolutely, Monte Carlo has been around for a long time, but with very limited success. It was only starting in 2006 that it became wildly successful and took over the scene as the standard way to implement a bot. Before that it was simply a minor, but interesting area of research. This is all documented in the computer-go mailing list archives and refereed papers.

What is a 4D on KGS out in the real world?

Which real world? There are many ranking systems, and they all vary to some extent among each other. KGS is as real as any of them. 4d on KGS is quite a respectable rank. Also, the ranks on KGS have been fairly stable for some years now.

Re:Go is not a game

[Raenex]

RULES FIGHT !

Yes, the debate is quite old, but that doesn't mean it's meaningless or not worth having. Problems with the Japanese rules are downplayed by their proponents, which leads to misinformation and frustration among new players who are told how simple they are. There are also practical concerns in tournament play among amateurs, which is why the AGA and other associations moved away from them.

WTF?

[mac1235]

"Many games are written in C++, but this requires a lot of ‘libraries’ to store information, along with a lot of man power to create them. XNA comes with a number of pre-made libraries, making it a lot easier to program with."

I thought C++, (as a well established Programming language) would have more libraries than XNA, which I had not previously heard of?

Re:WTF?

[mustPushCart]

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:WTF?

[TheNetAvenger]

You are not understanding how languages work inherently different.

All the C++ libraries in the world will not change how C++ fundamentally works.

Re:WTF?

[bcmm]

It seems that whenever MS gets involved in something really awesome, they have to dishonestly push one of their more bullshit technologies with it. (They sponsored the above.)

Re:WTF?

[cbhacking]

It's a matter of convenince. There are more C++ libraries than .NET libraries, but that doesn't make it convenint to find or use a good game framework that provides the libraries you need and isn't a pain to use. XNA isn't a language, but it is a framework aimed specifically at developing games, and from what I've seen it's very good at that. It's based on .NET, and typically used with C#. Thus, for game development, XNA (and .NET) is a good choice because it largely avoids the "I need to find/write code that does X" and "I need to integrate this piece of code that does X with the other piece of code that does Y" problems.

There's nothing inherently wrong developing a game in C++, but it's a lot easier to do it if you start with the XNA framework (with the .NET language of your choice, possibly even C++).

Re:WTF?

[phantomfive]

It was described poorly in the article. XNA is Microsoft's framework for writing games in C#, in other words, it IS a library. It's one way to program graphics on the Xbox, and the only way on Windows Phone 7. It's not as capable as some other frameworks (if you want to see games like this on WP7, forget about it). If you like C#, you will probably like XNA. In my opinion it's as good as any other sprite framework.

Re:WTF?

[bcmm]

"Many games are written in C++, but this requires a lot of libraries to store information" is a bullshit justification for any technology.

Re:WTF?

[gl4ss]

remember BGI?
borlands crappy graphics interface. sure, it sucked, but borlands dos sdk's did come with it(essentially the same thing available in c and pascal, and in finland there was even localised wrapper distributed on it, making all the drawing commands in finnish.. ugh! it was actually an elementary school course on programming, but it wasn't programming, it was scripting paint commands).

xna is just another name for .net + set of painting etc libs.

and of course, that sentence is saying that creating those libs takes a lot of manpower.. well, those xna libs didn't spring up to existence overnight either, they might be implying that those magical c++ libraries are harder to use and are properiaty so you can't use them. anyways, xna needs to be there for funding focus reasons for this project - and well, this project had to be in dire need of those.

Re:WTF?

[tepples]

You realize that it's an Xbox360 game, and options for making those are kinda limited?

Yeah, like how would one port an existing C++ game to Xbox 360 without being a well-known company?

I mean, seriously, did you expect MS folk to write a game for Wii or PS3 instead?

Not Wii, but Microsoft has been known to write games for Game Boy Color, Game Boy Advance, and Nintendo DS.

I seem to recall

[thesk8ingtoad]

Reading a research paper a few years ago that presented the idea that the best way to approach the game was through catastrophe avoidance. The idea was to identify the moves that would lead to a massive loss, then to take another move at random. I wonder how their AI would fare in comparison.

Re:I seem to recall

[lakeland]

Similar.

Monte-carlo will pick the path which leads to a win most often and this tends to produce the behaviour you've described. They still struggle when they're ahead in terms of guessing the most likely catastrophe and preventing it, I suspect that is the advance that will come next

how well does it rank?

[mbuimbui]

Is it a dan yet?

It isn't very strong

[Anonymous Coward]

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

Re:It isn't very strong

[Vintermann]

It is relatively easy to beat the existing Go games on a 19x19 board.

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:It isn't very strong

[GasparGMSwordsman]

Most of the rated programs require a server cluster to run at high skill levels. While it is nice that they can reach a level to be competitive against strong players, it is really stretching the facts to claim a personal user couldn't easily crush a standard install of any of the above programs.

Some examples from wiki http://en.wikipedia.org/wiki/Computer_Go#Recent_results:

On February 14, 2009, Many Faces of Go running on a 32-core Xeon cluster provided by Microsoft won against James Kerwin (1p) with a handicap of seven stones. The game was played during the 2009 AAAS general meeting in Chicago.[9]

On August 7, 2009, Many Faces of Go (version 12) resigned against Myungwan Kim (8p) in a 7-stone handicap game.[10] Many Faces was playing on a 32 node system provided by Microsoft. The "Man vs. Machine" event was part of the 2009 US Go Congress, which was held in Washington DC from August 1 to August 9.[11]

Re:It isn't very strong

[Vintermann]

They need clusters to do their best, sure, but they're better than I will ever be on even "modest" hardware. Sensei's Library claims Zen19 is running on a Mac Pro 8 core, Xeon 2.26GHz.

Zen19 is taking all comers on KGS - including, presumably, people who study it intensely to find predictably exploitable mistakes. It would be a very good tool for rating advancement if you could find such errors, since it's ranked at 4d.

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.

Re:Go is a pretty cool game

[shadowofwind]

Ha ha, enjoy the moment. 'That go guy' managed to get a scene inserted in the new TRON movie. What was the last cool movie you got into? Blade Runner? And a movie chess scene is always a display of raw intellectual strength, as opposed to a zen-like power to master nature.

Re:Capitalization

[EnglishTim]

The British Go Association would capitalise Go, Chess and Checkers, although it would be more likely to refer to the last one as Draughts.

I don't know whether they're correct.

Re:Explanation of go AI

[cheesecake23]

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.

Want to play the game for free? Some pointers

[Reemi]

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.

Re:Oh, who cares about quality?

[Alex Belits]

Microsoft keeps a "research team" for the sole purpose of paying people to not work for Microsoft's enemies (what at this point is pretty much everyone else). Microsoft's own interests are so far at odds with any kind of progress in technology, they can't give those "researchers" any projects that Microsoft itself can use in its own products, and this is the fact that I am going to bring to attention every time Microsoft Research is mentioned here.

Re:Oh, who cares about quality?

[bloodhawk]

What a load of horse shit. Where do tin foil hat wearing retards like you come from. MS couldn't afford to do that even if they wanted to. Not to mention the share holders would tear them to pieces for such an insane waste of money. MS research has produced a LOT of highly regarded research in many fields ranging from robotics to graphics, many of which do find there way into products eventually.

Re:Oh, who cares about quality?

[Gadget_Guy]

Wow. Is this mentioned in memo that was released as part of a court case? Is there something about it on Wikileaks? Or are you just making up sh!t because you just don't like Microsoft?

Re:Oh, who cares about quality?

[serviscope_minor]

That and the kinect of course, the key component of which (the human body pose inference) came from their research department.

Circular reasoning (nothing is obvious)

[mangu]

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.

How many times people have considered something "obvious" that later turns out to be wrong, when you analyze it to the absolute end? There seems to exist a consensus that some positions are better than others, but how do you know it unless you play it to the end?

I've never played go, but I often see comments on how difficult it seems to be to implement a good software to play go. Perhaps that's because go isn't really that well understood by humans either. When computers start playing go better than humans, some of these winning positions may not be so good after all.

Re:Circular reasoning (nothing is obvious)

[Kim0]

I could not agree more.

Kim0+

Re:Circular reasoning (nothing is obvious)

[Raenex]

There seems to exist a consensus that some positions are better than others, but how do you know it unless you play it to the end?

Exactly true, and the Japanese rules only make sense by referring to rules where you can play the game out. The history of Go rules are murky (the game is thousands of years old), but I firmly believe that Japanese rules were derived as a shortcut from simpler rules were it was easy to play things out. If you learn Chinese-style rules first, you can gain this insight as to how the Japanese rules make sense.

In practice, Chinese-style rules and Japanese-style rules are equivalent to within 1 point. Most games are decided by more than 1 point, and the game is played virtually the same.

Perhaps that's because go isn't really that well understood by humans either.

In practice, greater than 99% of games end without any such mystery when played by strong players. Players new to the game do not have this experience, so they should start with Chinese-style rules to avoid the mysterious nature of the endgame.

Re:Circular reasoning (nothing is obvious)

[mangu]

Q: What groups are "alive"?
A: Those groups that Go masters agree are alive.

Q: Who is a Go master?
A: People who know which groups are alive.

As I said, circular reasoning.

Assuming a set of rules that is unambiguous and algorithmic, then the problem of writing a perfect software for playing Go should be only a question of having enough machine power, just like for chess.

It's interesting that after machines started beating the top chess players they discovered some endings that were formerly thought to be draws that actually could be won if played perfectly, although it would take a large number of plays to win. I'm willing to bet that some day the same will be found to be true for Go.

Re:Circular reasoning (nothing is obvious)

[Anonymous Coward]

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.

Re:Circular reasoning (nothing is obvious)

[umghhh]

Well it is a game with full information which means if you knew all there would not be a point in playing. I guess so called Go Gods would not need play then as all would be clear to them from the onset. This particular property of the game is especially visible in determination of so called Komi which is a number of points White gets for having to start as a second.

Playing till the end is one way of ensuring that the result is correct and this is I think foreseen in some rule-sets that if players do not agree on status of some groups at the end of the game then they have to play out the game. This still does not guarantee that the result of such play-out is correct. One of fascinating things about this game is how it is similar to problems we encounter in our lives where complete information even if seemingly available (as with all stones on the board) still the knowledge what the status is, is not available. Why should it be? Looking at this from another angle do you think that Monte Carlo bots that seem to be approaching level of profi players or any hypothetical software that could win against strongest human know anything about the game?

Re:Circular reasoning (nothing is obvious)

[RockDoctor]

This still does not guarantee that the result of such play-out is correct.

I think you mean "ideal" or "perfect" rather than "correct". If players play moves which are not illegal (most moves are not illegal, all of the time), then whatever they play is correct, even if it is drastically sub-optimal. The old thing of the novice playing their first 10 stones to surround 12 points in the corner, while their teacher has taken most of the other 49 available points may be perfectly correct, even if drastically sub-optimal (I'm assuming a 9x9 board and a near total novice).

A lot of what makes Go so fascinating (for me) is that feeling of "if only I'd played one stone higher/ one stone lower", "if only ..."

Being able to see where you (or your fellow player) could have played differently, and probably more effectively, is a big thing for my enjoyment. YMMV.

Re:Circular reasoning (nothing is obvious)

[umghhh]

yes you are right I meant here 'correct' in context of correct play-out i.e. best possible play and not in context of rules i.e. what is/is not a legal move. The problem or issue seen by some as a problem is that we humans cannot really determine whether a play shown by players in such play-out case is really the best. This has for some a consequence that such play-out is pointless and 'wrong'. This goes into direction where ambiguity of so called japanese rules i.e. ones used most of players in Europe is or is not invalidating the rules - I think I can live with this even if in some cases this may strip me a win in an important game. There are people that do not accept this. For me this ambiguity even if unpleasant is still a valid part of the game and another mirror of reality on the board - as the game is an abstracted struggle of two armies etc.

Re:Circular reasoning (nothing is obvious)

[RockDoctor]

Such philosophical niceties wash over me.

The game (any specific instance of the game) exists in the context of the people playing it at the time of play. If one makes a move then, and it is not illegal, then it is the move that you have to live with. Whether it was optimal or not ... that's your fault. You can regret making mistakes, but nonetheless, you have to live with the moves you make.

Yes, I do allow my opponents to retract moves. But I prefer them to make their move once, then let me get on with considering my response.

Consumer-quality? So they're dumbing it down?

[smchris]

I don't see Clippy. GnuGo is way more than adequate as a backend for my abilities.

Re:Oh, who cares about quality?

[PopeRatzo]

That's my whole point, you dumbass!

Take it easy, Alex. It's too early to get so worked up.

Re:Oh, who cares about quality?

[cbhacking]

Wow, you both fail reading comprehension and basic knowledge about the industry.

MSR work goes into a *lot* of Microsoft products. Everything from little improvements to crypto techniques (which are still often huge news in the relevant community), to significant features like grammar checking, to full-fledged products (Surface is the best-known at present, but not only; for example MSR also delevoped the game Allegiance which was somewhat before its time but open-sourced when it wasn't a commercial success).

Also, if MS is "only interested in product crap" then why does so much of MSR's work end up in use? Why do they release cool new stuff like Kinect? If MS is "maintaining a monopoly at any cost" then why do they support projects like Mono or develop ways to run Linux better inside their hypervisor? Why would they bother with things like Bing, when they don't have anywhere near a monopoly on search?

Re:Fiddling While Rome Burns

[EnglishTim]

Oh, that's a great idea. Grab a bunch of researchers, give them a buglist, and throw them at an enormous codebase like Windows which they've never seen before. They're sure to fix more bugs than they create.

Misleading Title?

[rawler]

From the title, I expected something completely different.

Re:Relatively

[Vintermann]

It was a reasonable parsing of what you said. Either way, it does injustice to the Go Program writers: They have written programs that a go club attendee starting today can not take for granted that he will ever beat (assuming he has neither very much more or less talent than usual).

And that's not even taking program progression into account: 4d is simply out of reach for most of us. Most people on KGS seem to flatten out at 1k/1d or below, and use years for each further level - if they ever get them.

General applicability?

[nten]

Does retreating to chaotic gamespace work in other complex games too? It makes intuitive sense that if an opponent is better at you with pistols at ten paces, that you choose shotguns at twenty. If it is not considered bad form to refuse to acknowledge defeat until the last move, it seems this technique could turn Go into a game of mental endurance.

Re:General applicability?

[Kim0]

My mental image is a rabbit running into a thicket to avoid a fox, or eagle.

The Norwegian young chessmaster Magnus Karlsen is said to rely on making the game so complex that only he understands it.

Kim0+

Re:General applicability?

[RockDoctor]

Does retreating to chaotic gamespace work in other complex games too?

It might be pertinent to first ask if it works in Go. In my (not trivial) experience, it doesn't. Someone who has run out of ideas and starts playing randomly is going to be shredded in the next handful of moves, unless the other player is deliberately playing a "teaching game". What can seem to the inexperienced player (and I suspect that Kim0 is such - he may only have a few tens of thousands of games under his belt) to be chaotic play normally consists of several mutually entangled threads and does have a structure. Though you might need to be playing at a comparable level to the combatants on the board to see the structure.

"I don't understand this structure" does not equal "this is structureless."

Re:Fiddling While Rome Burns

[Czmyt]

It's Windows 7 Enterprise 64-bit with Microsoft Security Essentials. You're lucky not to have experienced this little annoying bug that is probably not enough of a time waster that it's worth seeking a solution online, let alone spending the time to submit a detailed bug report. Yes, I know approximately how big the Windows source code base is. Yes, I've made money writing software and also been paid to find workarounds to stupid bugs like this one. I would not allow them to actually change the code, just make suggestions to the "code monkeys." Serious point though: I think there is something wrong with a company that spends 9.5 billion annually on research yet they cannot manage to fix a bunch of six-month-old bugs in one of the most important parts of their flagship product.

Story?

[Sarten-X]

The worst part of this I see is that Go now gets a storyline:

The game starts with the player receiving a letter from a Go master explaining that your twin is missing. When you visit the master, he tasks you with the Path of Go quest, through which you must find your twin. Through the experience, you learn and play the game. In the course of your journey you interact with a number of characters and challenge them in games of Go.

As much as I like good stories, there are situations where you just don't need a story. A computer adaptation of a casual game is one of those times.

Coming next year from Microsoft: The Great Solitaire Battle! As the evil sorcerer throws his magic cards at you, you must make order of them to build up your own magical reserves!

Re:Capitalization

[adamdoyle]

You don't capitalize "checkers" or "chess"; you shouldn't capitalize "go".

It's one of those areas in which you're dealing with shades of gray. You wouldn't say "the chess" or "the go," which is a characteristic of a proper noun. (not being preceded by "the") Proper nouns are, obviously, capitalized. It really comes down to whether or not "chess" and "go" are proper nouns. They are names, which are generally proper nouns, but it's usually more _brand_ names than anything. It's not really something I would criticize though. It could really go either way..

Re:Capitalization

[BitterOak]

You don't capitalize "checkers" or "chess"; you shouldn't capitalize "go".

The difference is, the words "checkers" and "chess" do not have any other meanings in the English language besides the games, so there is no ambiguity. The word "go", however, is a very common verb in the English language, so capitalizing the name of the game helps to clarify the meaning.

Re:Oh, who cares about quality?

[spongman]

Yeah, i can just imagine all those PhDs sitting around all day thinking "well, I got my doctorate and all I'm doing with it is sitting here at Microsoft all day twiddling my thumbs not working for their competitors. i guess it's ok, at least i'm putting food on the table..." LOL

Re:Oh, who cares about quality?

[spongman]

there's so much cool stuff from MSR it's not funny.

however, one the best things IMHO is the Z3 theorem proover and related projects such as Pex and http://research.microsoft.com/en-us/projects/specsharp/.

Check out their online game Pex4Fun.

IGO for DOS, Windows, iPhone

[northerner]

The Microsoft Go program is only for Xbox.

For those that would like to try Go on a PC, there is a good version on Go for DOS & Windows called IGO by David Fotland, and it's free.
I've been using the DOS version which runs fine in a DOS window on a Windows PC.
There is a Windows version called Igowin and a version for the iPhone or iPod Touch or iPad.
I haven't tried the iPhone version yet.

IGO plays on a reduced sized 9x9 board, but is good for an introduction to the game.
The fill size version with a 19x19 board is called The Many Faces of Go and is available for purchase.
The readme.txt file says:
This program contains the same go engine as The Many Faces of Go, but only uses the first 5 levels (out of 10). It uses the same graphics as The Many Faces of Go, but is limited to 9x9 boards only.

To download:
http://www.smart-games.com/igo.html
http://www.smart-games.com/igowin.html
[the Windows has info on the iPod version]

Re:Capitalization

[adamdoyle]

Really? I find it hard to think of any examples. "The United States", sure, but that is very awkward. "The Germany"? "The Monopoly"? "The Phil"? "The Microsoft"? "The It's a Wonderful Life"? "The January"?

This rule seems to be not even remotely valid. Am I missing something?

I was sortof unclear, but I was saying that if it IS NOT preceded by "the," then it's a proper noun. "The United States" seems to be one of the few exceptions.

no incentive

[hxnwix]

Microsoft already has the money you payed for Windows 7, so there's no reason to invest any more money in Windows 7 unless it is so buggy that you'll avoid the next version.

However, it's not as if this is the first Microsoft OS you've used. Knowing that the previous iterations had glaring bugs, you still bought this version of Windows. Everyone is in this boat - Microsoft owns the desktop market and has for some time.

All that aside, I do find it odd that MS continues to invest so much in research that never bears fruit for them. Why bother when their only successes come from appropriating and integrating the ideas of others? Microsoft has been "researching" pen computing and touch technology for at least 15 years, and yet they can't hope to compete with the iPad unless they throw out their work and crib from Apple. The existing MS work is a sunk investment that they are clearly having difficulty abandoning.

MS would be much better off keeping the focus on their competitors and forgetting their own delusions of inventiveness and creativity.

Re:Oh, who cares about quality?

[The End Of Days]

Haters gotta hate.

Re:Capitalization

[gstoddart]

The difference is, the words "checkers" and "chess" do not have any other meanings in the English language besides the games, so there is no ambiguity.

Oh? Really

Both words have more than one meaning in English. You should stop making random assertions like that.

9x9 only ?

[RockDoctor]

From what few of the links in TFA work from this location, it looks like this is a toy that only plays 9x9 games.

This isn't impressive. 5x5 was solved (as in - optimal play has been mapped for the entire gamespace) around a decade ago. I wouldn't be surprised if 7x7 was also near to being solved by now (it's a mere 7.5 times as hard, probably) and I wouldn't be surprised to hear of 9x9 being solved while I'm still hearing with my ears instead of a machine. (Given the state of my ears, this is more challenging than it sounds. Pardon?)

But yeah - it's another competitor in the Computer Go stakes. It's unlikely to hurt the game. It may even help progress the art of Computer Go.

C++/CLI /clr:safe != C++

[tepples]

it's a lot easier to do it if you start with the XNA framework (with the .NET language of your choice, possibly even C++).

Ordinarily, when porting a game, one would start with a game that has been designed with proper separation of model and view and writing a graphics engine as a new view. For example, one could start with a Windows or Linux game written in standard C++ and add an Objective-C view for Mac OS X or iOS and a Java view for Android. But XNA doesn't support standard C++ because standard C++ doesn't compile to 100% pure verifiably type-safe IL. C++/CLI with /clr:safe does, but this language isn't standard C++: it uses an incompatible syntax for pointers and arrays, and as I understand it, porting a game written in standard C++ to XNA would involve a line-by-line rewrite of both the model and view.

The and proper nouns

[tepples]

Plenty of proper names are used with "the": The Czech Republic. The People's Republic of China. The New York Times. The Lord of the Rings.

Re:The and proper nouns

[adamdoyle]

Plenty of proper names are used with "the": The Czech Republic. The People's Republic of China. The New York Times. The Lord of the Rings.

What we have here is a perfect example of the inverse fallacy. I said p -> q (read: p implies q) and the quote above tries to suggest I'm wrong because q -/> P (read: q doesn't imply p).

I stated that the absence of "the" implies that the noun that follows is a proper noun. I didn't say that a proper noun implies the absence of a preceding "the."

Now granted, I still may be wrong in my original statement (as I'm not an English major), but the proof above is faulty.

Names of sports that likewise lack capitals

[tepples]

I stated that the absence of "the" implies that the noun that follows is a proper noun.

Thank you for clarifying. Your example of "the United States" confused the issue, making me think it was intended as a biconditional. But I have plenty of counterexamples to this statement as well, such as the name of every sport invented prior to 1923: football, cricket, baseball, basketball, ice hockey, etc. I imagine that checkers, chess, and go fall under the same rule as *ball.

Re:Names of sports that likewise lack capitals

[adamdoyle]

Yeah I guess I didn't really make it clear that I meant it in only the one direction.

I don't think it would bother me for any of the "-balls" or other examples to be capitalized. I, personally, would refrain from doing so but I don't think I would have a problem with someone else doing it. It's certainly an interesting question. I think I may start a question on english.stackexchange.com and see if I can find something more definitive. I think the problem here is the loose definition of a proper noun.

Re:Names of sports that likewise lack capitals

[adamdoyle]

http://english.stackexchange.com/questions/8126/is-the-game-go-a-proper-noun-what-about-checkers-or-chess