14 ms·

The Game Of Go: A Programmer's Perspective

146 points by louischatriot 15y ago

dethstarr 15y ago
I love the game of "Go" -- it's so strategic and it's particularly difficult when you're playing against a human. The mobile app I have for it is okay, but not great, probably due to the issues regarding algorithmic complexity. In fact, I like it a bit more than chess. I urge anyone to try it.
- GuiA 15y ago
  One of my best friends is extremely well ranked at chess (his highest ELO was ~2200, he was in France's top 20 of his age group when we were in high school), and has a marked disdain for go. Any players well versed in the two games care to expound on any key differences in terms of strategy/balance between the two?
  - louischatriot 15y ago
    The key difference is the philosophy behind both games. In Chess, the goal is to capture the king, destroying his army in the process. In Go, the goal is to build a territory, destroying is not necessary (smany games finish with very few catpures). I also like Chess, but I find this "building" philosophy fascinating.
    - karamazov 15y ago
      There have been analyses of western and eastern warfare strategies that hypothesize westerners use chess-like strategies (frontal assault), while easterners typically use go-like strategies (surrounding the enemy).
      - mquander 15y ago
        As a first impression, that seems pretty specious to me. I wouldn't at all describe frontal assault as being a normal chess strategy -- the most common would probably be the idea of a multi-pronged attack where your opponent cannot simultaneously defend everything, which is an equally fundamental strategy in Go, at a deeper level than "surrounding."
        hosh 15y ago
        It's less a difference of Western and Eastern and more of a difference between Clausewitz and Sun Tzu. Clausewitz was all about maneuvering the opposing army into a decisive battle (capture the king), and although you can use clever tactics, it is ultimately a war of attrition favoring the strong (such as industrialized nation-states). Sun Tzu was about using ambiguity so that the weaker opponent has a chance of prevailing over a stronger opponent (asymmetric warfare, or "cheating"). There have been Western military commanders that have used a distinctively Sun Tzu flavor. Even if you played chess with a multi-pronged attack, you're still ultimately gunning for the king. Your objective is absolute, and each side knows this. Your objectives within the course of a Go game is more fluid and ambiguous.
        asynchrony 15y ago
        There is fluidity to objectives during a game of chess between strong players. For example: inflicting/preventing weaknesses, seeking/avoiding favorable exchanges, occupying/closing important lines. Then all such long-term considerations suddenly become irrelevant when the game descends into a tactical melee. At any rate, I don't see how the objective of chess (checkmating the opposing king) is any more absolute or less ambiguous than the objective of go (surrounding more space than your opponent).
        hosh 15y ago
        Depends on how you want to play. Some people try to win by a certain amount of points. Some people try to lose by a certain amount of points. Some teachers move in a way to call attention to certain shapes or tactical sequences. Sometimes you just want to stick to beautiful moves. When you throw in handicap stones, komi, and reverse komi, how much you win or lose by is arbitrary. You can win by 0.5 points, but that's largely dependent on komi you agreed to. The losing player still has half of the board. All fluid objectives during a game of chess between strong players are still subordinate to the ultimate objective: capture the king. There's only one king on each side, so there is not much give. There are 361 empty space to choose from in Go.
      - njharman 15y ago
        Strategies have evolved massively over time and with technology.
  - RBerenguel 15y ago
    My main analogy when talking to chess players: chess is a battle and go is a war. I played chess, now only go. My main problem was the arbitrary set of rules in chess: go is more like axiomatic. Given two players, black and white pieces and a board, it's almost "natural" to develop it
  - mquander 15y ago
    I'm of moderate strength at both, being a chess expert and a 1d-1k KGS. Some brief comments: - Go makes me confront my fear of heuristics. My unconscious ability to pattern match the right moves is always ahead of my ability to understand why they are right, although I try to catch it up by thinking really hard. It's a unique experience. - Both the rules and strategy of Go feel more elegant in the mathematical sense of being a composition of simple ideas, which I like. Chess feels more like a set of arbitrary pieces of knowledge. - The handicap system in Go is an objectively awesome way to have players of different strengths play competitively. In chess, you can almost never play with someone 400 rating points your inferior and have it be a satisfyingly competitive game -- giving piece or pawn odds changes the game completely. In Go, if you give someone four stones, it feels like you're still playing Go. - When watching strong players, I like the fact that there aren't draws in Go. It makes the game dramatic until the end. - I like chess problems better than Go problems, and I personally find a level of beauty and variety in amazing chess brilliancies which surpasses what I perceive in great Go moves. I don't know of a Go equivalent to http://timkr.home.xs4all.nl/chess/chess.html http://timkr.home.xs4all.nl/chess/chess.html. - At least at an amateur level, it's harder to make a critical, near-irrecoverable mistake in Go -- there's not as much of a snowball effect making an advantage into a bigger advantage. That makes it feel less stressful for me when playing long games.
    - louischatriot 15y ago
      I especially agree with your first point. In Go, I often play moves just because I find them beautiful. Even in life-or-death situations, I begin by finding the "most beautiful" moves :)
    - docgnome 15y ago
      "it's harder to make a critical, near-irrecoverable mistake in Go" You must not have seen me play :-p
    - dulse 15y ago
      Go problems feel super compelling to me. Typical problems can be boring "counting" exercises, but I find it hard to beat something like the ear reddening move: http://senseis.xmp.net/?EarReddeningMove http://senseis.xmp.net/?EarReddeningMove There is a great series on youtube on fantastic moves from professional games with commentary in English: http://www.youtube.com/watch?v=CJ9Oexs59CE&feature=relmfu http://www.youtube.com/watch?v=CJ9Oexs59CE&feature=relmf... They are really beautiful in part because they become tesuji through a confluence of factors that reverberate across the entire board. It can be hard to see for amateurs (including me) but once you give them the right context and insight, they become startlingly brilliant. Also, it's interesting you find it hard to make a critical mistake in Go - this feels very common to me. For example, a decision like deciding to defend a group instead of sacrificing it (which comes up all the time) often snowballs really quickly.
  - caoxuwen 15y ago
    I feel in chess it's about concentrating your power with the goal of total elimination of the other side in one battle. With go, there are multiple battles where you make trade-offs - short term vs. long term, territory vs. influence. Focusing on solely one part of the equation is almost always not optimal, yet you can still develop your unique style of play. You would often feel it's not a zero-sum game where both sides are taking what they want(though in the end only one can win). Also with the huge branching factor, go feels more dynamic and fluid.
  - docgnome 15y ago
    I'm curious, what is it that your friend doesn't like?
  - asynchrony 15y ago
    I'm a fairly strong chess player (FIDE ELO 2325) and a much weaker go player (best rank around 5 kyu on internet sites). Chess is a very tactical game. There are many long term strategic concepts, but victory frequently goes to the alert tactical opportunist (and chess engines are the ultimate alert opportunists). Also, to win a chess game, you ultimately have to attack and destroy some part of your opponent's position. In go you just need one more point of space than your opponent -- there's no requirement to resort to violence at all. One thing I definitely prefer about go is the openings. In chess they've been so heavily analyzed that games between professionals frequently go 20+ moves before an original move is played. In go there seems to be an almost limitless number of reasonable approaches to the opening. I guess there just aren't as many good moves available in the chess openings. I'm not sure why your friend would have disdain for go. I think they're both fascinating games of strategy, certainly more engrossing than any RTS I've ever played.
  - bluecalm 15y ago
    I am 2300ELO in chess and about 4-5k in go (maybe a bit weaker now). My impression is that chess is almost purely tactical/close fight game while go is much more strategic/feel game. Of course that could be because I am much stronger in chess and go overwhelms me a bit. I like go more in general, it has aesthetic appeal which I like. The only drawback is that even blitz games are quite long while in chess you can fire up few 1 0 (1minute per game no increment) on internet in no-time :)
