IMAGE: Bryan Christie Design

Dead or Alive?

Let's start with the problem of the exploding tree of analysis. If we assume that the program must consider every possible continuation that could arise 12 plies into the future, as Deep Blue did in chess, you might expect to have to search a million times as fast. But we don't really need to pay that high a price, because there are ways to prune the tree of analysis.

One old standby, implemented in all chess programs, is called alpha-beta pruning, and it works by curtailing the examination of a move the moment it becomes clear that another move must be better. Let's say the program is comparing move A with move B, and it already knows that A leads to an advantage. If it finds, early on, that move B allows the other side to obtain a draw at the very least, then the program can cut off its analysis, saving a lot of time.

Alpha-beta pruning reduces the effective branching factor to about the square root of the number of move choices. For example, to look ahead 12 plies in pure brute-force mode, you would need to search only about 4 billion positions, or 4 x 10⁹, instead of 38¹²—or 10¹⁹—positions.

A newer way to cut back the overgrowth—null-move ­pruning—was not implemented in Deep Blue, even though one of its inventors, Murray Campbell, was a key member of the Deep Blue team. The algorithm performs a kind of thought experiment, asking how the position would look if you were to give up the right to move for one turn, thus allowing your opponent to make two moves in a row. If after that enormous sacrifice you still have a good position after a relatively shallow search, then the algorithm can stop its analysis right there. It has identified a cutoff point—a point at which the branch can be pruned, thus saving the labor of going through all the other possible responses.

Imagine that the program examines a line in which it has just won the opponent's queen—giving it an enormous material advantage—and the opponent has responded. Now the program asks: If I do nothing, can my opponent hurt me after, say, n–2 plies—where n is the number of plies I would have searched after a legal instead of a null move? If the answer is no, the program concludes that it has indeed won an entire queen for nothing, that its position is likely won, and that no further analysis is necessary. This dividend is well worth the shallow “n–2 ply” search the computer has invested.

In computer chess, the main risk in null-move pruning comes from the null move (or pass) itself, which is illegal in chess. Because it is illegal, certain positions that could be defended by a pass must lose; the null-move trick can cause a program to ignore this condition. In Go it doesn't matter, though, because players are allowed to make passes.

Null-move pruning was first proposed as a fairly conservative technique, curtailing the depth of search only by n–1 plies, but experimenters soon found that n–2 or even n–3 reductions sometimes gave good results. Even better performance comes from applying null-move pruning inside the reduced-depth search itself. Such “recursive null-move pruning,” when coupled with standard alpha-beta pruning, appears to reduce the branching factor to about the square root of the square root of the number of move choices. This means that recursive null-move pruning can keep the analysis tree from growing any faster in a Go program than it would in a chess program that did not use null-move pruning.

The upshot is that a machine searching no faster than Deep Blue did 10 years ago could go 12 brute-force plies deep in Go (with additional selective search extensions). It does so, however, without making a full and proper evaluation of the resulting positions, as it could do for chess.

Yet another time-saving technique emulates human thought (for a change). When human players search through the Go game tree, they generally check the live-or-dead status of each stone only once, then in effect cache the result in their memories. In other words, they don't check again unless they have good reasons to do so. The point of caching is to fetch often-used information rather than recalculate again and again.

The idea has been tried in computer chess, in the “method of analogy” algorithm, which reuses conclusions reached in one branch of analysis when similar positions arise in other branches. It reduces the search tree by a factor of three or four, but unfortunately the operations needed to cache, retrieve, and apply the conclusions slows the program by the same proportion. To wring a net gain out of the method, therefore, the slowdown must be contained, for instance, by using special-purpose hardware to do the computation or by finding new ways to chop the search tree even further.

Think of the tree again. What the method of analogy basically does is to take an entire branch from one part of the tree and graft it to another. Suppose that early on the program discovers a sequence in which white can win in just one ply, by capturing black's queen with a bishop. The program will then cache that sequence and apply it to latter parts of the search tree, provided that nothing major has happened in the meantime (like losing a piece) and that the bishop can still capture the queen.

In chess, this method of analogy works only for very short branches or for branches that contain mostly “forced” moves, that is, checks, check evasions, and captures. However, if the branches contain more than a ply or two of nonforcing moves (which present far more possibilities for calculation), then the program's accounting system breaks down.