BenjaminTeuber/Thoughts about Go Programming

Sub-page of BenjaminTeuber

Although I didn't actually spend so much time creating Go playing programs, I have many ideas about that topic:

Table of contents Table of diagrams
Bamboo joint
Kosumi
Strange jump
Super bamboo joint

The right data structure

Almost all Go programmers do everything on a square data structure that is similar to the boards we're playing on without further thinking. I believe this is a big mistake, as especially for pattern matching, a graph representation seems much more suitable.

Why use a square board?

People are used to playing on squares normally, but speaking in mathematical terms, you can play on any kind of graph as the only board property being used by the rules is being-adjecent (this fact makes Go boards much easier than chess or even mills boards). An example of a different kind of topology is RoundGo (actually this gave me the idea, as once I thought: "A perfect Go program should also be able to master Round-Go").

Obviously, playing on any graph equivalent to the graph of a 19X19-board gives exactly the same game as the square board. For human players, the square-structure gives the advantage that we can use our cognitive abilities to "see" things like surround, territory and distance easily. But a computer doesn't have those abilities, so the advantages don't hold, and the step from graph-go to square-go just make things more difficult, not easier.

Pros and cons of graph representation

When memorizing a pattern in graph representation, we will extract a subgraph of the board, and to look for it on another board, we must decide if it equals some subgraph of it. This procedure will cost more time that normal PatternMatching at first, but shows the clear advantage that we don't have to care about symmetry and stuff.

The next step will be to allow some variables and recursion for pattern definitions - and this will be the BIG point for our graph structure...

Chains as units

Each novice knows that "strings of adjectent stones somehow belong together". For pattern definitions, treating strings as units is just perfect:

[Diagram]
Bamboo joint  
[Diagram]
Kosumi  
[Diagram]
Strange jump  

Look at these shapes. In all of them, both black chains are connected by the same reason: There are two points (a and b) that are adjecent two both chains, so both points are miai for connection. If we had defined some pattern "black chain" that knows its "liberties", all three shapes are covered with exactly the same pattern definition. Using Prolog writing, it would somehow look like this:

miai_connected(X,Y) :-

 black_chain(X),
 black_chain(Y),
 liberty(X,A),
 liberty(X,B),
 liberty(Y,A),
 liberty(Y,B).

Now that we saw that treating chains as units is very neat, we have to think how to do so. One way would be to use just chains and no longer single stones in our data-structure, but this turns out to lose some information because after capture, the "inner structure" of a chain will be important again (think of nakade?, ishi no shita). So we have to go the other, more general way:

  • allow patterns to reference to other patterns
  • allow recursive patterns

This will also make a rekursive definition of shicho or more advanced stuff like eye, moyo, territory possible.

Core features of "the" program

Self-learning Pattern Library

Everything should just be calculated once, then it has te be "remembered". The database will - of course - make use of the "flexible-graph" datastructure including sub-pattern-abstraction, that means that instead of memorizing complete problem constellations or even the whole board, it will just save connection- and eye-information and maybe an additional information like "this and that kind of eye together is still killable"

Memorize Threat Information

After having calculated sth., not just the result should be stored, but also any opponents move that is a threat against it and maybe how it should be answered. This will be very useful to derive further results from this later, e.g. the rule "if A and B are connected and B and C are connected and there is no move threatening at both connections at once, then A and C are connected as well" seems very nice.


Vlad: Interesting ideas here! I am not sure about this "chain as units" stuff:

  • for the first, miai connection isn't the same as a firm connection, because one might decide to let oneself cut;
  • for the second, there is for example eye information that is lost (in your third example Black may have an eye, the others don't).
[Diagram]
Super bamboo joint  

:-) What about this dia? The group is actually fully alive!

Benjamin: I didn't write down yet how exactly I define paths (see below) and stuff. But using my definition for eyes it's easy to prove why that group is alive: Considering the three connection paths (a or b), (c or d), (e or f), both x and y are "surrounded" by black connection paths and strings and therefore eyes. I think you get the idea how I mean it...


How can a computer "understand" what's going on?

Levels of understanding

There are many different levels of understanding from basic connections until territory, each one based on the lower levels. Many programs try to omit this hierarchy by playing around with influence functions, moyo estimation and other hopeless stuff - a master program has to forget about this stuff and understand things slowly, one after another:

Basic-Connection

That means just to recognize chains - no problem.

Basic-Capture

Also very easy. A chain without liberties is dead.

Complex-Connection

The first non-trivial fundament of go. It means reading out to which points/chains a chain is are able to connect / can be cut of. This also includes reading for basic capture. After reading out connections, a program has to memorize the "path" along which the connection is made.

Eyes

Black eyes are regions of white and empty stones being "surrounded" by black chains that are all (complex-)connected, and where black is able to connect to all empty eye-points. The eye space must be distinct from the connection-paths. (This eye definition seems best to me, as it also covers the TwoHeadedDragon)

Moyo

Black moyo is a region of empty points where black can connect to from his chains on the board, but white cannot.

Territory

Black territory is a region of white and empty points where black can connect to all empty points and all white stones are dead.

This definition is actually a bit redundant, and it uses Japanese scoring. Probably I will do area-scoring instead - we'll see that later


Jeff: Good start. I like where you're going. There are some challenges, though, that the program must be capable of mastering. These situations come up even at the master level (as best I can tell based on my x kyu understanding of the game). A player judges he has complex-connection from A to B and from A to C. A is alive. Unfortunately, if either B or C were severed from A, he will loose the game (or a large chunk of territory/influence). Is there a dual-threat? Often there is.

Benjamin: Right, The threat-stuff will come up next^^

hotcoffee: I'm not a strong Go-Player, but consider myself a decent mathematician, and a C++ programmer occasionally blessed by inspiration. My own ideas regarding an approach to computer Go AI are very similar to your own, creating objects to model strings of stones. After thinking it up, I had to search for quite a qhile on SL to find a page with this approach and had almost given up. I had a few neat ideas which expand the ones you list here, and I was interested to know if you are intending to continue expanding on or implement your ideas? It'd be nice to be able to boucne ideas back and forth.


Algorithm


BenjaminTeuber/Thoughts about Go Programming last edited by MrTenuki on July 9, 2006 - 01:57
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library