z0r 15y ago
MoGo beats 5d KGS now? Kind of depressing if true, this day felt much longer off half a decade ago... But I won't believe it until I see a few of these games as they are played myself :)
- seigenblues 15y ago
  MoGo is not 5d KGS -- there are some bots that are 4d/5d KGS, using the approach given in the article. The two best (that I am aware of) are Zen19 -- closed source -- and pachi -- available here: http://pachi.or.cz/ http://pachi.or.cz/ The author of Pachi has a paper detailing the major algorithm advancement beyond Monte-Carlo game simulations, which is sharing information across simulations in a way that is totally nonintuitive to me. For me, a 3d/4d KGS go player, this is all very interesting stuff!
- mquander 15y ago
  Zen beat Takemiya Masaki a few weeks ago in a non-blitz two-game match at five and four stones. It didn't even use an excessive amount of hardware, just a couple of boxes: http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/ http://gogameguru.com/zen-computer-go-program-beats-takemiya...
  - fuzzythinker 15y ago
    Actually, the author considers them to be a blitz game.. http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/#comment-3856 http://gogameguru.com/zen-computer-go-program-beats-takemiya...
    - mquander 15y ago
      Fair enough. I'd call it a "quick" game, analogous to quick games in chess. It was 25 minutes of main time and 5x30 sec byo-yomi periods, IIRC. Not the kind of blitz people play on KGS, at least.
      - Retric 15y ago
codesuela 15y ago
am I the only one who thought the title is a pun on Game of thrones and Go as in Go (programming language)?
- agscala 15y ago
  I didn't make that connection. But even if that was the intention, who cares?
caoxuwen 15y ago
Go is a fantastic game. It's also a great analogy of the eastern philosophy with its emphasis on balance and long-term strategic vision.
- louischatriot 15y ago
  That's what I really like about Go. You always need to balance short-term greed and captures against vision. There is also the balance between keeping your groups strong and claiming a lot of territory.
  - muloka 15y ago
    Exactly. I generally find that when I am over zealous when playing I tend to lose. I find it similar to what I learned from practicing softer martial arts: the person that becomes tense/rigid loses.
    - hosh 15y ago
      Yeah. Cheng Man-ch'ing. "Invest in loss."
