The Game Of Go: A Programmer's Perspective
needforair.com
needforair.com
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.
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 !
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:
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.
i.e. I guess I'm just asking if it really is a heuristic.
When it's expanding the search tree, every node expansion is arrived at "intelligently". It starts at the root node, and at each branching, asking itself: which following move is the best mixture of good (based on MC games I've played on the leaf nodes of its children) and unknown (ie I haven't explored that branch very much yet). It does that at every node until the leaf, where it expands a node with the MC-simulator (and then propagates the result up the tree). So unlike some other tree-search algorithms, it isn't cobbled by having to expand all paths to a certain depth before exploring a particular sequence deeper. The result literally looks like a tree: some branches are really tall, maybe 18 moves deep, while others are really short. Even though the "heuristic" is MC, I don't like calling it brute force, because it uses the results of those MC games so well.
I wondered whether those (relatively) sparse "tracer bullets" actually find whole "good" sections of the tree - or whether it's just the specific leaf nodes it found that were good. The answer is that, since it's being used to guide exploration, it must be good - there'd be no point using it as a heuristic otherwise. So, the existence of a win in a region of the tree is a partial predictor of other wins in that region.
I read up on the rules of Go after asking, and it makes sense: once you own some territory, you'll tend to keep it - so that if a sequence of moves leads to a win, all the prefixes of those moves will also be strong positions along the way.
So it's not brute force, but a predictive heuristic. Still kinda surprising that it works well. :-)
The worst were ideas that made it better against his former self but worse against human players (it happened !)
Change makes it harder for programming, not just that you have to keep relearning, but new technologies change the tradeoffs (e.g. plan vs. hack; performance vs. dev time). The rule of thumb shifts over time. Perhaps we'll develop a meta-rule of thumb...
Go is a vivid metaphor. Other disciplines have traditions/conventions/practices that are taken on faith, and aren't even noticed, let alone questioned or "proven" - because they can't be, without a sufficiently complete formal model of their world. Personally, I've found agile-like pragmatic conventions work well: focus on specific concrete things that are clearly needed (YAGNI); start before you are ready, it will become clear as you go along.
The department at Middlebury was small, but I doubt that I could have received a better CS education elsewhere. The opportunity to do one-on-one interesting research so early in my college career was invaluable. All three semesters were Go-related, but I didn't focus on the same thing during each.
The first summer was spent scoping the lay of the land. Reading the papers, implementing naive "improvements", and a lot of testing. Our best result was achieved by implementing someone else's we'd read in a paper. It was a humbling experience.
The second semester started with finding ways to visualize the algorithm in action. Since the improvements were so nonintuitive I felt I had to find a better way to understand how it worked and what my changes were doing. Easier said than done.
The third semester was more varied. I did more testing and playing with parameters. I also ported a version to the iPhone (we wanted to be the first and best on there- this was before ios 2 was released). Then my professor and I started a company that was initially related to Go and iPhones but later pivoted substantially several times.
I'm very thankful for the opportunities I had at Middlebury and the chance to work with Tim Huang.
http://blog.printf.net/articles/2012/02/23/computers-are-ver...
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!
http://gogameguru.com/zen-computer-go-program-beats-takemiya...
Not the kind of blitz people play on KGS, at least.
Compared to ~40 in a chess game would be 2 min per side / 20 moves = 10 seconds a move. (http://www.chessgames.com/chessstats.html)
https://en.wikipedia.org/wiki/Byoyomi
After the 25 is up, each player can make as many moves in 30 seconds as they'd like, the 5 means that they can overstep that bound 5 times (by 30 second increments).
I urge anyone to try it.
Any players well versed in the two games care to expound on any key differences in terms of strategy/balance between the two?
- 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.
- 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.
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=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.
I do that too, but you have a lot of room to back out before your one mistake becomes a losing mistake. If I neglect a group inappropriately, and then make it heavy, and then try desperately to defend it, and eventually fail to survive with no compensation, that's a lot of mistakes; and I usually could have chosen to stop and cut my losses for quite a while before it came fatal.
In chess, you can have long sequences in the midgame and endgame when the game is on a fine tactical balance, and one not-obviously-awful, ill-considered move can either put you in an immediately resignable state or make you spend the rest of the game fighting on the brink of defeat, trying to draw. And that's not really a style of play you can opt out of if your opponent chooses it.
I think you mean, at an amateur level, it's hard to see the critical, irrecoverable mistakes that you and your opponent make ;)
That is exactly the reason that I think go (1) may be solved before chess is solved.
For go, there are some results that give hope that an all encompassing theory exists. For chess, the best we have are results of exhaustive searches of relatively simple situations and a bunch of heuristics. It is true that, together, those have led to spectacular results, but I do not think they will lead to a proof about who wins chess.
(1) to be exact: Mathematical go, as defined in http://www.amazon.com/Mathematical-Go-Chilling-Gets-Point/dp.... ko rules can have variations, and there are variations in how to count points at the end of a game. Both may affect only a tiny fraction of games, but a alpha-beta search may need only one path that is a win under ruleset A and a loss under ruleset B to change the outcome of a game.
You must not have seen me play :-p
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.
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.
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.
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).
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.
There's only one king, but both sides have 15 additional pieces. One extra pawn is often enough to win, and in the majority of games between competent players one side resigns long before an actual checkmate is on the horizon.
If you want to exchange off the pieces and make a draw, you can. If you're only interested in playing surprising/paradoxical/beautiful moves, so be it.
In go, regardless of the handicap, or whether you want to win by more or lose by less, the objective is still to surround more space than your opponent.
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.h...
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.
There is also the balance between keeping your groups strong and claiming a lot of territory.
I find it similar to what I learned from practicing softer martial arts: the person that becomes tense/rigid loses.
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.