### Locality in Go

In June I said this on Twitter:

@luqui The board is a graph. A node for each empty point, a node for each group. Legality of a move depends only its radius 2 neighborhood.

@luqui The distance between two points may shrink by at most 2 when a move is played (because groups can be joined). Speed of light is 2.

@luqui Let R be a region of the board. The set of possible states of R after T moves is not affected by anything farther than cT = 2T.

@luqui Note: 2 points may move away from each other FTL (if a group dies), but not towards each other. Moving away is not communicating.

@luqui Information about legal possibilities can’t go FTL, but info about good moves can; strategy now depends on far future possibilities.

I’ll explain this again in a different way. Minimax search is an algorithm for perfect play in any combinatorial game. To solve Go by minimax search would, however, take a very long time, and so it is not a practical method by itself.

One technique that has been useful for Chess is to apply minimax search to a similar game with a new rule. The new rule is this: after *n* moves, for some particular *n*, the game will end and the final score will be determined using a board evaluation function. The optimal move in this modified game may then be assumed to be a decent move in the original chess position.

Since Go has a large number of moves available from most game positions, the values of *n* for which such calculations are practical are quite small. If we could throw out most possible moves (that is, if we could know that they are suboptimal without search), then we could search more deeply.

Enter *locality* – the fact that it takes a long time for effects on a go board to propagate over a long distance.

(The shading in this diagram shows the distance to the highlighted region, as defined by the metric discussed in the quoted material).

Suppose that our board evaluation function only cares about a small region R of the board, such as the highlighted region shown above. This means we’re now dealing with a local goal instead of the overall goal of winning the game. Let’s just press on, and at a later date we can figure out how local goals relate to winning the game.

If *n*=1, then the value within a region depends on the set of states that R can be in after one move. To determine which states are possible, we would need the following information:

- If a chain has only one liberty within R, we wish to know if it has an external liberty. This requires looking at points at distance 1 from R.
- If a chain has no liberties within R, then it
*must*have an external liberty; but whether it can be captured depends on if it has two external liberties. This again requires looking at points at distance 1. - If an empty point in R is bordered only by (WLOG) white stones, then the legality of a black play there may depend on whether it captures a white chain that is itself at distance 1 from R. To answer this question involves looking at points at distance 2 from R.

This is the extent of the information we may need about the rest of the board. So the set of reachable states in R depends only on a radius-2 neighborhood of R.

Now we can proceed by induction. Suppose that the depth-(n-1) value of R depends only on a neighborhood of radius 2(n-1). Then to get the depth n value, we would simply look at all the possible states that the radius 2(n-1) neighborhood can be placed into by one move, and take the max (or min) of their depth-(n-1) values. The set of possible states depends only on a radius 2 neighborhood of the radius 2(n-1) neighborhood – that is, it depends only on a radius 2n neighborhood of R. Thus the depth n value depends only on the depth 2n neighborhood.

Of course, this bound is not very tight; it would be possible to achieve much tighter bounds.