tel 15y ago
That's a really fascinating peek at the methods used! I love that they use multi-armed bandit models and that they built a heuristic that wins partly because it's highly parallelizable. This is how you beat a human mind.
cjbprime 15y ago
For what it's worth, I wrote a similar post recently that some might find interesting: http://blog.printf.net/articles/2012/02/23/computers-are-very-good-at-the-game-of-go http://blog.printf.net/articles/2012/02/23/computers-are-ver...
- ScottBurson 15y ago
  Good post, and I agree: it is a little sad to see the game cracked in a way that sheds so little light on human cognition.
bevan 15y ago
I worked on UCT-based (one-arm bandit algorithm) go players for 3 semesters. It was truly a great, if often frustrating, experience. It's a tough problem to get your head around. Sure, the premise makes sense- that the Monte Carlo heuristic plus the UCT tree-exploration algorithm balances promising nodes with uncertain ones to intelligently expand the tree. But tweaking that algorithm usually hurt performance more than helped, and the tweaks that did improve gameplay were non-intuitive. One semester our goal was to improve the random-playout generator to play slightly more human-like games. It turns out that almost any play enhancements made in the Monte Carlo simulator crippled performance (for instance: instead of playing randomly, search the board for an opportunity to capture the opponent). The best result we had was achieved by applying the capture-if-possible heuristic on only two positions per random move (ex: at the beginning of the MC-simulator's move, pick two positions randomly- if moving in either one captures the opponent, do it). Applying that heuristic on any more than 2 positions per move made the random games play out more slowly than it was worth. Needless to say, a lot of time was spent testing our tweaks (which itself was quite time consuming). It was frustrating to see our initial seemingly sensible tweaks cripple performance, and it definitely took some time to calibrate ourselves to the problem at hand. But I probably learned more about programming while working on Go than in any other 3-semester span. Peter Drake's Orego player is a great starting point for exploring the UCT algorithm (Peter Drake wrote a popular Java textbook you may have used in undergrad). I highly encourage people interested in AI to check it out: https://sites.google.com/site/drpeterdrake/research/orego https://sites.google.com/site/drpeterdrake/research/orego
- Alex3917 15y ago
  I'm confused as to why you would want to capture. My understanding is that pro players try to avoid having to actually capture unless necessary. (I.e. if they are winning a capturing race then the right move is always to tenuki unless the other player does something that demands a response.)
  - bevan 15y ago
    Real-life tactics unfortunately don't make for good heuristics in the Monte Carlo simulator. Our goal was to improve overall gameplay by making the Monte Carlo simulator play slightly more realistically than random. Keep in mind that when the Monte Carlo simulator plays completely random games, it still does pretty good. I believe it's on par with GnuGo, a good pre-UCT go player, on a 9x9 board on a modern quad-core. Whether a heuristic applied within the MC-simulator generates sample games that better assess the strength of a move is a tricky question to ponder. But it seems reasonable that most non-random tactics, however simple, would accomplish that (such as proximity- or capture-based tactics). The reason that good real-life tactics do not correlate with improved gameplay when implemented in MC-simulators is because the logic required for even simple tactics can reduce the number of semi-random games the computer can play by several orders of magnitude. Picking a random move is extremely quick (choosing a number with a Mersenne Twister is faster than adding two numbers- compare that to the operations required to determine how many pieces surround a given position). That's partly why very simple heuristics like capture-if-possible are only effective if they're applied on a few (2, in our case) open board positions per move in a MC-simulated game. So its just slightly non-random. Anyway I hope that made sense. It's a weird problem to think about at first, but it's actually really fun to play around with. I recommend checking out Drake's implementation.
gcp 15y ago
This article also illustrates how important it is as a researcher to publicize yourself well. Mogo really only had a very small part in the breakthroughs that were made. Yet it is heralded in every such article as the bot that made it all happen. For those that are curious what happened, there are some seminal references: Monte Carlo Go. Bernd Brügmann - This introduced the basic idea. Monte-Carlo Go Developments. Bruno Bouzy - Bouzy is the guy that kept hammering at the original Brügmann idea while everyone else thought it was a dead end. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Remi Coulom - This was really the breakthrough paper, that showed how to combine Monte Carlo simulations with a tree search. Was also the first MC bot to win the gold medals. Mogo replaced the ad-hock operators in the last paper with an algorithm with more mathematical grounding (UCT). Even though the name is now very well known, most top Go programs, including the last research published about Mogo, actually already dropped the idea and went back to more ad-hock formulas again. The article also makes the common mistake that the position is evaluated using random games. Calling them random is quite misleading. It seems to be necessary to include some knowledge in them, but too much knowledge hurts the strength again - regardless of any speed impact. It's an open problem to fundamentally understand exactly what kind of knowledge helps the program to actually play stronger. What happened in Go is also a nice illustration that if you want to make a computer good at an AI task, the key is finding an algorithm that approximately-linearly improves with the computing power you throw at it. If you do this, you crack the wall. Algorithmic and hardware improvements will do the rest in the years to come.
- llimllib 15y ago
  Just for fun, I wrapped those three papers and a Gelly UCT paper up in a zip file, in case anybody wants to read them: http://dl.dropbox.com/u/25636/go_papers.zip http://dl.dropbox.com/u/25636/go_papers.zip
