Re: [computer-go] Data structures for Go

[Richard Brown <rbrown@xxxxxxxx>]

Hmmm, I'm not sure that I -- lowly IT schlub with no further credentials
than a B.A. in "Asian Studies" -- should be giving advice to a CS prof,
but...

Peter Drake wrote:
> We're contemplating doing some research on data structures for computer 
> Go.  It is not obvious to us how to store chains, groups, eyes, 
> connections, and so on in an incrementally-updatable way that supports 
> undo (which is necessary for any kind of search).  The problem is 
> further complicated by the fact that the objects being represented are 
> fluid (growing, splitting, and merging) and sometimes ill-defined.
Here's a vote for linked lists of points.  Easy to join together --
and to separate, in the case of undo.  Capture -- and uncapture -- of
anywhere from one to four groups is also very easy, using linked lists.

Even multiple-stone suicide (if that's permitted under your rule set),
and the undoing of same, is easy.  Others may have better ideas, but
I've found the linked-list approach to be just dandy for such purposes.

[I tried board bitmaps, and found them too unwieldy.  That is, I was too
lazy to get them working after I had already implemented linked lists!]

The linked-list solution seems trivial and obvious to me now, but perhaps
that's only because I haven't had to pay much attention to it lately; it's
been working fine, which has allowed me recently to concentrate on other,
more challenging tasks.

Anyway, it's certainly trivial compared to move selection, isn't it?

I had to respond to Peter's message, though, because I am actually
deeply intrigued by the implications of his closing question:

> Is this something the computer Go community would find useful, or is it 
> considered a minor implementation detail?
When the Ing prize was around [It's expired now, right?] they said that
no part of your program could be written by anyone else.  So, even if I
would "find useful" some code that you produce, I wouldn't have been
allowed to use it in my program, in competition, would I have been?

That's why I wrote this sort of code myself.  And before I did write it,
and at the time that I was writing it, and for a long time afterward --
right up until this very moment, in fact -- I expected that others would
do likewise, as was so required by the rules for competing for the Ing
prize.

But maybe times have changed.

Is it now all right, in computer go, to "find useful" the work of others?

I have always considered this an implementation detail that _everyone_
who writes a go-playing program should be required, as I was, to do for
himself or herself.

Certainly, it's o.k. with me if others, in an _academic_ setting,
"find useful" Peter's work, but I wouldn't want to have to _compete_,
for anything like the Ing prize, against any of those others, who might
appropriate Peter's work for use in their _competitive_ programs.

It hardly seems fair, at this juncture, to change the rules.

Do I misunderstand?  And what about Benson's algorithm?  Some programs
use that, don't they?  I guess it's all right; I don't really know...
As long as you pick your own variable names, and type the code yourself?

Or what?

Can some kind reader help me to understand these sorts of things,
as they apply to computer go, and to computer go _competition_?

My thanks to Peter, whose message prompted me to articulate my
feelings of uncertainty in this area.

--
Richard L. Brown            Office of Information Services
Senior Unix Sysadmin        University of Wisconsin System
                           780 Regent St., Rm. 246
rbrown@xxxxxxxxxxxxxxxxx             Madison, WI  53715

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://computer-go.org/mailman/listinfo/computer-go