File computer-go log.199801

[sympa-request@xxxxxx]

This digest for list has been created on Wed Jan 21 17:54:10 3898

------- THIS IS A RFC934 COMPILANT DIGEST, YOU CAN BURST IT -------

From: rbrown@xxxxxxxxxxxxxxxxx
Mime-Version: 1.0
Date: Wed, 21 Jan 1998 10:29:36 -0600
Message-Id: <000719D2.3088@xxxxxxxxxxxxxxxxx>
Subject: Notation
To: computer-go@xxxxxxxxxxxxxxxxx
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-Description: cc:Mail note part
X-Sequence: 2
Precedence: list

Haven't contributed to this list in a while; been very busy.  Avid reader,
though.

Being intrigued by the thread "How To Make a Very Strong Go Program," and by
way of testing the new hsc.fr address, I thought I would share some ideas with
y'all.

Of primary concern is notation.  A good notation, for any sort of problem, can
bring us a long way toward a possible solution.  By "good" in the case of a go
notation, I mean that the notation has at least these properties:

     o     Efficiency.  The notation does not require much storage space, and
           yeilds easily to standard sorting and searching algorithms, so that
           it is not time-consuming to parse or otherwise process expressions.

     o     Convenience.  Information encoded into the notation is easily
           extracted and used by the program.  New information is easily
           encoded and processed for later extraction and use by the program.

     o     Symmetry.  Aside from the oft-touted eightfold visual symmetry of
           go -- namely, that a position is invariant with respect to trans-
           lations and rotations of the board -- there are in addition other
           symmetries it is desirable to exploit in a notation.

This last item deserves further attention.  Consider a specific situation, in
which a player might next place a stone on a board.  Not only is the "pattern"
of the board symmetric respect to eightfold visual symmetry, it is also
symmetric with respect to the actual colors of the stones.  In other words, if
we were to replace all the white stones with black stones, and vice-versa, the
pattern is still essentially the same pattern, invariant with respect to the
actual colors of the stones.

Clearly, the distinction between friendly and foe stones must be preserved, but
if a notation permits all "isomers" of a pattern to be described with a single
expression, "stripping out" the symmetries, so to speak, then it is a good one.

One particularly "go-like" symmetry which a good notation will take into
account, is the notion of the "edge" and "corner" of the board.  As an example,
consider a two-eyed group in the middle of the board, and a similar one, say,
in the lower left corner.
                                                 |
                            O O O O O            |O O O O
                            O   O   O            |  O   O
                            O O   O O            +---------

                             Middle.               Corner.


The two eyes that each group has are functionally equivalent, or symmetrical
with respect to whether they occur somwhere in the middle of the board, at
an edge, or in a corner.  A notation which is able to "strip out" this peculiar
go-symmetry, effectively making the middle-edge-corner distinction a don't-care
condition, is to my mind an absolute necessity.  The actual locations of the
groups or their eyes is of very little interest.

Oh, yes, one final thing (I've rambled on long enough for one message):  The
notation must not be bound by the _order_ of moves.  For example, suppose a
joseki situation arises, but the moves that created the situation were played
"out-of-order".  A program should be able to detect the joseki situation just
as if all the previous moves were played in "book order".  The actual order of
the moves should be a don't-care condition as well.  So it is extremely helpful
if there is a notation which permits the program to find the joseki situation
anyway, one which "doesn't care" about the actual order of moves, when the
program is trying to recognize such patterns.

Similar remarks apply to _ouba_ or "big points", and also to _tesuji_.  In
fact, if a pattern of interest of _any_ kind can (from the notation itself)
be instantly recognized without regard to various kinds of symmetries such as
actual location, color, order, or orientations of stones and/or vacant points,
then the notation suffices as "good".

More later.

Rich

------- CUT --- CUT --- CUT --- CUT --- CUT --- CUT --- CUT -------