- louischatriot 15y ago
  I explained the key ideas behind Mogo and not another program because it is the one I worked on, and know well. It is true though that I could also have mentionned Coulom's Crazy Stone. About your second point - there is indeed some expert knowledge during the pseudo random games (cf the "use of a little expert knowledge" bullet point), but I wanted to insist on the idea of using almost-random-games to evaluate a position, because I found it so unexpected at the time !
amalag 15y ago
The fact that computers have such a hard time is a reason it is worth playing and makes Go attractive. The fact that chess can be reduced just makes chess unappealing.
- fusiongyro 15y ago
  This isn't the first time I've seen this sentiment about Go from (I presume) a programmer, and I have always found it puzzling. It seems like the opposite of the Seneca quote, "Men love their country, not because it is great, but because it is their own." Loving Go because it is hard for a computer seems like a scornful reason to love it compared to loving it because it is Go. Like loving your wife because she is beautiful, it is intrinsically temporary. There are better places to search for mystical appreciation for human cognition, specifically places that lack definitions like starting, ending and success. What I find attractive about Go is that it emphasizes subtle influences over outright attacks. Everything is vague, slowly coming into focus. You feel more like you're trying to secretly drive a Ouija board than trying to eliminate the opponent. I seldom feel like, this is the move that ruined my game, whereas with chess I can almost always immediately identify the move that costs me the game. Then again, I am terrible at Go and I hardly ever play, but I have a sense, possibly illegitimate, that getting better at Go would make my whole life better, whereas getting better at chess would simply make me a better conniver, and I'm already pretty good.
  - amalag 15y ago
    It is not a scornful sentiment, it is the same appreciation that you are referring to. Just like computing 2+2 is not the same as theoretical mathematics and creativity in mathematics, finding a game that is not computer reducible is an aspect of beauty in the game that is not present in chess because it is reducible. edit: seems that go programs are quite advanced and may overtake human players as well, though the methods are a bit different from chess
- deleted 15y ago
  [deleted]
- asynchrony 15y ago
adi92 15y ago
I learnt Go by watching this anime on Netflix called 'Hikaru no Go'. Its pretty kiddish, but fun, and really inspires you to learn the game!
thirdhaf 15y ago
I lost a large bet in 2010 on being able to create a computer program capable of beating my roommate at Go. UCT was my go-to solution to this problem but my opponent was able to beat my creation on a 13x13 board since he spent every free waking moment playing Go against a commercial app on the iPhone. My UCT-based creation ended up beating me but losing against someone who trained intensively for six weeks.
losvedir 15y ago
This seems like a really interesting area of research. As far as I can tell from my (limited) background on chess/go/etc algorithms, they seem to include lots of hard-coded scenarios (like a bunch of chess openings) and brute force searching. Are there any teams working on more, I don't know, human-seeming algorithms? Everyone seems to agree that humans are good at these games from pattern recognition on a large corpus of game experiences. I'm out of my element here and realize I'm approaching "Even though I don't understand what you do, I'm going to assume it's easy for you to implement my suggestion" territory, but what if you encoded positions as general shapes rather than stone-by-stone? What if you played through lots and lots of games and built up Bayesian probability models of how likely certain combinations of shapes lead to victories? I mean, when a human go player looks at a board position and sizes it up what are they doing? I guess if we aren't particularly good at computer vision and understanding how the human mind works yet, then there are hard problems here, but it seems like a neat sort of interdisciplinary approach. edit: It looks like NeuroGo[1] linked to from an article in a different comment is more akin to what I'm thinking. It's just not very good.... ha. [1] http://webdocs.cs.ualberta.ca/~emarkus/neurogo/neurogo1996.html http://webdocs.cs.ualberta.ca/~emarkus/neurogo/neurogo1996.h...
- exDM69 15y ago
  > As far as I can tell from my (limited) background on chess/go/etc algorithms, they seem to include lots of hard-coded scenarios (like a bunch of chess openings) and brute force searching. When playing chess at an advanced level, you need to know a fair number of different openings (that even have names). Chess AI programs have a huge library of openings, endings and other game situations that are evaluated. In contrast, Go does not have a "library" of openings the same way chess does. There are simply too many ways a game can progress. However, in Go, there are many "micro patterns" that repeat over and over again, and you have to learn some of these even at a beginner level. There are numerous recurring formations, like the "Ladder", where one player inevitably loses and it should be recognized after 3-5 stones are in a specific form. So Go has these patterns that recur, but they aren't as clear and simple as in chess. While a ladder can be recognized after just a few stones, the outcome may depend on a stone on the other side of the board, that may be have been there for 100 turns. This is what makes pattern recognition tricky for Go AI.

