Re: computer-go: Languages for programming go are?

[Daniel Bump <bump@xxxxxxxxxxxxxxxxxx>]

Bob Myers wrote:

> 2) If one were to imagine a new language, invented solely for the
> purpose of writing a great computer go system, what would its
> characteristics likely be?  (Or would there be multiple new languages,
> for different parts of the problem?)

It seems to me that this could be a productive line of thought.
Developing such a language could easily be as hard as writing
a program from scratch, but potentially very fruitful.

Probably the language would need to have support for maintaining
certain basic structures (a list of strings and their properties,
such as size, number of liberties, adjacent strings) during
reading, support for pattern matching and support for alpha-beta. 
About pattern matching, Tanguy Urvoy has done some very interesting
experiments with GNU Go which show that an approach based on finite
state automata from compiler design theory can be fast.

Robert Jasiek wrote:

> "no_side_condition". For a common language for every
> programmer we would have to agree on each term. However, 
> probably every programmer uses such terms differently. The
> problem of creating an efficient language is the problem of
> getting all programmers to agree on a meaning and usage of all 
> terms.

The term "group" is slippery. There are irreducible
groups (strings) and then larger units which can
potentially be split up. The problem is simplest for
strings.

The difficulty of agreeing on the definition of the
larger groups (superstrings or dragons) reflects the
the language would need to be extensible. At a
minimum, the user needs to be able to extend:

(1) The structures maintained during reading;

(2) The goal of the search (encoded in an
evaluation function).

To elaborate, reading can be performed for various
tasks, such as determining the life and death of a
string (liberty count is enough for this), life and
death of a dragon (eye shape is now important),
connections, or semeai. In practical terms, this
means that the user needs to be able to specify
which nodes are terminal, and what evaluation
function (expensive or fast) is used at them.

(3) Ordering of nodes. Efficiency of alpha/beta
depends strongly on the ordering of the nodes.

Reading can be accomplished by pushing or popping
moves on a stack. In evaluating a position, millions
of nodes can be generated this way, provided most of
the reading is done with an cheap evaluation function
(life or death of a string). It is not practical to
keep the entire move tree in memory. But it could
be practical, and very useful, if the language
provided tools for keeping a subset of the tree
in memory. For example, if a large subtree produces
the result that a certain move refutes another
move, it may be useful to collapse the subtree and
keep just the refutation. This means support for
pruning and merging move trees. Since different
reads may have different goals, merging the
resulting move trees might be tricky but if this
could be done, it might be very useful.

Daniel Bump