orgtheory.net

go > chess

A Wired article explains how artificial intelligence has now been able to crack the game of Go and why it’s harder than chess. From the write up:

Good opens the article by suggesting that Go is inherently superior to all other strategy games, an opinion shared by pretty much every Go player I’ve met. “There is chess in the western world, but Go is incomparably more subtle and intellectual,” says South Korean Lee Sedol, perhaps the greatest living Go player and one of a handful who make over seven figures a year in prize money. Subtlety, of course, is subjective. But the fact is that of all the world’s deterministic perfect information games — tic-tac-toe, chess, checkers, Othello, xiangqi, shogi — Go is the only one in which computers don’t stand a chance against humans.

This is not for lack of trying on the part of programmers, who have worked on Go alongside chess for the last fifty years, with substantially less success. The first chess programs were written in the early fifties, one by Turing himself. By the 1970s, they were quite good. But as late as 1962, despite the game’s popularity among programmers, only two people had succeeded at publishing Go programs, neither of which was implemented or tested against humans.

Why is Go so hard and pretty at the same time?

To understand this, think about Go in relation to chess. At the beginning of a chess game, White has twenty possible moves. After that, Black also has twenty possible moves. Once both sides have played, there are 400 possible board positions. Go, by contrast, begins with an empty board, where Black has 361 possible opening moves, one at every intersection of the 19 by 19 grid. White can follow with 360 moves. That makes for 129,960 possible board positions after just the first round of moves.

The rate at which possible positions increase is directly related to a game’s “branching factor,” or the average number of moves available on any given turn. Chess’s branching factor is 35. Go’s is 250. Games with high branching factors make classic search algorithms like minimax extremely costly. Minimax creates a search tree that evaluates possible moves by simulating all possible games that might follow, and then it chooses the move that minimizes the opponent’s best-case scenario. Improvements on the algorithm — such as alpha-beta search and null-move — can prune the chess game tree, identifying which moves deserve more attention and facilitating faster and deeper searches. But what works for chess — and checkers and Othello — does not work for Go.

The trouble is that identifying Go moves that deserve attention is often a mysterious process. “You’ll be looking at the board and just know,” Redmond told me, as we stood in front of the projector screen watching Crazy Stone take back Nomitan’s initial lead. “It’s something subconscious, that you train through years and years of playing. I’ll see a move and be sure it’s the right one, but won’t be able to tell you exactly how I know. I just see it.”

But finally, Go computers are catching up due to advances in AI theory:

It wasn’t long before he made his breakthrough. Coulom had exchanged ideas with a fellow academic named Bruno Bouzy, who believed that the secret to computer Go might lie in a search algorithm known as Monte Carlo. Developed in 1950 to model nuclear explosions, Monte Carlo replaces an exhaustive search with a statistical sampling of fewer possibilities. The approach made sense for Go. Rather than having to search every branch of the game tree, Monte Carlo would play out a series of random games from each possible move, and then deduce the value of the move from an analysis of the results.

Rather than having to search every branch of the game tree, Monte Carlo would play out a series of random games from each possible move.

Bouzy couldn’t make it work. But Coulom hit upon a novel way of combining the virtues of tree search with the efficiency of Monte Carlo. He christened the new algorithm Monte Carlo Tree Search, or MCTS, and in January of 2006, Crazy Stone won its first tournament. After he published his findings, other programmers quickly integrated MCTS into their Go programs, and for the next two years, Coulom vied for dominance with another French program, Mogo, that ran a refined version of the algorithm.

Good reading for game theory nerds.

50+ chapters of grad skool advice goodness: From Black Power/Grad Skool Rulz

About these ads

Written by fabiorojas

June 6, 2014 at 12:06 am

Posted in fabio, fun, just theory

4 Responses