146 points by louischatriot 15y ago

I love the game of "Go" -- it's so strategic and it's particularly difficult when you're playing against a human. The mobile app I have for it is okay, but not great, probably due to the issues regarding algorithmic complexity. In fact, I like it a bit more than chess. I urge anyone to try it.

GuiA 15y ago
One of my best friends is extremely well ranked at chess (his highest ELO was ~2200, he was in France's top 20 of his age group when we were in high school), and has a marked disdain for go. Any players well versed in the two games care to expound on any key differences in terms of strategy/balance between the two?
- louischatriot 15y ago
  The key difference is the philosophy behind both games. In Chess, the goal is to capture the king, destroying his army in the process. In Go, the goal is to build a territory, destroying is not necessary (smany games finish with very few catpures). I also like Chess, but I find this "building" philosophy fascinating.
  - karamazov 15y ago
    There have been analyses of western and eastern warfare strategies that hypothesize westerners use chess-like strategies (frontal assault), while easterners typically use go-like strategies (surrounding the enemy).
    - mquander 15y ago
      As a first impression, that seems pretty specious to me. I wouldn't at all describe frontal assault as being a normal chess strategy -- the most common would probably be the idea of a multi-pronged attack where your opponent cannot simultaneously defend everything, which is an equally fundamental strategy in Go, at a deeper level than "surrounding."
      - hosh 15y ago
        It's less a difference of Western and Eastern and more of a difference between Clausewitz and Sun Tzu. Clausewitz was all about maneuvering the opposing army into a decisive battle (capture the king), and although you can use clever tactics, it is ultimately a war of attrition favoring the strong (such as industrialized nation-states). Sun Tzu was about using ambiguity so that the weaker opponent has a chance of prevailing over a stronger opponent (asymmetric warfare, or "cheating"). There have been Western military commanders that have used a distinctively Sun Tzu flavor. Even if you played chess with a multi-pronged attack, you're still ultimately gunning for the king. Your objective is absolute, and each side knows this. Your objectives within the course of a Go game is more fluid and ambiguous.
        asynchrony 15y ago
        There is fluidity to objectives during a game of chess between strong players. For example: inflicting/preventing weaknesses, seeking/avoiding favorable exchanges, occupying/closing important lines. Then all such long-term considerations suddenly become irrelevant when the game descends into a tactical melee. At any rate, I don't see how the objective of chess (checkmating the opposing king) is any more absolute or less ambiguous than the objective of go (surrounding more space than your opponent).
        hosh 15y ago
        Depends on how you want to play. Some people try to win by a certain amount of points. Some people try to lose by a certain amount of points. Some teachers move in a way to call attention to certain shapes or tactical sequences. Sometimes you just want to stick to beautiful moves. When you throw in handicap stones, komi, and reverse komi, how much you win or lose by is arbitrary. You can win by 0.5 points, but that's largely dependent on komi you agreed to. The losing player still has half of the board. All fluid objectives during a game of chess between strong players are still subordinate to the ultimate objective: capture the king. There's only one king on each side, so there is not much give. There are 361 empty space to choose from in Go.
    - njharman 15y ago
      Strategies have evolved massively over time and with technology.
- RBerenguel 15y ago
  My main analogy when talking to chess players: chess is a battle and go is a war. I played chess, now only go. My main problem was the arbitrary set of rules in chess: go is more like axiomatic. Given two players, black and white pieces and a board, it's almost "natural" to develop it
- mquander 15y ago
  I'm of moderate strength at both, being a chess expert and a 1d-1k KGS. Some brief comments: - Go makes me confront my fear of heuristics. My unconscious ability to pattern match the right moves is always ahead of my ability to understand why they are right, although I try to catch it up by thinking really hard. It's a unique experience. - Both the rules and strategy of Go feel more elegant in the mathematical sense of being a composition of simple ideas, which I like. Chess feels more like a set of arbitrary pieces of knowledge. - The handicap system in Go is an objectively awesome way to have players of different strengths play competitively. In chess, you can almost never play with someone 400 rating points your inferior and have it be a satisfyingly competitive game -- giving piece or pawn odds changes the game completely. In Go, if you give someone four stones, it feels like you're still playing Go. - When watching strong players, I like the fact that there aren't draws in Go. It makes the game dramatic until the end. - I like chess problems better than Go problems, and I personally find a level of beauty and variety in amazing chess brilliancies which surpasses what I perceive in great Go moves. I don't know of a Go equivalent to http://timkr.home.xs4all.nl/chess/chess.html http://timkr.home.xs4all.nl/chess/chess.html. - At least at an amateur level, it's harder to make a critical, near-irrecoverable mistake in Go -- there's not as much of a snowball effect making an advantage into a bigger advantage. That makes it feel less stressful for me when playing long games.
  - louischatriot 15y ago
    I especially agree with your first point. In Go, I often play moves just because I find them beautiful. Even in life-or-death situations, I begin by finding the "most beautiful" moves :)
  - docgnome 15y ago
    "it's harder to make a critical, near-irrecoverable mistake in Go" You must not have seen me play :-p
  - dulse 15y ago
    Go problems feel super compelling to me. Typical problems can be boring "counting" exercises, but I find it hard to beat something like the ear reddening move: http://senseis.xmp.net/?EarReddeningMove http://senseis.xmp.net/?EarReddeningMove There is a great series on youtube on fantastic moves from professional games with commentary in English: http://www.youtube.com/watch?v=CJ9Oexs59CE&feature=relmfu http://www.youtube.com/watch?v=CJ9Oexs59CE&feature=relmf... They are really beautiful in part because they become tesuji through a confluence of factors that reverberate across the entire board. It can be hard to see for amateurs (including me) but once you give them the right context and insight, they become startlingly brilliant. Also, it's interesting you find it hard to make a critical mistake in Go - this feels very common to me. For example, a decision like deciding to defend a group instead of sacrificing it (which comes up all the time) often snowballs really quickly.
