Tamsin's Paper Go Computer


I don't know whether this idea has already been put forward in the reams of pages about computer go. Anyway, I remember reading that Alan Turing devised a chess-playing program that he could execute himself from instructions on a piece of paper. This was before the days of readily available programmable computers. It enabled him to test the strength of his approach to chess programming. It played very poorly (a "caricature of my own style"), but nevertheless it worked.

Could this be applied to go in a useful way? Much of the effort in programming go must be in the coding. However, wouldn't it be good to know in advance that the strategic and tactical algorithm?s are going to be effective?

Therefore, I suggest a way to develop a strong go program might be to write down a series of instructions or priorities (a kind of super-checklist) and to follow them strictly when playing a game, to find out if these would be worth encoding. Obviously it would take too long to play many complete games like this, but a number of runs up to move 100 or so should provide useful information.

HolIgor: Actual coding of the algorithm is not so difficult, even though the calculations may be quite involved. Formulation of the algorithm is on the other hand a very difficult thing. If the rules are formulated I can try to implement them.

One can first ask a simple questions: what data should be collected from the board position. For example, the number of liberties of the stones, Manhattan distances etc. The second question is what can one do with all that information.

WilliamNewman: Many programming languages support a style of just writing down a set of instructions or priorities as easily as you might do it on a set of cards, if I understand correctly what you mean. (It sounds rather like a simple case of what's called "functional programming". If you look at section 5 of [ext] http://homepages.inf.ed.ac.uk/wadler/papers/sigplan-angry/sigplan-angry.ps, you might find that it sounds similar.) But any time you specify behavior to something without common sense, you end up needing to be very pedantic about what you mean. Whether with ordinary code or with cards (assuming that the instructions are going to be followed by a machine, not by your human buddy), you can't just write your rule to do one thing if, e.g., a move is urgent and another thing otherwise. You can still use high level concepts like "urgent", "sente", "miai", or "thick", but only if you can define them precisely to the machine. Generally such precise definitions have to ground out somewhere in terms of trivial concepts like the number of adjacent stones or the distance from the edge, which makes things difficult. Even defining medium-level concepts like "dead" or "connected" or "surrounded" at the level that humans use them seems to be very difficult. (If you had good definitions of them you could solve general tsume-go problems, which no one knows how to do...)

Matt Noonan: I think that Dieter did something like this, though not as extreme. If I remember right, he played for a while using only proverbs when possible. I seem to remember him being disappointed with the results, but maybe he can give his own impressions here.

Dieter: I did play several games trying to stick to principles. The conclusions were more on the mental aspect than the rational aspect of playing a game:

  • I found it very difficult not to get caught up in my bad habits of playing without thinking, out of pure desire to kill/invade/develop
  • I tended to read less deeply and choose a move from its merits according to a strategic principle. So I needed more emphasis on tactical backup of the different choices.

Gorobei: I tried something recently along these lines: writing minimal programs to solve the life and death problems in Graded Go Problems for Beginners. The first program was just "find a group in atari and play its liberty," and it could solve the first 12 or so problems. Later programs needed concepts like: kill a group in atari, otherwise save my group in atari; if no atari, put an enemy group into atari; given two ways to kill an enemy group, pick the one that maximizes our own liberties, etc. After the first 40 or so problems, the rules got quite nasty.

axd: DGS might offer a crude way to assist in this experiment: one can tie a Notes pane to a game and formulate the rules in it; whenever the game comes up, the rules pane will appear and you can "execute" them. You can even try different "programs" in different games, as each game has its own (private) notes pane.

Tamsin's Paper Go Computer last edited by axd on November 15, 2007 - 23:17
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library