space and games

November 11, 2011

Locality in Go

Filed under: Go — Peter de Blanc @ 7:43 am

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.

Distances in Go

(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.

November 10, 2011

Papers on Go

Filed under: Go — Peter de Blanc @ 12:59 am

I’m compiling some references to Go research. This is just a start:

The Game of go as a complex network.
A Dynamical Systems Approach to Static Evaluation in Go.
Time symmetric Go.
A Note On Go Endgame And Nonstandard Analysis.
Optimizing GoTools’ Search Heuristics Using Genetic Algorithms.
Computer Go: Knowledge, Search, and Move Decision.
Computer Go as a Sum of Local Games: An Application of Combinatorial Game Theory
When One Eye is Sufficient: A Static Classification

June 14, 2010

Some material from my upcoming book

Filed under: Go — Peter de Blanc @ 9:15 pm

I’m writing a book about Go strategy. I’ll be comparing moves by professionals to moves by amateurs in the 1-3k range. My hope is that amateur players may improve by trying to imitate the professionals.

Two-Stone Corner Patterns
Three-Stone Corner Patterns
Four-Stone Corner Patterns

November 4, 2009

Go proverbs: “A rich man should not pick quarrels.”

Filed under: General, Go — Peter de Blanc @ 1:19 pm

Go players have hundreds of proverbs — pithy sentences that convey important heuristics. It is not enough to simply read proverbs; you must study them at length to unfold them into procedural knowledge.

Most proverbs are particular to Go (e.g. six die but eight live), but some generalize to other adversarial situations, and a few proverbs contain important lessons about rationality.

One of my favorite proverbs states that a rich man should not pick quarrels. Go, in its most common formulations, is a game of satisficing. The player with more points wins the game, and winning is enough; there is no extra reward for winning by a large margin. The proverb says that if you are currently winning (i.e. you are a rich man), then you should not do things (such as picking quarrels) that make the outcome more random. By decreasing the variance in the probability distribution for your final score, you increase the probability that you will hold onto enough points to win. Anything that makes the game simpler and more predictable is good for you.

We can see this in Chess (the winning player should seek to trade pieces) and in epee fencing (the winning player should seek double-touches).

If, on the other hand, you are a poor man, then you should pick quarrels. There’s a good example of this in Indiana Jones and the Temple of Doom. In one scene, Indy is in the middle of a rope bridge, and swordsmen are approaching from either side, so Indy cuts the bridge.

If you are winning, simplify. If you are losing, complexify.

Powered by WordPress