- caoxuwen 15y ago
  I feel in chess it's about concentrating your power with the goal of total elimination of the other side in one battle. With go, there are multiple battles where you make trade-offs - short term vs. long term, territory vs. influence. Focusing on solely one part of the equation is almost always not optimal, yet you can still develop your unique style of play. You would often feel it's not a zero-sum game where both sides are taking what they want(though in the end only one can win). Also with the huge branching factor, go feels more dynamic and fluid.
- docgnome 15y ago
  I'm curious, what is it that your friend doesn't like?
- asynchrony 15y ago
  I'm a fairly strong chess player (FIDE ELO 2325) and a much weaker go player (best rank around 5 kyu on internet sites). Chess is a very tactical game. There are many long term strategic concepts, but victory frequently goes to the alert tactical opportunist (and chess engines are the ultimate alert opportunists). Also, to win a chess game, you ultimately have to attack and destroy some part of your opponent's position. In go you just need one more point of space than your opponent -- there's no requirement to resort to violence at all. One thing I definitely prefer about go is the openings. In chess they've been so heavily analyzed that games between professionals frequently go 20+ moves before an original move is played. In go there seems to be an almost limitless number of reasonable approaches to the opening. I guess there just aren't as many good moves available in the chess openings. I'm not sure why your friend would have disdain for go. I think they're both fascinating games of strategy, certainly more engrossing than any RTS I've ever played.
- bluecalm 15y ago
  I am 2300ELO in chess and about 4-5k in go (maybe a bit weaker now). My impression is that chess is almost purely tactical/close fight game while go is much more strategic/feel game. Of course that could be because I am much stronger in chess and go overwhelms me a bit. I like go more in general, it has aesthetic appeal which I like. The only drawback is that even blitz games are quite long while in chess you can fire up few 1 0 (1minute per game no increment) on internet in no-time :)

z0r 15y ago

MoGo beats 5d KGS now? Kind of depressing if true, this day felt much longer off half a decade ago... But I won't believe it until I see a few of these games as they are played myself :)

seigenblues 15y ago
MoGo is not 5d KGS -- there are some bots that are 4d/5d KGS, using the approach given in the article. The two best (that I am aware of) are Zen19 -- closed source -- and pachi -- available here: http://pachi.or.cz/ http://pachi.or.cz/ The author of Pachi has a paper detailing the major algorithm advancement beyond Monte-Carlo game simulations, which is sharing information across simulations in a way that is totally nonintuitive to me. For me, a 3d/4d KGS go player, this is all very interesting stuff!
mquander 15y ago
Zen beat Takemiya Masaki a few weeks ago in a non-blitz two-game match at five and four stones. It didn't even use an excessive amount of hardware, just a couple of boxes: http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/ http://gogameguru.com/zen-computer-go-program-beats-takemiya...
- fuzzythinker 15y ago
  Actually, the author considers them to be a blitz game.. http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/#comment-3856 http://gogameguru.com/zen-computer-go-program-beats-takemiya...
  - mquander 15y ago
    Fair enough. I'd call it a "quick" game, analogous to quick games in chess. It was 25 minutes of main time and 5x30 sec byo-yomi periods, IIRC. Not the kind of blitz people play on KGS, at least.
    - Retric 15y ago

codesuela 15y ago

am I the only one who thought the title is a pun on Game of thrones and Go as in Go (programming language)?

agscala 15y ago
I didn't make that connection. But even if that was the intention, who cares?

caoxuwen 15y ago

Go is a fantastic game. It's also a great analogy of the eastern philosophy with its emphasis on balance and long-term strategic vision.

louischatriot 15y ago
That's what I really like about Go. You always need to balance short-term greed and captures against vision. There is also the balance between keeping your groups strong and claiming a lot of territory.
- muloka 15y ago
  Exactly. I generally find that when I am over zealous when playing I tend to lose. I find it similar to what I learned from practicing softer martial arts: the person that becomes tense/rigid loses.
  - hosh 15y ago
    Yeah. Cheng Man-ch'ing. "Invest in loss."

tel 15y ago

That's a really fascinating peek at the methods used! I love that they use multi-armed bandit models and that they built a heuristic that wins partly because it's highly parallelizable. This is how you beat a human mind.

cjbprime 15y ago

For what it's worth, I wrote a similar post recently that some might find interesting: http://blog.printf.net/articles/2012/02/23/computers-are-very-good-at-the-game-of-go http://blog.printf.net/articles/2012/02/23/computers-are-ver...

ScottBurson 15y ago
Good post, and I agree: it is a little sad to see the game cracked in a way that sheds so little light on human cognition.

bevan 15y ago

I worked on UCT-based (one-arm bandit algorithm) go players for 3 semesters. It was truly a great, if often frustrating, experience. It's a tough problem to get your head around. Sure, the premise makes sense- that the Monte Carlo heuristic plus the UCT tree-exploration algorithm balances promising nodes with uncertain ones to intelligently expand the tree. But tweaking that algorithm usually hurt performance more than helped, and the tweaks that did improve gameplay were non-intuitive. One semester our goal was to improve the random-playout generator to play slightly more human-like games. It turns out that almost any play enhancements made in the Monte Carlo simulator crippled performance (for instance: instead of playing randomly, search the board for an opportunity to capture the opponent). The best result we had was achieved by applying the capture-if-possible heuristic on only two positions per random move (ex: at the beginning of the MC-simulator's move, pick two positions randomly- if moving in either one captures the opponent, do it). Applying that heuristic on any more than 2 positions per move made the random games play out more slowly than it was worth. Needless to say, a lot of time was spent testing our tweaks (which itself was quite time consuming). It was frustrating to see our initial seemingly sensible tweaks cripple performance, and it definitely took some time to calibrate ourselves to the problem at hand. But I probably learned more about programming while working on Go than in any other 3-semester span. Peter Drake's Orego player is a great starting point for exploring the UCT algorithm (Peter Drake wrote a popular Java textbook you may have used in undergrad). I highly encourage people interested in AI to check it out: https://sites.google.com/site/drpeterdrake/research/orego https://sites.google.com/site/drpeterdrake/research/orego

Alex3917 15y ago
I'm confused as to why you would want to capture. My understanding is that pro players try to avoid having to actually capture unless necessary. (I.e. if they are winning a capturing race then the right move is always to tenuki unless the other player does something that demands a response.)
- bevan 15y ago
  Real-life tactics unfortunately don't make for good heuristics in the Monte Carlo simulator. Our goal was to improve overall gameplay by making the Monte Carlo simulator play slightly more realistically than random. Keep in mind that when the Monte Carlo simulator plays completely random games, it still does pretty good. I believe it's on par with GnuGo, a good pre-UCT go player, on a 9x9 board on a modern quad-core. Whether a heuristic applied within the MC-simulator generates sample games that better assess the strength of a move is a tricky question to ponder. But it seems reasonable that most non-random tactics, however simple, would accomplish that (such as proximity- or capture-based tactics). The reason that good real-life tactics do not correlate with improved gameplay when implemented in MC-simulators is because the logic required for even simple tactics can reduce the number of semi-random games the computer can play by several orders of magnitude. Picking a random move is extremely quick (choosing a number with a Mersenne Twister is faster than adding two numbers- compare that to the operations required to determine how many pieces surround a given position). That's partly why very simple heuristics like capture-if-possible are only effective if they're applied on a few (2, in our case) open board positions per move in a MC-simulated game. So its just slightly non-random. Anyway I hope that made sense. It's a weird problem to think about at first, but it's actually really fun to play around with. I recommend checking out Drake's implementation.

gcp 15y ago

This article also illustrates how important it is as a researcher to publicize yourself well. Mogo really only had a very small part in the breakthroughs that were made. Yet it is heralded in every such article as the bot that made it all happen. For those that are curious what happened, there are some seminal references: Monte Carlo Go. Bernd Brügmann - This introduced the basic idea. Monte-Carlo Go Developments. Bruno Bouzy - Bouzy is the guy that kept hammering at the original Brügmann idea while everyone else thought it was a dead end. Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search. Remi Coulom - This was really the breakthrough paper, that showed how to combine Monte Carlo simulations with a tree search. Was also the first MC bot to win the gold medals. Mogo replaced the ad-hock operators in the last paper with an algorithm with more mathematical grounding (UCT). Even though the name is now very well known, most top Go programs, including the last research published about Mogo, actually already dropped the idea and went back to more ad-hock formulas again. The article also makes the common mistake that the position is evaluated using random games. Calling them random is quite misleading. It seems to be necessary to include some knowledge in them, but too much knowledge hurts the strength again - regardless of any speed impact. It's an open problem to fundamentally understand exactly what kind of knowledge helps the program to actually play stronger. What happened in Go is also a nice illustration that if you want to make a computer good at an AI task, the key is finding an algorithm that approximately-linearly improves with the computing power you throw at it. If you do this, you crack the wall. Algorithmic and hardware improvements will do the rest in the years to come.

llimllib 15y ago
Just for fun, I wrapped those three papers and a Gelly UCT paper up in a zip file, in case anybody wants to read them: http://dl.dropbox.com/u/25636/go_papers.zip http://dl.dropbox.com/u/25636/go_papers.zip
louischatriot 15y ago
I explained the key ideas behind Mogo and not another program because it is the one I worked on, and know well. It is true though that I could also have mentionned Coulom's Crazy Stone. About your second point - there is indeed some expert knowledge during the pseudo random games (cf the "use of a little expert knowledge" bullet point), but I wanted to insist on the idea of using almost-random-games to evaluate a position, because I found it so unexpected at the time !

amalag 15y ago

The fact that computers have such a hard time is a reason it is worth playing and makes Go attractive. The fact that chess can be reduced just makes chess unappealing.

fusiongyro 15y ago
This isn't the first time I've seen this sentiment about Go from (I presume) a programmer, and I have always found it puzzling. It seems like the opposite of the Seneca quote, "Men love their country, not because it is great, but because it is their own." Loving Go because it is hard for a computer seems like a scornful reason to love it compared to loving it because it is Go. Like loving your wife because she is beautiful, it is intrinsically temporary. There are better places to search for mystical appreciation for human cognition, specifically places that lack definitions like starting, ending and success. What I find attractive about Go is that it emphasizes subtle influences over outright attacks. Everything is vague, slowly coming into focus. You feel more like you're trying to secretly drive a Ouija board than trying to eliminate the opponent. I seldom feel like, this is the move that ruined my game, whereas with chess I can almost always immediately identify the move that costs me the game. Then again, I am terrible at Go and I hardly ever play, but I have a sense, possibly illegitimate, that getting better at Go would make my whole life better, whereas getting better at chess would simply make me a better conniver, and I'm already pretty good.
- amalag 15y ago
  It is not a scornful sentiment, it is the same appreciation that you are referring to. Just like computing 2+2 is not the same as theoretical mathematics and creativity in mathematics, finding a game that is not computer reducible is an aspect of beauty in the game that is not present in chess because it is reducible. edit: seems that go programs are quite advanced and may overtake human players as well, though the methods are a bit different from chess
deleted 15y ago
[deleted]
asynchrony 15y ago

adi92 15y ago

I learnt Go by watching this anime on Netflix called 'Hikaru no Go'. Its pretty kiddish, but fun, and really inspires you to learn the game!

thirdhaf 15y ago

I lost a large bet in 2010 on being able to create a computer program capable of beating my roommate at Go. UCT was my go-to solution to this problem but my opponent was able to beat my creation on a 13x13 board since he spent every free waking moment playing Go against a commercial app on the iPhone. My UCT-based creation ended up beating me but losing against someone who trained intensively for six weeks.

losvedir 15y ago

This seems like a really interesting area of research. As far as I can tell from my (limited) background on chess/go/etc algorithms, they seem to include lots of hard-coded scenarios (like a bunch of chess openings) and brute force searching. Are there any teams working on more, I don't know, human-seeming algorithms? Everyone seems to agree that humans are good at these games from pattern recognition on a large corpus of game experiences. I'm out of my element here and realize I'm approaching "Even though I don't understand what you do, I'm going to assume it's easy for you to implement my suggestion" territory, but what if you encoded positions as general shapes rather than stone-by-stone? What if you played through lots and lots of games and built up Bayesian probability models of how likely certain combinations of shapes lead to victories? I mean, when a human go player looks at a board position and sizes it up what are they doing? I guess if we aren't particularly good at computer vision and understanding how the human mind works yet, then there are hard problems here, but it seems like a neat sort of interdisciplinary approach. edit: It looks like NeuroGo[1] linked to from an article in a different comment is more akin to what I'm thinking. It's just not very good.... ha. [1] http://webdocs.cs.ualberta.ca/~emarkus/neurogo/neurogo1996.html http://webdocs.cs.ualberta.ca/~emarkus/neurogo/neurogo1996.h...

exDM69 15y ago
> As far as I can tell from my (limited) background on chess/go/etc algorithms, they seem to include lots of hard-coded scenarios (like a bunch of chess openings) and brute force searching. When playing chess at an advanced level, you need to know a fair number of different openings (that even have names). Chess AI programs have a huge library of openings, endings and other game situations that are evaluated. In contrast, Go does not have a "library" of openings the same way chess does. There are simply too many ways a game can progress. However, in Go, there are many "micro patterns" that repeat over and over again, and you have to learn some of these even at a beginner level. There are numerous recurring formations, like the "Ladder", where one player inevitably loses and it should be recognized after 3-5 stones are in a specific form. So Go has these patterns that recur, but they aren't as clear and simple as in chess. While a ladder can be recognized after just a few stones, the outcome may depend on a stone on the other side of the board, that may be have been there for 100 turns. This is what makes pattern recognition tricky for Go AI.