Wednesday, June 25, 2008

Go from a set theoretic perspective

As I work on Dakengo (my Go playing engine written in Common Lisp), I'm constantly trying to think in terms of abstractions. Consequently, one of the ideas that popped into my head recently is to try to build a set theoretic model of Go and see if I can derive anything useful. So starting with this entry, I'm going to write down these ideas as they develop.

Some definitions are in order. I'm going to use the term position to refer to a board configuration with zero or more black and/or white stones placed on the intersections, as they would be in a game of Go.

I'm going to use the term size to refer to the dimensions of a square board. I'm going to restrict myself to board sizes that are actually played in the real world: 9x9, 13x13, and 19x19. Of course, I can add more to the list (for example, some people toss around 25x25 as the next largest board size that anyone might consider playing). The important point is at the end of the day my goal is to write code that runs on actual machines, so I'm not interested in mathematical infinity. It's tough enough that the number of possible positions is so large as to be practically infinite, even if technically finite.

Also, I'm going to assume some other basic attributes of a game of Go, such as there being two players, one playing white stones and the other black, that each player alternates in placing a single stone (possibly removing prisoners), and that there are mutually-agreed conditions under which the game will end. I'm not going to consider non-traditional variations derived from Go.

Let's consider sets of positions. One such set to contemplate is that which contains all possible unique positions. Let's call it P. This set is finite because on any given Go board there are finitely many possible configurations of black stones, white stones, and empty intersections. And as I mentioned above, I'm restricting myself to a finite number of possible board sizes.

Right off the bat, I want to partition P into subsets. This is because when we want to start a game of Go, we have to make some choices before the first stone gets placed. Those choices then reduce the kinds of positions that we need to reason about as the game proceeds. And reasoning about positions is what this effort is all about.

With some simplification, the choices boil down to:
1. the size of the board
2. which scoring rule is in effect
3. which ko rule is in effect
4. whether suicide moves are allowed
For the time being, I won't drill down into what the different superko rules are, or how territory scoring compares to area scoring, or what the end game protocol is, or any other such details. That stuff doesn't matter at this point and will just muddy the waters. What's important is that choices from those areas have to be made in order to play.

Let's use Pnr as the name for the subset of P whose members, which I'll often refer to as p or q or some other lowercase letter, are constrained to those that are valid based on the rules listed above. Here n is one of the board sizes (9, 13, 19, etc) and r is a selection from the other choices. I think much of the time, I won't specify r in any detail, but I think it will be helpful to be explicit about n in most cases.

Next time, I want to talk about interesting subsets of Pnr, and even more interesting than that, I want to define relations between elements of these sets.