Subscribe to comments with RSS.

  1. I am an amateur player at both, and both are great board games. It’s interesting to see on orgtheory a post like this, which I’ve thought about for a while. Compared with chess (8×8), go (19×19) is, I believe, much more complex (and thereby more addictive, but not better obviously) since most (serious) chess players could play like a Kasparov in the first 10 or even 20 moves as long as he/she knows some openings and traps. But many professional chess players who I talked to and had some (most of them limited) exposure to go, would still disagree with me. If you check out USCF players and ratings, actually you could find ten-year old’s with an expert’s rating (>2000) is not that rare, which says something about it. Fischer made some comments like (correct me if I am wrong) it’s all about memorization in chess today (well, to some extent), and that’s probably why he invented chess 960, which speaks to the real limitation of chess; that is, all initial positions are fixed for the pieces. And the calculation, if you ever use a computer to do the analyses, is more on the linear side; that is, it’s pretty clear who is gaining advantage or not (to great extent). In go, I bet you can see whether one is a novice or pro in the first ten or 20 moves, but hardly ever you could give someone definitive evidence in many occasions. The challenge also comes from a lack of computer gurus versed at go. If you’ve had exposure to and played both games, actually you would find they reflect profound cultural differences between the East and West. If I have to liken the comparison between the two games to something,then go is like Taoism and chess positivism, go is like impressionism and chess realism.

    The comparison about the number of possible moves is kind of interesting, but not that accurate since human brains can readily rule out some impossible moves. Like in go, rules/experiences tell you not to place any stone in the lowest two ranks for the first couple of moves and in chess, rarely it is recommended to move a flank pawn or move knights to some flank files in the first couple of moves, which makes the possible reasonable moves for white to be limited to probably seven or eight (most common).

    Like

    John

    June 9, 2014 at 6:33 pm

  2. John, one issue that go/chess comparisons often overlook is that chess is (roughly) monotonic in terms of complexity vs. time. As time goes on, you get fewer and fewer pieces in chess. In go, it is ambiguous. You fill up space, but that is not stable. Groups can be captured and reborn. That’s probably why chess is boring in some respect. The complexity slope is flat or down. While, it oscillates for go.

    Like

    fabiorojas

    June 9, 2014 at 6:40 pm

  3. I am not sure if this would be fair to chess, but draws in chess can be quite ugly. The draw in chess could be subjective (e.g., with some accidentally repeated moves) or stalemate when one side is clearly gaining advantage, which I would argue/guess is actually an imposed rule (e.g., like castling or en passe) to make the game chart toward a bit more unexpected/lively. Draws in go, such as triple-ko draw, is just stunningly beautiful. Think about the rule in go, it is so simple, but its complexity unbelievable. Plus the rate of draw is so much higher in chess than it is in go.

    Looks like probably we should have a new section on game theory in sociology, where we could play/study board games and make a living out of it. But really they are not just board games, since so many life/science principles could be found in these two board games.

    Like

    John

    June 9, 2014 at 10:15 pm

  4. Now, I read through the details of that post. Just for reference, although Norimoto Yoda was probably one of the best in Japan, but he’s long passed his prime time. So he is probably considered as an average nine-dan (the highest level for go professionals, and there are a total of nine for professionals, one for each level from one to nine). With a four-stone handicap (between Crazy Stone [the computer] and Yoda), it’s like a nine-dan against a weak one-dan (the lowest level among go professionals). The difference is certainly beyond trivial. It would usually take a go prodigy at least ten years (e.g., Lee ChangHo, a Korean go prodigy who got the first important world champion at the age of 14) to go from one to nine dan without some rule-breaking treatment. I am not sure what’s the comparison in chess; it would probably be like Kasparov (certainly above 2800) against a 2000-point rated player? A deep-blue in go (that can defeat the best go player/s, the majority are in China now) is probably hard to emerge, my prediction? at least 20 years, to say the most optimistic.

    Go is just so not popular here. Here is a side note. When I was asked to sketch my bio, including interests (of course I wrote down go), and sent to an administrative coordinator, I was literally told that there was a misspelled word, and need to send corrections.

    Like

    John

    June 9, 2014 at 11:09 pm


Comments are closed.

Follow

Get every new post delivered to your Inbox.

Join 1,653 other followers

%d bloggers like this: