go > chess
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.